算法基础之八数码

八数码

• 核心思想：BFS

  • 将矩阵展开成字符串 寻找 目标字符串”12345678x”

  •   #include <iostream>
      #include <algorithm>
      #include <unordered_map>
      #include <queue>
      
      using namespace std;
      
      int bfs(string start){
          
          string end = "12345678x";  //目标字符串
          queue<string> q;  //遍历到的字符串(状态)
          unordered_map<string,int> d;  //根据字符串(状态)查距离
          q.push(start);  
          d[start] = 0;    //初始化
          int dx[4] = {1,0,-1,0},dy[4] = {0,-1,0,1};
          
          while(q.size()){
              auto t = q.front();
              q.pop(); 
              if(t==end) return d[t];  //终止条件
              
              int distance = d[t];  //当前距离
              int k=t.find('x');  //找到x的下标
              int x=k/3,y=k%3;  //将x从字符串的下标 转成 矩阵的xy坐标
              for(int i=0;i<4;i++){
                  int a = x+dx[i],b = y+dy[i];  //移动四个方向
                  if(a>=0&&a<3&&b>=0&&b<3){  //可交换
                      swap(t[k],t[a*3+b]);  //交换
                      if(!d.count(t)){  //找t 如果没有返回0
                          d[t] = distance +1;  //更新距离
                          q.push(t);  //加入队列
                      }
                      swap(t[k],t[a*3+b]);  //复原
                  }
              }
          }
          return -1;
      }
      
      int main(){
          char s[2];
          
          //将字符存成字符串
          string start;
          for(int i=0;i<9;i++){
              cin>>s;
              start += *s;
          }
          
          cout<<bfs(start)<<endl;
          
          return 0;
      }