leetcode934 最短的桥

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode934 最短的桥，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1233字，纯文字阅读大概需要2分钟。

内容图文

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);
    }
}

内容总结

以上是互联网集市为您收集整理的leetcode934 最短的桥全部内容，希望文章能够帮你解决leetcode934 最短的桥所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---