leetcode 847. Shortest Path Visiting All Nodes

Posted on | In , |

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

思路

用二进制的数来表示当前访问节点的状态
4个节点 如1101表示 0，2，3号节点已访问过

最后的终止状态是1111

或者用Hashtable 也可以

为了遍历所有的节点 一个节点可以被重复访问 所以不能用 vis[cur] 跳过访问过的节点

但是不跳过访问过的状态 可能会陷入 0->1->0的死循环

所以建立二维数组vis 记录当前访问过的节点和状态
不会重复在这个节点的访问状态
即 在1号节点已经访问过0号，1号房间

pair<int,int> {1,0011}

即在搜索1号节点的邻居时不会再访问0号节点 因为此时状态不会更新
还是 0011

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
class Solution {
public:
    int n,m;
   map<int,vector<int> > g;
    int shortestPathLength(vector<vector<int>>& graph) {
        m=graph.size();
     
            for(int i=0;i<graph.size();i++){
            for(int j=0;j<graph[i].size();j++){
                g[i].push_back(graph[i][j]);       
            }   
        }
        int ans=1e8;
        queue<pair<int,int> >q;
        for(int i=0;i<m;i++)
            q.push(pair<int,int>{i,1<<i});
        int steps=0;
        bool vis[12][5000]={false};
        int kstate=(1<<m)-1;//!!
        while(!q.empty()){
            int size=q.size();
            while(size--){
                pair<int,int> p=q.front();
                q.pop();
                int cur=p.first;
                int state=p.second;
                
                if(state==kstate) return steps;
                if(vis[cur][state]) continue;
                vis[cur][state]=1;
                for(int i=0;i<g[cur].size();i++){
                    q.push(pair<int,int>{g[cur][i],state|(1<<g[cur][i])});//!! 当前状态 1<<g[cur][i]
                //    cout<<cur<<" -> "<<g[cur][i]<<" state:"<<(state|g[cur][i])<<" steps:"<<steps<<endl;
                    
                }
                
                
                
            }
            
            steps++;
            
            
        }
               return -1;
    }
  
    
};