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
Solution:
class Solution {
class Node {
int bitMask;
int curr;
int cost;
public Node(int bit, int n, int c){
bitMask = bit;
curr = n;
cost = c;
}
public boolean equals(Object o){
Node p = (Node) o;
return bitMask == p.bitMask && curr == p.curr && cost == p.cost;
}
public int hashCode(){
int hash = 17;
hash += 31 * hash + bitMask;
hash += 31 * hash + curr;
return 31 * hash + cost;
}
}
public int shortestPathLength(int[][] graph) {
int n = graph.length;
Deque<Node> queue = new ArrayDeque();
Set<Node> set = new HashSet();
for (int i = 0; i < n; i ++) {
int mask = (1 << i);
queue.offer(new Node(mask, i, 0));
set.add(new Node(mask, i, 0));
}
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.bitMask == (1 << n) - 1) return node.cost;
for (int next : graph[node.curr]) {
int mask = node.bitMask | (1 << next);
Node nextNode = new Node(mask, next, node.cost + 1);
if (set.add(nextNode)) {
queue.offer(nextNode);
}
}
}
return -1;
}
}