【codevs1225】八数码难题

problem

solution

codes

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
using namespace std;
const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
string goal = "123804765", s;
map<string,int>ma;
int main(){
    cin>>s;
    queue<string>q;
    q.push(s);
    while(!q.empty()){
        string t = q.front();  q.pop();
        if(t == goal)break;
        int z;
        for(z = 0; z < 9; z++)
            if(t[z]=='0')break;
        int x=z/3, y=z%3;
        for(int i = 0; i < 4; i++){
            int nx=x+dx[i], ny=y+dy[i], nz=nx*3+ny;
            if(nx<0||nx>=3||ny<0||ny>=3)continue;
            string tt = t;
            swap(tt[z],tt[nz]);
            if(!ma.count(tt)){
                q.push(tt);
                ma[tt] = ma[t]+1;
            }
        }
    }
    cout<<ma[goal]<<"\n";
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80472780