#|最小步数问题(BFS) bfs|最小步数问题|最短路|算法

文章目录

- 引入
- AcWing 845. 八数码
- AcWing 1107. 魔板

引入最小步数问题也是通过bfs求最短路的问题。
但之前我们遇到的bfs求最短路都是只有一张图，所有状态都在一个图内，例如走迷宫问题。BFS应用——走迷宫
而最小步数问题的每个状态都分别对应一张图。
那么怎样表示这些状态就是一个难点。通常我们会借用哈希表来表示状态。
AcWing 845. 八数码

文章图片

补充一个小技巧：
设元素x在一维数组的下标为index，二维数组的下标为(row,col)，（ps：已知二维数组长度为n * m）
一维数组转换为二维数组的下标
row = index / m
col = index % m
二维数组转换为一维数组的下标
index = col + row * m
(可以发现，下标转换过程中只与列数m有关，与行数n无关)

#include #include #include #include using namespace std; int dx[4] = {0,-1,0,1}, dy[4] = {-1,0,1,0}; int bfs(string start) { string end = "12345678x"; //终点状态 queue> q; unordered_map,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 在字符串t中的下标 int x = k / 3, y = k % 3; //将 x 的一维数组的下标转换为3X3的二维数组下标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]); //将x与这个数进行交换(在一维字符串数组中交换)if(!d.count(t)) //新状态没有被搜过，更新距离并加入队列 { d[t] = distance + 1; q.push(t); } swap(t[k], t[a * 3 + b]); //恢复状态 } } } return -1; }int main() { string start; //初始状态 for(int i=0; i<9; i++) { char c; cin >> c; start += c; } cout << bfs(start) << endl; }

AcWing 1107. 魔板 【#|最小步数问题(BFS)】

文章图片

#include #include #include #include #includeusing namespace std; unordered_map,int> d; //最小步数数组 unordered_map,pair> pre; //记录每个状态是由哪个状态转移的 queue> q; char g[2][4]; void set(string state) //将字符串按顺时针放回g数组中 { for(int i=0; i<4; i++) g[0][i] = state[i]; for(int i=3,j=4; i>=0; i--,j++) g[1][i] = state[j]; } string get() //将g数组中字符按顺时针变成字符串 { string res; for(int i=0; i<4; i++) res += g[0][i]; for(int i=3; i>=0; i--) res += g[1][i]; return res; }string move0(string state) //A操作 { set(state); for(int i=0; i<4; i++) swap(g[0][i],g[1][i]); return get(); }string move1(string state) //B操作 { set(state); char v0 = g[0][3], v1 = g[1][3]; //将最后一列保存下来 for(int i=3; i>0; i--) //将前三列向右移 { g[0][i] = g[0][i-1]; g[1][i] = g[1][i-1]; } g[0][0] = v0, g[1][0] = v1; //将最后一列赋到第一列上 return get(); }string move2(string state) //C操作 { set(state); char v = g[0][1]; //将左上角存下来 g[0][1] = g[1][1]; g[1][1] = g[1][2]; g[1][2] = g[0][2]; g[0][2] = v; return get(); }void bfs(string start,string end) { q.push(start); d[start] = 0; while(q.size()) { string t = q.front(); q.pop(); string m[3]; //A、B、C三种操作后得到的字符串 m[0] = move0(t); //A操作 m[1] = move1(t); //B操作 m[2] = move2(t); //C操作for(int i=0; i<3; i++) { string s = m[i]; //某个操作后的字符串 if(!d.count(s)) //没有被搜过 { d[s] = d[t] + 1; //更新距离 pre[s] = {char(i+'A'),t}; if(s == end) break; q.push(s); } } } }int main() { int x; string start,end; //初始状态、终点状态 for(int i=0; i<8; i++) { cin >> x; end += char(x + '0'); } for(int i=0; i<8; i++) start += char(i + '1'); bfs(start,end); cout << d[end] << endl; string res; while(end != start) { res += pre[end].first; end = pre[end].second; //将end更新为上一个状态 } reverse(res.begin(),res.end()); //头文件algorithm if(res.size()) cout << res; }