leetcode934 最短的桥

https://leetcode-cn.com/problems/shortest-bridge/
给定一个数组。数组中包含两个岛屿。求两个岛屿之间的最短距离。
采用找岛屿的方式(DFS),把其中的一个岛屿全部标记为2。并且用一个queue来存储上,此时采用BFS根据queue中的每一个节点逐步向外扩,直到遇到第一个数字1,也就找到了最短的距离。

class Solution { 
    public int shortestBridge(int[][] A) {
        int len1 = A.length;
        int len2 = A[0].length;
        Queue<int[]> q = new LinkedList<int[]>();
        boolean found = false;
        for(int i = 0; i<A.length && !found; i++){
            for(int j=0; j<A[0].length && !found; j++){
                if(A[i][j]==1){
                    dfs(A,i,j,q);
                    found = true;
                }
            }
        }

        int[][] dic = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        int step = 0;
        while(!q.isEmpty()){
            int size = q.size();
            while(size>0){
                int x = q.peek()[0];
                int y = q.peek()[1];
                q.poll();
                for(int i = 0; i<4; i++){
                    int tx = x + dic[i][0];
                    int ty = y + dic[i][1];
                    if(tx<0 || ty<0 || tx>=len1 || ty>=len2 || A[tx][ty]==2){
                        continue;
                    }
                    if(A[tx][ty] == 1){
                        return step;
                    }
                    A[tx][ty] = 2;
                    q.add(new int[]{tx,ty});
                }
                size--;
            }
            step++;
        }
        return -1;
    }

    private void dfs(int[][] A, int i, int j, Queue<int[]> q){
        int len1 = A.length;
        int len2 = A[0].length;

        if(i<0 || j<0 || i>=len1 || j>=len2 || A[i][j]!=1){
            return;
        }
        A[i][j] = 2;
        q.add(new int[]{i,j});
        dfs(A,i-1,j,q);
        dfs(A,i+1,j,q);
        dfs(A,i,j-1,q);
        dfs(A,i,j+1,q);
    }
}
上一篇:WebBrowser控件打开https站点


下一篇:010.PGSQL-炸裂函数regexp_split_to_table、分组连接string_agg