lcBFS1

Posted on Edited on

1 BFS

最关键的是：
- bfs本身的特性，一个是按照层数往下遍历，一个是可以决定是否遍历完当前层再往下遍历
- bfs的队列初始化即为bfs的搜索起点，然后注意状态问题，当每个节点带有状态以后，bfs的visited变量就不仅仅是node的编号，应该是node的编号 + “当前状态”，具体参考(0864,0847)
- 注意：遍历当前层，需要把size记录成临时变量，因为curLevel会加入新元素
- 注意：入队后就需要置为visited，否则可能重复入队

bfs的遍历本质上可以看成当前点，到所有后继节点的可能跳转的状态。(0733例题)

bfs的核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int bfsCheck(vector<vector<int>>& oriBoard) {
        queue<vector<vector<int>>> curLevel;
        curLevel.push(oriBoard);
        vis.insert(toInt(oriBoard));

        int depth = 1;
        while(!curLevel.empty()) {
            int curSize = curLevel.size();
            // pop all curLevel and do next level
            while(curSize-- > 0) { // 最关键的，一定不要直接写成curLevel.size，因为curLevel会放后面的节点的呜呜呜
                auto board = curLevel.front();
                curLevel.pop();

                auto coord = getPos(board);
                int x = coord.first;
                int y = coord.second;
            
                for(int mv = 0; mv < 4; ++mv) {
                    int nextX = x + dx[mv];
                    int nextY = y + dy[mv];
                    if(0 <= nextX && nextX < 2 && 0 <= nextY && nextY < 3) {
                        swap(board[nextX][nextY], board[x][y]);
                        // cout << "trying : " << x << ", " << y << " to " << nextX << ", " << nextY << " withd d = " << depth <<endl;
                        // print(board);
                        
                        int intBoard = toInt(board);

                        if(0 == vis.count(intBoard)) {
                            curLevel.push(board);
                            if(isTar(board)) {
                                // cout << "final tar: " << endl;
                                // print(board);
                                return depth;
                            }
                            vis.insert(intBoard);
                        }
                        swap(board[x][y], board[nextX][nextY]);
                    }
                }
            }
            ++depth;
        }

2 例题

0733slidingPuzzle 滑动到123450谜题

1 题目

https://leetcode.cn/problems/sliding-puzzle/

2 解题思路

  • 1 解题思路：
    • 1.1 为何选用bfs，因为要获得最终的移动步数，那么bfs的层数就是最终的答案
    • 1.2 节点就是当前的棋盘，后继节点为移动后改变的棋盘
    • 1.3 使用位运算加速
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class Solution {
public:
    constexpr static int tar = ((1<<3) | (2<<6) | (3<<9) | (4<<12) | (5<<15));
    unordered_set<int> vis;

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

    bool isTar(vector<vector<int>>& board) {
        return tar == toInt(board);
    }
    int toInt(vector<vector<int>>& board) {
        return board[0][0]<<3 | board[0][1]<<6 | board[0][2]<<9 | board[1][0]<<12 | board[1][1]<<15;
    }

    pair<int, int> getPos(vector<vector<int>>& board) {
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 3; ++j) {
                if(board[i][j] == 0) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }

    int slidingPuzzle(vector<vector<int>>& board) {
        int res = 0;
        if(toInt(board) == tar) {
            return 0;
        }
    
        res = bfsCheck(board);
        return res;
    }

    void swap(int& a, int& b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    int bfsCheck(vector<vector<int>>& oriBoard) {
        queue<vector<vector<int>>> curLevel;
        curLevel.push(oriBoard);
        vis.insert(toInt(oriBoard));

        int depth = 1;
        while(!curLevel.empty()) {
            int curSize = curLevel.size();
            // pop all curLevel and do next level
            while(curSize-- > 0) {
                auto board = curLevel.front();
                curLevel.pop();

                auto coord = getPos(board);
                int x = coord.first;
                int y = coord.second;
            
                for(int mv = 0; mv < 4; ++mv) {
                    int nextX = x + dx[mv];
                    int nextY = y + dy[mv];
                    if(0 <= nextX && nextX < 2 && 0 <= nextY && nextY < 3) {
                        swap(board[nextX][nextY], board[x][y]);
                        // cout << "trying : " << x << ", " << y << " to " << nextX << ", " << nextY << " withd d = " << depth <<endl;
                        // print(board);
                        
                        int intBoard = toInt(board);

                        if(0 == vis.count(intBoard)) {
                            curLevel.push(board);
                            if(isTar(board)) {
                                // cout << "final tar: " << endl;
                                // print(board);
                                return depth;
                            }
                            vis.insert(intBoard);
                        }
                        swap(board[x][y], board[nextX][nextY]);
                    }
                }
            }
            ++depth;
        }
        return -1;

    }

    void print(vector<vector<int>>& board) {
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 3; ++j) {
                cout << board[i][j] << " ";
            }cout << " | ";
        }
        cout << "----------\n";
    }

};

0675golfCutTree 高尔夫砍树

1 题目

https://leetcode.cn/problems/cut-off-trees-for-golf-event/

2 解题思路

  • 1 解题思路：
    • 1.1 使用优先队列将所有树从小到高排序，存为trees
    • 1.2 每次从trees中取出一个树，对其进行bfs直到找到trees的下一个目标
  • 2 bfs思路：
    • 2.1 queue初始化为起点
    • 2.2 对于queue中所有元素，加入当前queue的所有后继，加入以后就把元素置为visited
    • 2.3 进入下一个level
  • 3 为什么加入的过程中就要吧元素置为vis？因为：假设1层有a,b, 2层有c，c为ab的邻居，那么遍历第1层的时候，对于ab的后继，到a，加入c，若不置为vis，则b会再加入一遍，导致bfs很慢！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
class Solution {
public:
    int m;
    int n;
    
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, -1, 0, 1};
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    int cutOffTree(vector<vector<int>>& forest) {
        // get all trees
        m = forest.size();
        n = forest[0].size();

        auto cmp = [](const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) {
            return a.second > b.second;
        };
        priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, decltype(cmp)>trees (cmp);

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(forest[i][j] > 1) {
                    trees.push({{i, j}, forest[i][j]});
                }
            }
        }


        int curX = 0, curY = 0;
        int tarX = -1, tarY = -1;
        int res = 0;
        while(!trees.empty()) {
            auto tree = trees.top();
            trees.pop();

            tarX = tree.first.first;
            tarY = tree.first.second;
            
            // judge if we can walk to x, y
            // cout << "from/to: " << curX << "," << curY << " -> " << tarX << "," << tarY << endl; 
            if(!tryWalk(forest, curX, curY, tarX, tarY, res)) {
                return -1;
            } else {
                // cut tarX, tarY
                forest[tarX][tarY] = 1;
                curX = tarX;
                curY = tarY;
            }
            // auto step = bfs(forest, curX, curY, tarX, tarY);
            // if(-1 == step) {
            //     return -1;
            // } else {
            //     // cut tarX, tarY
            //     forest[tarX][tarY] = 1;
            //     res+= step;
            //     curX = tarX;
            //     curY = tarY;
            // }
        }

        return res;
    }

    int bfs(vector<vector<int>>& forest, int sx, int sy, int tx, int ty) {
    if (sx == tx && sy == ty) {
        return 0;
    }

    int row = forest.size();
    int col = forest[0].size();
    int step = 0;
    queue<pair<int, int>> qu;
    vector<vector<bool>> visited(row, vector<bool>(col, false));         
    qu.emplace(sx, sy);
    visited[sx][sy] = true;
    while (!qu.empty()) {
        step++;
        int sz = qu.size();
        for (int i = 0; i < sz; ++i) {
            auto [cx, cy] = qu.front();
            qu.pop();
            for (int j = 0; j < 4; ++j) {
                int nx = cx + dirs[j][0];
                int ny = cy + dirs[j][1];
                if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
                    if (!visited[nx][ny] && forest[nx][ny] > 0) {
                        if (nx == tx && ny == ty) {
                            return step;
                        }
                        qu.emplace(nx, ny);
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }
    return -1;
}


    // using bfs from <curX, curY> to <tarX, tarY>, the depth of bfs should be the distance
    bool tryWalk(vector<vector<int>>& forest, int curX, int curY, int tarX, int tarY, int& res) {
        // bfs
        queue<pair<int, int>> curLevel;
        vector<vector<int>> vis(m, vector<int>(n, false));
        
        curLevel.push({curX, curY});
        vis[curX][curY] = true;

        int depth = 0;
        while(!curLevel.empty()) {
            // queue<pair<int, int>> nextLevel;

            // while(!curLevel.empty()) {
            int curLevelSize = curLevel.size();
            while(curLevelSize-- > 0) {
                auto curNode = curLevel.front();

                curLevel.pop();
                if(curNode == pair<int, int>{tarX, tarY}) {
                    // update res
                    res += depth;
                    return true;
                }
                for(int mv = 0; mv < 4; ++mv) {
                    int nextX = curNode.first + dx[mv];
                    int nextY = curNode.second + dy[mv];

                    if(0 <= nextX && nextX < m && 0 <= nextY && nextY < n && 0 != forest[nextX][nextY] && !vis[nextX][nextY]) {
                        curLevel.push({nextX, nextY});
                        vis[nextX][nextY] = true;
                        // cout << "nextNode: " << curNode.first << "," << curNode.second << endl; 
                    }
                }
            }
            // curLevel = std::move(nextLevel);
            ++depth;
        }
        return false;
    }
};

0847allTravelShortestPath 访问所有节点最短路径

1 题目

https://leetcode.cn/problems/shortest-path-visiting-all-nodes/

2 解题思路

  • 1 解题思路：
    • 1.1 使用三元组 <u, mask, dist>表示，当前节点u的mask的搜索情况对应的搜索距离dist，调用bfs即可，但是对于下一个v，我们需要检测： v节点的1 << v | mask这种访问情况是否被访问过
    • 1.2 如何考虑这个方法？
      • 1.2.1 初始化的时候所有节点都加入队里（认为可以从每个节点出发）
      • 1.2.2 bfs的具体过程中，退出条件就是 队首的mask是否标记了所有节点都被访问
    • 1.3 这个方法为什么可以？
      • 一句话：这个方法：利用bfs，按照路径长度从小到大遍历了所有的可能路径（队列初始化有所有的顶点就是这个意思），比如初始化，就是说将长度为0的所有可能路径遍历完成，然后下一层bfs会将所有长度为1的可能路径遍历完成，这个路径的记录方式为mask以及mask对应的终点u，那么由于路径长度是从小到大去遍历的，那么必然保证最终答案是最短路径，
      • 假设用dfs做，那么dfs要考虑所有路径可能，然后去比较，那么会出现枚举的情况，然鹅bfs不会，因为省去所有长度比最短路径大的路径
  • 2 总结一下：最关键的有两点
    • 2.1 利用bfs能够将遍历路径的长度从小到大遍历的特性
    • 2.2 使用<到达点，已经遍历的点，目前长度>来记录所有的遍历情况这个trick很聪明
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 这里看一个具体 
[[1,2,3],[0],[0],[0]]

// 具体的遍历顺序为：
// 遍历到达的节点 目前遍历的节点 遍历路径的长度
0 00000001 0
1 00000010 0
2 00000100 0
3 00001000 0
1 00000011 1
2 00000101 1
3 00001001 1
0 00000011 1
0 00000101 1
0 00001001 1
2 00000111 2
3 00001011 2
1 00000111 2
3 00001101 2
1 00001011 2
2 00001101 2
0 00000111 3
0 00001011 3
0 00001101 3
3 00001111 4
3 00001111 4


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        queue<tuple<int, int, int>> curLevel;
        int n = graph.size();
        vector<vector<bool>> seen(n, vector<bool>(1 << n));

        for(int i = 0; i < n; ++i) {
            curLevel.emplace(i, 1 << i, 0);
            seen[i][1 << i] = true;
        }

        while(!curLevel.empty()) {
            auto [node, mask, dist] = curLevel.front();
            // printf("%d %x", node, mask);
            // cout << dist << endl;
            curLevel.pop();
            
            // << not priority to -
            if(mask == (1 << n) - 1) {
                return dist;
            }
            
            for(auto neighbor : graph[node]) {
                int newMask = mask | 1 << neighbor;
                if(!seen[neighbor][newMask]) {
                    curLevel.emplace(neighbor, newMask, dist + 1);
                    seen[neighbor][newMask] = true;
                }
            }
        }

        return -1;
    }
};

0864getAllKeys 获取所有钥匙的最短路径

1 题目

https://leetcode.cn/problems/shortest-path-to-get-all-keys/submissions/

2 解题思路

  • 1 解题思路：
    • 1.1 首先考虑使用bfs,因为从起点到终点，bfs的遍历深度就等于最短路径，那么有一个问题对于：[“@a.”,”bAB”]这样的地图如何知道经过a和b的最短路呢？
    • 1.2 也就是这个bfs会走”回头路”，但是又不是完全的回头路，因为走路的人的状态发生了变化，也就是手里多了钥匙，也就是bfs的变种：带状态(压缩)的bfs
    • 1.3 那么就很容易想到，原来最普通的bfs判断是否走过就是只用了位置xy，那么现在我们多增加一个信息，也就是拥有的钥匙，那么该点没有走过变成了什么呢？那就是：该点位置没有走过，或者当前的拥有钥匙的状态在该点没有出现过
    • 1.4 有了1.3我们就很容易知道，用什么数据结构去存顶点是否被访问啦： map<pair<int, int>, set> seenKey; 左边是该点的位置，右边是该点所经历过的所有钥匙的集合
    • 1.5 还需要考虑如何记录路径长度：map<pair<pair<int, int>, int>, int> dis; 很显然，左侧是<xy,key>，右侧代表了xy在key情况下的路径长度
    • 1.6 考虑一个具体[“@a.”,”bAB”]的例子即可：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      cur: 0,0 -> 000000
      next: 0,1 charis a-> 000001
      next: 1,0 charis b-> 000010
      cur: 0,1 -> 000001
      next: 0,2 charis .-> 000001
      next: 1,1 charis A-> 000001
      next: 0,0 charis @-> 000001
      cur: 1,0 -> 000010
      next: 0,0 charis @-> 000010
      cur: 0,2 -> 000001
      cur: 1,1 -> 000001
      next: 1,0 charis b-> 000011
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class Solution {
public:

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

    int shortestPathAllKeys(vector<string>& grid) {
        m = grid.size();
        n = grid[0].size();
        int i = 0;
        int j = 0;
        int keyNum = 0;
        int stX = -1, stY = -1;
        for(auto& s : grid) {
            j = 0;
            for(auto& c : s) {
                if('a' <= c && c <= 'f') {
                    ++keyNum;
                }
                if('@' == c) {
                    stX = i;
                    stY = j;
                }
                ++j;
            }
            ++i;
        }
        
        int tarKey = 0;
        for(int i = 0; i < keyNum; ++i) {
            tarKey = tarKey | (1 << i);
        };

        // cout << "tarKey is : " << bitset<8>(tarKey) << " | st: " << stX << " " << stY << endl;
        return bfs(grid, stX, stY, tarKey);
    }

    bool canWalk(vector<string>& grid, int x, int y, int keyInfo) {
        if('A' <= grid[x][y] && grid[x][y] <= 'F') {
            int keyNum = grid[x][y] - 'A';
            return ((keyInfo >> keyNum) & 1) != 0;
        } 
        if('#' == grid[x][y]) {
            return false;
        }

        return true;
    }

    int bfs(vector<string>& grid, int stX, int stY, int tarKey) {
        queue<pair<pair<int, int>, int>> curLevel; // xy, key
        curLevel.push({{stX, stY}, 0});
        map<pair<pair<int, int>, int>, int> dis; // xy, key -> pathLen
        map<pair<int, int>, set<int>> seenKey; // xy -> key
        dis[{{stX, stY}, 0}] = 0;
        seenKey[{stX, stY}] = {0};

        int res = 0;

        while(!curLevel.empty()) {
            int curSize = curLevel.size();
            while(curSize-- > 0) {
                auto curNode = curLevel.front();
                int curDis = dis[curNode];
                int x = curNode.first.first;
                int y = curNode.first.second;
                int curKey = curNode.second;

                curLevel.pop();
                // cout << "cur: " << x << "," << y << " -> " << bitset<6>(curKey) << endl;
                for(int mv = 0; mv < 4; ++mv) {
                    int nextX = x + dx[mv];
                    int nextY = y + dy[mv];
                    pair<int, int> nextNode = {nextX, nextY};
                    // nextNode not explored or has new keys
                    if(0 <= nextX && nextX < m && 0 <= nextY && nextY < n && \
                         canWalk(grid, nextX, nextY, curKey) && \
                        (0 == seenKey.count(nextNode) || 0 == seenKey[nextNode].count(curKey))) {
                        int nextKey = curKey;
                        if('a' <= grid[nextX][nextY] && grid[nextX][nextY] <= 'f') {
                            nextKey = curKey | (0x1 << (grid[nextX][nextY] - 'a'));
                        }
                        
                        curLevel.push({{nextX, nextY}, nextKey});
                        seenKey[{nextX, nextY}].insert(nextKey);
                        dis[{nextNode, nextKey}] = dis[curNode] + 1;
                        
                        // cout << "next: " << nextX << "," << nextY << " charis "<< grid[nextX][nextY] << "-> " << bitset<6>(nextKey) << endl;
                        if(nextKey == tarKey) {
                            return dis[curNode] + 1;
                        }
                    }
                }
            }
        }
        return -1;
    }
};