934. Shortest Bridge

DFS + BFS
Time O(mn)
Space O(mn)

昨天contest的题目，没有做出来，原因是看错了题就觉得不会做就放弃了
今天仔细看了一下特别想抽自己
题目说有2个island, 找到flip的最少的点使两个island连在一起
昨天看成了有无数个island...
如果无数个island的话，从一个island出发BFS, reach到一个新island的时候记录步数，此时有可能相同的步数也reach到了其他的island，所以需要把当前层全部走完，找到所有当前层的1，作为接下来dfs的起点。。。

这道题本身就简单很多了，首先搜整个图找到第一个'1'点，进行DFS就找到了第一个island, 一边找一遍把找到的点都放到queue里面作为后面expand的基础
expand通过BFS的level traversal记录step数，如果找到了第一个没有检查过的'1'点，就是另外island的点，直接返回走到这个点用到的步数就好了

这道题的Time和Space要求都很严，必须在进入下一层之前进行valid检查，否则就会TLE或者MLE

class Solution {
    public int shortestBridge(int[][] A) {
        int rows = A.length;
        int cols = A[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> que = new LinkedList<>();
        boolean flag = false;
        for (int y = 0; y < rows; y++) {
            if (flag) {
                break;
            }
            for (int x = 0; x < cols && !flag; x++) {
                if (!visited[y][x] && A[y][x] == 1) {
                    dfs(A, y, x, visited, que);
                    flag = true;
                }
            }
        }
        // que contains all nodes that belong to current area
        int level = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] curr = que.poll();
                for (int i = 0; i < 4; i++) {
                    int currX = curr[1] + dx[i];
                    int currY = curr[0] + dy[i];
                    if (currX >= 0 && currX < A[0].length && currY >= 0 && currY < A.length && !visited[currY][currX]) {
                        if (A[currY][currX] == 1) {
                            return level;
                        } else {
                            visited[currY][currX] = true;
                            que.offer(new int[]{currY, currX});
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
    private int[] dx = new int[]{1, 0, -1, 0};
    private int[] dy = new int[]{0, -1, 0, 1};
    private void dfs(int[][] A, int y, int x, boolean[][] visited, Queue<int[]> que) {
        visited[y][x] = true;
        que.offer(new int[]{y, x});
        for (int i = 0; i < 4; i++) {
            int currX = x + dx[i];
            int currY = y + dy[i];
            if (currX >= 0 && currX < A[0].length && currY >= 0 && currY < A.length
               && A[currY][currX] == 1 && !visited[currY][currX]) {
                dfs(A, currY, currX, visited, que);
            }
        }
    }
}