题目

思路

• 可以将不同的状态视作不同的节点，想要求最短的操作路径，那么显然BFS是首先想到的。
• 一开始的写的一版代码太过繁琐了，可以直接用一个string来保存每个状态，交换的话，可以上下左右分别遍历，然后判断是否合法即可，之前的想法太繁琐了。简单一点就行。
• 可以用哈希表或者红黑树保存状态，同时避免重复操作。
• 在出队列的时候进行判断。

  代码

  ```cpp

  include

  include

  include

  include

  include

using namespace std;

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int bfs(string start) { string end = “12345678x”; queue q; q.push(start); unordered_map d; d[start] = 0;

while (!q.empty()) {
    string cur = q.front();
    q.pop();
    int distance = d[cur];
    if (cur == end) {
        return distance;
    }
    int k = cur.find('x');
    for (int i = 0; i < 4; i++) {
        int x = k / 3 + dx[i];
        int y = k % 3 + dy[i];
        if (x >= 0 && x < 3 && y >= 0 && y < 3) {
            swap(cur[k], cur[3 * x + y]);
            if (!d.count(cur)) {
                d[cur] = distance + 1;
                q.push(cur);
            }
            swap(cur[k], cur[3 * x + y]);
        }
    }        
}
return -1;

}

int main() { string start; for (int i = 0; i < 9 ;i++) { char c; cin >> c; start += c; }

cout << bfs(start) << endl;
return 0;

} ```