洛谷—— P1379 八数码难题

https://daniu.luogu.org/problem/show?pid=1379

题目描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入输出格式

输入格式：

输入初始状态，一行九个数字，空格用0表示

输出格式：

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入输出样例

输入样例#1：

283104765

输出样例#1：

4

BFS搜索每种移动的状态，hash判重

 #include <cstring>

 #include <cstdio>

 #include <queue>

 #define swap(a,b) {int tmp=a; a=b; b=tmp; }

 const int op[][]={{,,},

                     {,,},

                     {,,}};

 bool vis[];

 struct Checkerboard {

     int step;

     int map[][];

     Checkerboard() { step=; memset(map,,sizeof(map)); }

 } u;

 std::queue<Checkerboard>que;

 int fx[]={,,,-};

 int fy[]={,,-,};

 char s[];

 inline bool print(Checkerboard x)

 {

     for(int i=; i<; ++i)

       for(int j=; j<; ++j)

         if(x.map[i][j]!=op[i][j]) return ;

     return true;

 }

 inline int BFS()

 {

     que.push(u);

     for(Checkerboard v; !que.empty(); )

     {

         v=u=que.front(); que.pop();

         int tmp=,t=,k=;

         for(int i=; i<; ++i)

           for(int j=; j<; ++j)

             tmp+=k*u.map[i][j],t++,k*=t;

         vis[tmp]=;

         if(print(u)) return u.step;

         int x,y;

         for(int i=; i<; ++i)

             for(int j=; j<; ++j)

             if(u.map[i][j]==)

             {

                 for(int k=; k<; ++k)

                 {

                     x=fx[k]+i,y=fy[k]+j;

                     if(x>=&&y>=&&x<&&y<)

                     {

                         v.map[i][j]=v.map[x][y];

                         v.map[x][y]=;

                         v.step=u.step+;

                         int tmp=,t=,k=;

                         for(int i=; i<; ++i)

                           for(int j=; j<; ++j)

                             tmp+=k*v.map[i][j],t++,k*=t;

                         if(!vis[tmp])

                             vis[tmp]=,que.push(v);

                         v=u;

                     }

                 }

                 goto STEP;

             }

         STEP:;

     }

     return ;

 }

 int Presist()

 {

     scanf("%s",s);

     for(int i=; i<; ++i) u.map[][i]=s[i]-'';

     for(int i=; i<; ++i) u.map[][i%]=s[i]-'';

     for(int i=; i<; ++i) u.map[][i%]=s[i]-'';

     printf("%d\n",BFS());

     return ;

 }

 int Aptal=Presist();

 int main(){;}