跳蚱蜢问题

蚱蜢问题"/>

跳蚱蜢问题

#include<bits/stdc++.h>
using namespace std;
string st = "123456780", ed = "876543210";
int dx[] = {1,-1,2,-2};
int n = 9;int bfs(){unordered_map <string, int> dist; // dist[str] 存的是 从st到str的最短距离dist[st] = 0;queue<string> q;q.push(st);while(q.size()){//auto 自动识别类型//front拿到队列组前面的元素 auto t = q.front(); //可以发现这里t为string类型 q.pop();//k空盘的位置 int k = t.find('0');//遍历四个方向 for(int i = 0; i < 4; i++){string str = t;swap(str[k],str[(k + dx[i] + n) % n]);if(dist.count(str)) continue;dist[str] = dist[t] + 1;if(str==ed) return dist[str];q.push(str);} }return -1 ;
} int main(){cout<<bfs()<<endl;return 0;
}