[蓝桥杯][历届试题]九宫重排（BFS+哈希）

 [蓝桥杯][历届试题]九宫重排

时间限制: 1Sec 内存限制: 128MB 提交: 586 解决: 126

题目描述

如下面第一个图的九宫格中，放着  1~8  的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

 

我们把第一个图的局面记为：12345678. 
把第二个图的局面记为：123.46758 
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。 
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入

输入第一行包含九宫的初态，第二行包含九宫的终态。 

输出

输出最少的步数，如果不存在方案，则输出-1。

样例输入

   

    

     

      

     
     

      

       12345678. 
      
     
    

     

      

     
     

      

       123.46758 
      
     
   
  

样例输出

3

  

提示

思路：

 把此类问题看成 寻最短路径问题，相当于空白格相当于起点，然后找到空白格从开始图的位置到最后目标图的位置且图中数字   相同的最小步数。 

 寻找最小步数 ，可以用BFS来实现，涉及到状态压缩 和 查重  这里我们可以借助一个map映射

（将字符状态映射为一个int型的整数  比如 12345678. ----> 98 别管这个值怎么来的 反正 每个状态 可以映射为唯一的一个整数值）来标记是否这个界面已经被访问过。或则自己写一个哈希来存状态。


 AC代码：

  

   

    

     

    
    

     

      #include<iostream> 
     
    
   

    

     

    
    

     

      #include<string.h> 
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      char start[4][4],goal[4][4];
     
    
   

    

     

    
    

     

      int df[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
     
    
   

    

     

    
    

     

      map<string,int> vis;
     
    
   

    

     

    
    

     

      struct Node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int x,y;
     
    
   

    

     

    
    

     
    long long step;
     
    
   

    

     

    
    

     
    char Map[4][4];
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     

      bool check_g(Node a)///判断这个图和目标图是否相同
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
      if(a.Map[i][j]!=goal[i][j])return false;
     
    
   

    

     

    
    

     
    return true;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool check_cf(Node a)///判断这个局面是否出现过
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          string s = "";
     
    
   

    

     

    
    

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

    

     

    
    

     
     for(int j=1;j<=3;j++)s+=a.Map[i][j];
     
    
   

    

     

    
    

     
    if(vis[s]>0)return false;
     
    
   

    

     

    
    

     

          vis[s]++;
     
    
   

    

     

    
    

     
    return true;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int BFS(int x1,int y1)///BFS寻找最少步数
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          Node cur,next;
     
    
   

    

     

    
    

     

          cur.x = x1;cur.y = y1;
     
    
   

    

     

    
    

     

          cur.step = 0;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

              cur.Map[i][j] = start[i][j];//复制一份状态
     
    
   

    

     

    
    

     

          queue<Node> Q;//创建一个队列
     
    
   

    

     

    
    

     

          Q.push(cur); //加入队列
     
    
   

    

     

    
    

     
    if(check_g(cur)) return cur.step;//检查是否为目标状态
     
    
   

    

     

    
    

     
    while(!Q.empty()){
     
    
   

    

     

    
    

     

              cur = Q.front();
     
    
   

    

     

    
    

     

              Q.pop();    // 出队列
     
    
   

    

     

    
    

     
        for(int i=0;i<4;i++){
     
    
   

    

     

    
    

     

                  next.x = cur.x + df[i][0];
     
    
   

    

     

    
    

     

                  next.y = cur.y + df[i][1];
     
    
   

    

     

    
    

     
             for(int i1=1;i1<=3;i1++)
     
    
   

    

     

    
    

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

    

     

    
    

     

                     next.Map[i1][j]= cur.Map[i1][j];//复制一份状态
     
    
   

    

     

    
    

     

                  next.step = cur.step + 1;//当前 步数加一
     
    
   

    

     

    
    

     
            if(next.x>=1&&next.x<=3&&next.y>=1&&next.y<=3){//边界内
     
    
   

    

     

    
    

     
                swap(next.Map[next.x][next.y],next.Map[cur.x][cur.y]);///交换两个方格的位置；
     
    
   

    

     

    
    

     
                if(check_cf(next)){//检查重复
     
    
   

    

     

    
    

     
                    if(check_g(next)) return next.step;//检查是否为目标状态
     
    
   

    

     

    
    

     

                         Q.push(next);//入队列
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return -1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int x1,y1;
     
    
   

    

     

    
    

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

    

     

    
    

     
      for(int j=1;j<=3;j++){
     
    
   

    

     

    
    

     

                  cin>>start[i][j];
     
    
   

    

     

    
    

     
            if(start[i][j]=='.') x1=i,y1=j;///记录空白格的位置
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

                  cin>>goal[i][j];
     
    
   

    

     

    
    

     

          cout<<BFS(x1,y1)<<endl;
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

 
题目链接：https://www.dotcpp.com/oj/problem1426.html

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/86649189