Как написать компаратор для карты и priority_queue, где элементы представляют собой двухмерный массив - PullRequest
Новая
       31

Как написать компаратор для карты и priority_queue, где элементы представляют собой двухмерный массив

0 голосов
/ 05 июня 2018

Я пытаюсь осуществить поиск A * для головоломки N, размер которой равен 15. Мое начальное состояние будет случайным.Состояние цели - это массив des в коде.Я могу поменять местами только плитки с 0 (пустое состояние) в 4 направлениях головоломки, чтобы создать новое состояние.Для реализации этого я использовал priority_queue и 4 карты.Для всего этого я использовал 2-х мерный массив.Сравнение - это компаратор для priority_queue, а map_cmp - это компаратор для 4 карт.Vis используется для отслеживания посещенных состояний, Dis - для подсчета пути, parent - для сохранения родителя состояния, а ab - для сохранения позиции 0 (пробела) каждого состояния.Вот код: 

enter code here
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};
int des[4][4]={{0,1,2,3},{4,5,6,7},{8,9,10,11},{12,13,14,15}};
int func1(int node[][4])
{
    int cnt=0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(i==0 && j==0)
                continue;
            if(des[i][j]!=node[i][j])
                cnt++;
        }
    }
    return cnt;
}
double func2(int node[][4])
{
    int a,b,x,y;
    double sum=0.0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(node[i][j]==0)
                continue;
            a=node[i][j];
            x=a/4;
            y=a%4;
            sum+=sqrt((i-x)*(i-x)+ (j-y)*(j-y));
        }
    }
}
struct map_cmp {
    bool operator()(const int (&a)[4][4], const int (&b)[4][4]) const {
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(a[i][j]!=b[i][j])
                    return true;
                else
                    continue;
            }
        }
        return false;
    }
};
map<int[4][4],int,map_cmp>vis;
map<int[4][4],int,map_cmp>dist;
map<int[4][4],int[][4],map_cmp>parent;
map< int[4][4],pair<int,int>,map_cmp >ab;
struct compare
{
    bool operator()(const int (&a)[4][4],const int (&b)[4][4] )const{
        return ((dist[a]+func1(a)) < (dist[b]+func1(b)));
    }
};
bool isValid(int row, int col)
{
    return (row >= 0) && (row < 4) && (col >= 0) && (col < 4);
}
int bfs( int src[][4],int a,int b)
 {
    int u[4][4];
    int v[4][4];
    int x,y;
    vis[src]=1;
    dist[src]=0;
    parent[src]={0};
    ab[src]=pii(a,b);
    pii pos;
    priority_queue < int[4][4], vector < int[4][4] > , compare > q;
    q.push(src);
    while(!q.empty())
    {
        u = q.top();
        q.pop();
        pos=ab[u];
        for(int i=0;i<4;i++)
        {
            copy(u,u+16,v);
            x=pos.first+fx[i];
            y=pos.second+fy[i];
            if(isValid(x,y))
            {
                swap(v[pos.first][pos.second],v[x][y]);
                vis[v]=1;
                dist[v]=dist[u]+1;
                ab[v]=pii(x,y);
                parent[v]=u;
                if(memcmp(des,v,sizeof(des))==0)
                    return dist[v];
                q.push(v);
            }
        }
    }
}
int main()
{
    int a,b,i,j,k,m,n,x,y;
    int result[5];
    int src[4][4]={{7,2,12,11},{10,14,0,6},{8,13,3,1},{9,5,15,4}};
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            if(src[i][j]==0)
            {
                x=i;
                y=j;
                break;
            }
        }
        if(j!=4)
            break;
    }
    a=bfs(src,x,y);
    ab.clear();
}

Я получаю ошибки для компаратора карт и priority_queue.
Это:
1. Нет совпадения для оператора [] в dist [a] / vis / parent / ab [короче все карты]
2. недопустимое присвоение массива
3. нет соответствующей функции для вызова 'std :: priority_queue, сравните> :: push (int (* &) [4]) '

Это мой первый пост здесь.Извините за любые ошибки.Буду признателен за любую помощь, так как я уже сделал все, что мог

1 Ответ

0 голосов
/ 05 июня 2018

Оставьте в покое проблему с неизменяемым массивом.

Давайте рассмотрим вопрос о названии вопроса, начиная с определения std::priority_queue, std::priority_queue<class _Tp, class _Container, class _Compare>

три параметра elementтип , контейнер элемента (по умолчанию std :: vector), компаратор (это класс с () компаратором, по умолчанию std :: less). 

    class TpType {};

    class TpTypeComparatator {
        bool operator () (TpType &a, TpType &b) const {
            return true;
        }
    };

    std::priority_queue, TpTypeComparatator> q;
...