一类特殊的BFS

通常来说，BFS模版如下：

q = new Queue()
seen = new HashSet()
q.add(start)
seen.add(start)
steps = 0
while not q.empty():
    size = q.size()
    while size-- > 0:
        state = q.pop()
       if is_goal(state) : return steps
       for new_state in expand(state):
           if not valid(new_state) or seen.contains(new_state):
               continue
           q.add(new_state)
           seen.add(new_state)
   ++steps
return -1

通过visited数组保证每一个节点只被访问一次，从而加速了搜索。
但是有一类搜索中，根据题目要求不得不重复访问。这个时候我们需要对进入队列的状态变量进行调整，该状态变量应该是{当前访问节点的状态，全局节点状态}，这样就能有效解决问题。

Shortest Path Visiting All Nodes
An undirected, connected graph of N nodes (labeled 0, 1, 2, …, N-1) is given as graph.
graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:
Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Note:
1 <= graph.length <= 12
0 <= graph[i].length < graph.length

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        const int n = graph.size();
        const int Final = (1 << n) - 1; //111..11
        vector<vector<int>> visited(n, vector<int>(1<<n, 0)); //n*2^n
        queue<pair<int,int>> q;
        for(int i=0; i<n; ++i)
            q.push({i,1<<i});
        int steps = 0;
        
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                int curNode = q.front().first;
                int curStat = q.front().second;
                q.pop();
                if(curStat == Final) return steps;
                if(visited[curNode][curStat]) continue;
                visited[curNode][curStat] = 1;
                //Expand
                for(int neightbour : graph[curNode])
                    q.push({neightbour, curStat | (1<<neightbour)});
            }
            ++steps;
        }
        return -1;
    }
};

Shortest Path to Get All Keys
We are given a 2-dimensional grid. “.” is an empty cell, “#” is a wall, “@” is the starting point, (“a”, “b”, …) are keys, and (“A”, “B”, …) are locks.
We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can’t walk over a lock unless we have the corresponding key.
For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys. If it’s impossible, return -1.
Example 1:
Input: ["@.a.#","###.#",“b.A.B”]
Output: 8

Example 2:
Input: ["@…aA","…B#.","…b"]
Output: 6

Note:

1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only ‘.’, ‘#’, ‘@’, ‘a’-‘f’ and ‘A’-‘F’
The number of keys is in [1, 6]. Each key has a different letter and opens exactly one lock.

class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int final_keys = 0; //最终要达到的状态
        queue<int> q;
        vector<vector<vector<int>>> seen(m, vector<vector<int>>(n, vector<int>(64,0)));
        
        //Init
        for(int i=0; i<m; ++i)
            for(int j=0; j<n; ++j){
                const char c = grid[i][j];
                if(c == '@'){
                    q.push((i<<16) | (j<<8));
                    seen[i][j][0] = 1;
                }else if(c>='a' && c<='f')
                    final_keys |= (1<<c-'a');
            }
        
        const vector<int> dirs{-1,0,1,0,-1};
        
        int steps = 0;
        while(!q.empty()){
            int size = q.size();
            while(size--){
                int s = q.front(); q.pop();
                int x = s>>16;
                int y = (s>>8) & 0xFF;
                int key = s & 0xFF;
                if(key == final_keys) return steps;
                for(int i=0; i<4; ++i){
                    int nkey = key;
                    int nx = x + dirs[i];
                    int ny = y + dirs[i+1];
                    if(nx<0 || nx>=m || ny<0 || ny>=n) continue;
                    const char c = grid[nx][ny];
                    if(c == '#') continue;//Wall
                    //Do not have the key
                    if(c>='A' && c<='F' && !(nkey & (1<<(c-'A')))) continue; # 是lock但是没有钥匙
                    //Update the key we have
                    if(c>='a' && c<='f')
                        nkey |= (1<<(c-'a'));
                    if(seen[nx][ny][nkey]) continue;
                    q.push((nx<<16) | (ny<<8) | nkey);
                    seen[nx][ny][nkey] = 1;
                }
            }
            ++steps;
        }
        return -1;
    }
};

一类特殊的BFS

FEATURED TAGS

FRIENDS