第三章：如何用 BFS 算法秒杀各种智力题

labuladong 如何用 BFS 算法秒杀各种智力题

BFS是一种“齐头并进”遍历树的方式

• 要用到队列。在while的for循环中，把当前队头pop出去。若找到目标了，则return。若没有找到，则把队头对应的相邻节点（如果这个相邻节点之前没有被访问）加进队列中

773. 滑动谜题

• 相当于一棵树。每次0的移动会产生新的状态
• 用一个set集合记录节点是否曾被visited
• 相邻索引记录的是：每个格子相邻的格子序号 （而不是具体某一个数字对应的相邻数字序号），因此不管格子怎么变，这个neighbor索引向量都不变

// #include <vector>
// #include <set>
// #include <unordered_set>
// #include <queue>
// #include <string>
// #include <algorithm>
// using namespace std;

class Solution {
public:
    int slidingPuzzle(vector <vector<int>> &board) {
        int m = 2, n = 3;
        string start;
        string target = "123450";
//        将当前数组转成字符串
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                start += to_string(board[i][j]);
            }
        }

//        位置对应的索引
        vector <vector<int>> neighbor = {
                {1, 3},
                {0, 4, 2},
                {1, 5},
                {0, 4},
                {3, 1, 5},
                {4, 2}
        };

        queue <string> q;
        unordered_set <string> visited;
//        队列和visited中插入初始状态
        q.push(start);
        visited.insert(start);

        int step = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                string cur = q.front();
                q.pop();

                if (cur == target) return step;// 如果找到了，则返回

                // // 找到数字 0 的索引
                int idx = find(cur.begin(), cur.end(), '0') - cur.begin();
                for (int adj : neighbor[idx]) {
                    //这里一定要创建一个临时的string，使同一批tmp都对应相同的cur，下面tmp的改变不会影响cur
                    string tmp = cur; 
                    swap(tmp[adj], tmp[idx]);
//                    若没被访问，则添加
                    if (!visited.count(tmp)) {
                        q.push(tmp);
                        visited.insert(tmp);
                    }
                }
            }
            step+=1; // 如果这一批for循环没找到，则步数+1，继续找
        }
        return -1;
    }
};