时间戳

首页 > 解决方案 > 如何为元素为二维数组的 map 和 priority_queue 编写比较器

c++ - 如何为元素为二维数组的 map 和 priority_queue 编写比较器

问题描述

我正在尝试为大小为 15 的 N 拼图实现 A* 搜索。我的开始状态将是随机的。目标状态是代码中的des数组。我只能在拼图中的 4 个方向交换 0（空白状态）的图块以创建新状态。为了实现这一点，我使用了一个 priority_queue 和 4 个地图。对于所有这些，我使用了二维数组。Compare 是 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[简而言之所有映射] 中的 operator[]不匹配
2. 无效的数组分配
3. 调用 'std::priority_queue, compare> 没有匹配的函数::push(int (*&)[4])'

这是我在此的头一篇博文。抱歉有任何错误。任何帮助将不胜感激，因为我已经尽我所能

标签： c++multidimensional-arraycomparatorpriority-queue

解决方案

不理会未调整大小的数组问题。

让我们考虑问题标题中的问题，从定义开始std::priority_queue， std::priority_queue<class _Tp, class _Container, class _Compare>

三个参数是元素类型、元素容器（默认 std::vector）、比较器（这是一个带有 () 比较器的类，默认 std::less）。

    类 TpType {};

    类 TpTypeComparator {
        bool operator () (TpType &a, TpType &b) const {
            返回真；
        }
    };

    std::priority_queue, TpTypeComparatator> q;

推荐阅读