Eleven puzzle

双向广搜 + 映射

#include<cstring>
#include<string>
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
//#pragma comment(linker, "/STACK:1024000000,1024000000");

using namespace std;

#define INF 0x3f3f3f3f          //无穷大

long long d[30];
int g[5][5];                   //十三格拼图

struct node
{
  int g[5][5];                 //拼图
  int step;
  int x1,y1;                   //双向
  int x2,y2;
} p1;

map<long long ,int >mp[2];     //映射-键：值
queue<node>que;                //优先队列
 
int dir[][5]= {{0,1},{0,-1},{1,0},{-1,0}};                   //右左上下

bool inbound(node k,int x,int y)                            //黑格不过边界，不重合
{
  if(x >= 0 && x < 5 && y >= 0 && y < 5 )
  {
    if(k.g[x][y]==INF||k.g[x][y]==12) return false;
    else return true;
    return false;
  }
  return false;
}

long long getval(node k)    //从上至下从左至右将二维数组压维成一维数组
{
  long long sum=0;
  for(int i=0; i<5; i++)
  {
    for(int j=0; j<5; j++)
    {
      if(k.g[i][j]!=INF)
      {
        if(k.g[i][j]/10) sum=sum*100+k.g[i][j];
        else sum=sum*10+k.g[i][j];
        }
      }
    }
  return sum;
}

void bfsx(int flag)
{
  mp[flag].clear();
  node k;
  while(!que.empty()) que.pop();                          //清空
  que.push(p1);            //开始或结束局面入队
  mp[flag][getval(p1)]=1;  //储存映射
  while(!que.empty())
  {
    k=que.front();
    que.pop();
    long long pri=getval(k);
    if(flag)              //开局局面
    {
      if(mp[0][pri])     //相遇
      {
        if(mp[0][pri]+k.step-2<=20)                      //不超过最大步数
        {
          printf("%d\n",mp[0][pri]+k.step-2);
          return ;
        }
        else continue;
      }
    }
    for(int i=0; i<4; i++)                              //一号黑格四个方向
    {
      node temp=k;
      int s=temp.x1+dir[i][0];
      int t=temp.y1+dir[i][1];
      if(inbound(temp,s,t))
      {
        temp.step++;                                   //加步数
        if(temp.step>12&&!flag) continue;              //剪枝：终点开算步数超12去掉 12+10=2*11
        else if(temp.step>10&&flag) continue;          //剪枝：起始开算步数超10去掉
        swap(temp.g[temp.x1][temp.y1],temp.g[s][t]);   //交换位置：移动黑格
        long long pri=getval(temp);
        if(mp[flag][pri]) continue;                    //剪枝：去重
        mp[flag][pri]=temp.step;                       //储存步数
        temp.x1=s,temp.y1=t;                           //更新黑格坐标
        que.push(temp);                                //入队
      }
    }
    for(int i=0; i<4; i++)                             //二号黑格四个方向
    {
      node temp=k;
      int s=temp.x2+dir[i][0];
      int t=temp.y2+dir[i][1];
      if(inbound(temp,s,t))
      {
        temp.step++;
        if(temp.step>12&&!flag) continue;
        else if(temp.step>10&&flag) continue;
        swap(temp.g[temp.x2][temp.y2],temp.g[s][t]);
        long long pri=getval(temp);
        if(mp[flag][pri]) continue;
        mp[flag][pri]=temp.step;
        temp.x2=s,temp.y2=t;
        que.push(temp);
      }
    }
  }
  if(flag) printf("No solution!\n");
}

int main()
{
  memset(g,0x3f,sizeof g);                            //数组初始值无穷大
  g[0][2]=12;                                         //13格子的最终局面
  g[1][1]=1,g[1][2]=2,g[1][3]=3;
  g[2][0]=4,g[2][1]=5,g[2][2]=6,g[2][3]=7,g[2][4]=8;
  g[3][1]=9,g[3][2]=10,g[3][3]=11;
  g[4][2]=12;
  memcpy(p1.g,g,sizeof g);                           //结构体内的拼图初始化无穷大
  p1.x1=0,p1.y1=2;                                   //最终局面的xy坐标
  p1.x2=4,p1.y2=2;
  p1.step=1;
  bfsx(0);
  int T;
  scanf("%d",&T);
  while(T--)
  {
    memset(g,0x3f,sizeof g);
    for(int i=0; i<5; i++)                          //写入开始局面
    {
      if(i==0||i==4) scanf("%d",&g[i][2]);
      else if(i==1||i==3) for(int j=1; j<=3; j++) scanf("%d",&g[i][j]);
      else for(int j=0; j<5; j++) scanf("%d",&g[i][j]);
    }
    int flag=0;
    for(int i=0; i<5; i++)
    {
      for(int j=0; j<5; j++)
      {
        if(g[i][j]==0)
        {
          g[i][j]=12;                              //黑格编号
          if(!flag) p1.x1=i,p1.y1=j;               //第一个黑格
          else p1.x2=i,p1.y2=j;                    //第二个黑格
          flag=1;
        }
      }
    }
    memcpy(p1.g,g,sizeof g);
    p1.step=1;
    bfsx(1);
  }
  return 0;
}

笔记：拼图用压维的方式储存当前移动状态，遍历的过程用映射的方式标记点与步数，双向广搜，先搜索结束固定的点储存map，之后都不用更改，再搜索起始拼图，这个方式很适合多次搜索，节约了一多半的时间