一维数组下标转二位数组下标
//一维数组种下标k转化为n行m列的数组的下标变化 A[k]=B[k/n][k%m]; //逻辑上的转换,二维数数组本质上还是在内存种连续存储的 //此操作可以不转化一维数组为二维数组,对数组进行二维逻辑上的操作
//队列先进先出,队列前面的元素比后面元素的d值要小,所以第一次出现t==end时d[t]值就是最短路 #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<unordered_map> using namespace std; const int N = 1e2 + 10; typedef pair<int, int>PII; int n, m; queue<string>q; unordered_map<string, int>d; int bfs(string start) { string end = "12345678x"; int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };//上下左右四个bfs方向 q.push(start); d[start] = 0; while (q.size()) { auto t = q.front(); q.pop(); int distance = d[t]; if (t == end)return distance; int k = t.find('x');//找到x的下标 int a = k / 3, b = k % 3; for (int i = 0; i < 4; i++) { int x = a + dx[i], y = b + dy[i];//转化为二维坐标以便判断是否越界 if (x >= 0 && x < 3 && y >= 0 && y >= 0 && y < 3) { swap(t[k], t[x * 3 + y]);//交换两个字符,产生一个状态 if (!d.count(t))//如果该状态第一次出现 { d[t] = distance + 1;//原状态变成新状态路径加一 q.push(t);//将新状态入队 } swap(t[k], t[x * 3 + y]);//恢复原状态,来向其他方向进行bfs } } } return -1; } int main() { string start; char c; for (int i = 0; i <9; i++) { cin >> c; start += c; } cout << bfs(start) << endl; return 0; }