题目描述
bfs
这道题目使用bfs搜索,按照不同的分支来进行查找,分4个方向,但是一开始我陷入了题目中的“至少”,想成一个最优的问题。其实这道题目可以转成把一个字符移动到另外一个位置的最短移动次数问题。
两个难点:1、状态的表示;2、状态的转移;
思考:用dfs是否能够解出来?
备注:我觉得的难点,1、不知道用string来表示起点,2、bfs结合一个map使用,这个求最短距离,我想成了使用一个变量去记录;
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int bfs(string start){
string end = "12345678x";
queue<string> q;
unordered_map<string, int> d;
q.push(start);
d[start] = 0;
while(q.size()){
string t = q.front();
q.pop();
int distance = d[t];
if (t == end){
return distance;
}
int k = t.find('x'); // x下标的位置
int x = k / 3, y = k % 3;
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)){
d[t] = distance + 1;
q.push(t);
}
swap(t[k], t[a*3 + b]);
}
}
}
return -1;
}
int main(){
string s;
for (int i = 0; i < 9; i ++){
char c;
cin >> c;
s += c;
}
cout << bfs(s) << endl;
return 0;
}