[LeetCode] 934. Shortest Bridge

bingo 发布于2019-08-16 13:57 / 2764人阅读

Problem

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]
Output: 1
Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3:

Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Note:

1 <= A.length = A[0].length <= 100
Ai == 0 or Ai == 1

Solution

class Solution {
    public int shortestBridge(int[][] A) {
        //find the first island, using dfs
        int m = A.length, n = A[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue queue = new LinkedList<>(); //for bfs
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        
        boolean found = false;
        for (int i = 0; i < m; i++) {
            if (found) break;
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    found = true;
                    dfs(A, i, j, visited, dirs, queue);
                    break;
                }
            }
        }
        
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] dir: dirs) {
                    int x = cur[0]+dir[0], y = cur[1]+dir[1];
                    if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) continue;
                    if (A[x][y] == 1) return count;
                    queue.offer(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
            count++;
        }
        return -1;
    }
    
    private void dfs(int[][] A, int i, int j, boolean[][] visited, int[][] dirs, Queue queue) {
        int m = A.length, n = A[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || A[i][j] == 0 || visited[i][j]) return;
        queue.offer(new int[]{i, j});
        visited[i][j] = true;
        for (int[] dir: dirs) {
            dfs(A, i+dir[0], j+dir[1], visited, dirs, queue);
        }
    }
}

云服务器 GPU云服务器 Shortest bridge Bridge模式 LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72626.html

Leetcode PHP题解--D86 748. Shortest Completing Word

摘要：题目链接题目分析从给定的一个字符串中提取字符。若出现次数相同，则返回第一个符合条件的单词。假定结果必定存在。思路先提取字符，转换成小写，并计算字符出现的次数。短则覆盖，长则抛弃。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D86 748. Shortest Completing Word 题目链接 748. Shortest Completing Word 题目分析从给定的一个...

seasonley 2019-07-01 13:59 评论0 收藏0
Leetcode PHP题解--D49 821. Shortest Distance to a Ch

摘要：返回字符串中每一个字符离给定的字符的最短距离。否则，当当前下标大于上一个出现字符的位置，且存在下一个字符时，距离为两者中最小的那个。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D49 821. Shortest Distance to a Character 题目链接 821. Shortest Distance to a Character 题目分析给定一个字符串s和一个字符...

Shisui 2019-07-01 12:44 评论0 收藏0
[LeetCode] 244. Shortest Word Distance II

Problem Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the l...

Nekron 2019-08-16 14:00 评论0 收藏0
[Leetcode] Shortest Word Distance 最短单词间距

摘要：代码第一次写入就先不比较第一次写入就先不比较哈希表法复杂度时间空间思路因为会多次调用，我们不能每次调用的时候再把这两个单词的下标找出来。我们可以用一个哈希表，在传入字符串数组时，就把每个单词的下标找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...

jsliang 2019-08-14 12:48 评论0 收藏0
[LeetCode] Shortest Distance to a Character

Problem Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string. Example 1: Input: S = loveleetcode, C = eOutput: [3, 2, 1...

blankyao 2019-08-19 11:00 评论0 收藏0