【bfs】AcWing 845. 八数码(求最短步数)
y总思考过程:
这个状态是矩阵的形式,非常的不好存;
这里的“存”指的是:
- bfs里的queue<>q的下标
- 转移的时候dis数组的下标
- 我们还要快速判断一个状态是否出现过
->
把状态压缩成字符串
用unordered_map来存字符串下标,记录转移了多少次。
最妙的一点 :把状态压缩成字符串来转移,
每次转移’x’的位置,我们判断这个状态有没有到达过,可以用unordered_map的count()函数
- 矩阵内坐标转字符串:(在按0开始存的情况下)map[i] [j]=string[i*n+j];
- 字符串转矩阵内坐标:(在按0开始存的情况下)string[i]->map[i/n] [i%n];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
string start;
string ed="12345678x";
unordered_map<string,int>dis;
queue<string>q;
inline int bfs(){
q.push(start);
dis[start]=0;
while(!q.empty()){
string u=q.front();q.pop();
if(u==ed)return dis[u];
int k=u.find('x');
int x=k/3;
int y=k%3;
rep(i,1,4){
int xx=x+dx[i],yy=y+dy[i];
string v=u;//v存下一个状态的字符串
if(xx>=0 && xx<3 && yy>=0 && yy<3){
swap(v[k],v[xx*3+yy]);
if(!dis.count(v)){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
}
return -1;
}
int main(){
rep(i,1,9){
char c;cin>>c;
start+=c;
}
printf("%d\n",bfs());
return 0;
}