847 Shortest Path Visiting All Nodes
You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.
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: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
好难啊！要遍历所有的点，有些点不得不遍历多次，又不能有无用的步骤。使用一个超大矩阵存放走过的步骤，第一个元素表示从哪个点开始，第二个元素表示走之后的状态，如果一个状态存在过，说明这一步是无用的。由于最大只有 12 个点，所以可以使用一个整数表示状态，使用一个二进制整数，如果某一位为 1 ，表示这个点遍历过，例如 11010 表示第 2,4,5 个点遍历过，完成时的状态为每一位都是 1 。对每个点进行 bfs ，将新的没有走过的点和状态加入队列。当完成的状态出现时，返回步数。
public int shortestPathLength(int[][] graph) {
int len = graph.length;
int finished = (1 << len) -1;
int step = 0;
boolean[][] visited = new boolean[len][1<<len];
Queue<int[]> queue = new LinkedList<>();
for(int i=0;i<len;++i){
queue.add(new int[]{i, 1<<i});
}
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;++i){
int[] pair = queue.poll();
if(finished == pair[1]) return step;
for(int next: graph[pair[0]]){
int nextState = pair[1] | (1<<next);
if(visited[next][nextState]) continue;
queue.add(new int[]{next, nextState});
visited[next][nextState] = true;
}
}
step++;
}
return step;
}