847. Shortest Path Visiting All Nodes

[1ST TRY]
BFS比较straightforward
从所有点出发，每次向neighbor node探索一次，直到全部探索完
这里的问题是如何记录state
因为每个node可以重复走，所以不能通过node是否visited过来探索
这里的visited的含义是，站在当前的这个node，我已经探索过了哪些node，如果我站在当前的node而已经探索过的node set是重复的，就证明是一个重复的state
如果利用HashSet来记录站在当前node所visited过的node，就会成为Map -> (node, visited States) -> Map of Set<Set<Integer>> 非常复杂
观察到最多只有12个点，所以用一个int 的bit manipulation来记录visit过的点
bit x 位为1则证明这个点还没有visit过
如果 bit x位成为0就证明visit过了
所以一开始把0 - N bit都变成1，当这个mask == 0的时候就是走完了


100.00 %
class Solution {
    public int shortestPathLength(int[][] graph) {
        if (graph == null || graph.length <= 1) {
            return 0;
        }
        // 2 dimensional -> current node + state
        int init = 0;
        int N = graph.length;
        for (int i = 0; i < N; i++) {
            init |= 1 << i;
        }
        // curr[0] -> node, curr[1] -> state
        boolean[][] visited = new boolean[N][init + 1];
        Queue<int[]> que = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            int state = init & ~(1 << i);
            que.offer(new int[]{i, state});
            visited[i][state] = true;
        }   
        int steps = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            steps++;
            while (size-- > 0) {
                int[] curr = que.poll();
                // curr[0] node, curr[1] state
                int[] neighbors = graph[curr[0]];
                for (int neighbor : neighbors) {
                    int nextState = curr[1] & ~(1 << neighbor);
                    if (nextState == 0) {
                        return steps;
                    }
                    if (!visited[neighbor][nextState]) {
                        visited[neighbor][nextState] = true;
                        que.offer(new int[]{neighbor, nextState});
                    }
                }
            }
        }
        return steps;
    }
}

[2ND TRY]
Same idea with 1st try
Instead of using extra space to keep a visited matrix
I used the higher bits to set the node number
It's like hash the [node | visitedNodes] into a single integer
1.13 %
class Solution {
    public int shortestPathLength(int[][] graph) {
// start from any node, bfs until all nodes are visited
// use mask to keep track of visited states
if (graph == null || graph.length == 0 || graph[0] == null || graph[0].length == 0) {
return 0;
}
int N = graph.length;
int init = 0;
for (int i = 0; i < N; i++) {
init |= 1 << i;
}
int min = Integer.MAX_VALUE;
// The (2N, N] bits are used to mark current node
for (int start = 0; start < graph.length; start++) {
// node start as the entry point
Queue<Integer> que = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
// set bit(start) to zero
int initState = init & (~(1 << start));
que.offer(setCurr(initState, start, N));
visited.add(initState);
int step = 0;
while (!que.isEmpty()) {
step++;
int size = que.size();
while (size-- > 0) {
int curr = que.poll();
for (int next : graph[getCurr(curr, N)]) {
int nextState = getState(curr, N) & (~(1 << next));
if (nextState == 0) {
min = Math.min(min, step);
}
int hash = setCurr(nextState, next, N);
if (!visited.contains(hash)) {
visited.add(hash);
que.offer(hash);
}
}
}
}
}
return min;
}

private int setCurr(int state, int curr, int N) {
int mask = 1 << N;
while (curr-- > 0) {
mask <<= 1;
}
return state | mask;
}

private int getCurr(int state, int N) {
state = state >> N;
int result = 0;
while (state > 1) {
result++;
state >>= 1;
}
return result;
}

private int getState(int state, int N) {
int mask = 0;
for (int i = 0; i < N; i++) {
mask |= 1 << i;
}
return state & mask;
}
}