leetcode 847

问题

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:

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

Example 2:

1
2
3
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. 1 <= graph.length <= 12
  2. 0 <= graph[i].length < graph.length

分析

每个阶段的状态保存需要有两个部分来表示，一个是需要保存所有已经访问过的节点有哪些，另一个是最终停在了哪一个节点上。保存已经访问过的节点可是使用二进制位压缩来表示，比如节点0，2，3被访问，可以表示为二进制 1101。于是我们使用二维数组来表示状态，第一维表示当前节点的位置，第二位来表示已经访问过的节点的有哪些。使用广度优先搜索，来从初始状态逐渐推向整个状态，visited[n][1<<n] 用来标记状态是否已经被遍历过。
note：之前一直想的是DFS，没有想到BFS也有和DP相结合的情况。

代码

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
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<bool>> visited(n, vector<bool>(1<<n, false));
        int endState = (1<<n)-1;
        queue<pair<int,int>> q;
        for (int i = 0; i < n; ++i) {
            q.push({i, 1<<i});  // 加入第一层的所有可能状态
            visited[i][1<<i] = true;
        }
        int level = 0;
        while (q.size()) {
            int s = q.size();
            while (s--) {  // 遍历一层
                auto [x, state] = q.front();
                q.pop();
                if (state == endState) {
                    return level;
                }
                for (int y: graph[x]) {
                    if (visited[y][state | (1<<y)])
                        continue;
                    visited[y][state | (1<<y)] = true;
                    q.push({y, state | (1<<y)});
                }
            }
            level++;
        }
        return -1;
    }
};