思路:数据量小的题首先往暴搜想,这题要算最小步数,所以用bfs暴搜。如果要算所有方案数之类的才用dfs暴搜。
#include <iostream>
#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"; //定义终点状态
if (start == end) return 0;
queue<string> q;
q.push(start);
unordered_map<string, int> d;
d[start] = 0;
while (q.size())
{
auto t = q.front();
q.pop();
int x, y;
for (int i = 0; i < 9; i ++ )
if (t[i] == 'x')
x = i / 3, y = i % 3; //找出x的坐标
for (int i = 0; i < 4; i ++ ) //用偏移量走格子
{
string state = t; //用一个新字符串来更新t的下一个状态
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3)
{
swap(state[x * 3 + y], state[a * 3 + b]);
if (d.count(state) == 0) //判断该状态是否到达过
{
d[state] = d[t] + 1;
if (state == end) return d[state];
q.push(state);
}
}
}
}
return -1;
}
int main()
{
string start, state; //start储存八数码,state用于计算逆序对
char c;
while (cin >> c)
{
start += c;
if (c != 'x') state += c;
}
int cnt = 0; //八数码隐藏性质:当数队中逆序对数量为奇数时无解
for (int i = 0; i < 8; i ++ ) //上结论只对3X3的八数码或类似的奇数X奇数 数码有效
for (int j = i + 1; j < 8; j ++ ) //例如对4X4数码无效,对5X5数码有效...
if (state[i] > state[j])
cnt ++ ;
if (cnt % 2) puts("-1"); //奇数直接无解,偶数再bfs,节省了计算量
else cout << bfs(start) << endl;
return 0;
}