LeetCode #934 最短的桥

Espada 最近想系统地学声乐! 本文由博客端 https://blog.yuanmo.xyz 主动推送

934.png

Problem Description

在给定的二维二进制数组 A 中,存在两座岛。(岛是由四面相连的 1 形成的一个最大组。)

现在,我们可以将 0 变为 1,以使两座岛连接起来,变成一座岛。

返回必须翻转的 0 的最小数目。(可以保证答案至少是 1。)

note

e.g.

Solution

题目保证答案至少是 1,那么一定是 2 个岛。岛的定义是上下左右相连所以斜着的不算。返回翻转 0 的最小值,这个最小值就是桥的长度,也就是「最短路径」。

一般看到「最短路径」我们会想到 bfsA*Dijkstra 算法,一般都是点对点的,这里是两个岛屿,所以只要将一个岛的所有边缘上的点都求一遍到第二个岛的路径,返回最小的路径就可以了。

所以问题就是怎么找出这两个岛?岛屿只有上下左右相连,所以可以根据深度优先搜索,将某坐标的上下左右进行搜索,如果是 1 则继续搜索,是 0 则终止。为了将两个岛区分开,我们需要将第一个找到的岛「涂色」,因为后面需要找第二个岛,如果都用 1 表示就没法区分开了。

注意的点:

  1. bfs 去找第二个岛,因为是第一个岛的每个节点去广搜,所以 visited 访问标记每次循环需要初始化。
  2. bfs 周围的点如果是 -1 的话没必要入队,因为可能同是旁边的点(旁边的点会 bfs 一次,这里重复了),或者是第一个岛的非边缘的点,一定不是「最短路径」。
  3. bfs 一定能找到第二个岛的点,所以一定是在迭代里 return 的。
  4. 优化点也有,比如在该题其实不需要 visited 访问标记,每次初始化很浪费时间空间。
public class ShortestBridge {
    public static int shortestBridge(int[][] arr) {
        List<int[]> firstLand = new ArrayList<>();
        boolean[][] visited = new boolean[arr.length][arr[0].length];
        boolean flag = false;
        for (int i = 0; i < arr.length; i++) {
            if (flag) {
                break;
            }
          	// 设置一个flag,找到后需要继续遍历这个arr了。
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == 1) {
                    dfs(arr, i, j, visited, firstLand);
                    flag = true;
                    break;
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int[] xy : firstLand) {
            // 【注意】每次初始化访问标记【注意】
            visited = new boolean[arr.length][arr[0].length];
            ans = Math.min(ans, bfs(arr, xy[0], xy[1], visited));

        }
        return ans;
    }

    /**
     *
     * @param arr
     * @param x
     * @param y
     * @param visited
     * @param firstLand
     */
    public static void dfs(int[][] arr, int x, int y, boolean[][] visited, List<int[]> firstLand) {
        if (x >= 0 && y >= 0 && x < arr.length && y < arr[0].length && !visited[x][y]) {
            visited[x][y] = true;
            if (arr[x][y] == 0) {
                return;
            }
            arr[x][y] = -1;
            firstLand.add(new int[]{x, y});
            // 仅仅只有上下左右
            dfs(arr, x - 1, y, visited, firstLand);
            dfs(arr, x + 1, y, visited, firstLand);
            dfs(arr, x, y - 1, visited, firstLand);
            dfs(arr, x, y + 1, visited, firstLand);
        }
    }


    /**
     * wcnd,写死我了
     *
     * @param arr
     * @param x
     * @param y
     * @param visited
     * @return
     */
    public static int bfs(int[][] arr, int x, int y, boolean[][] visited) {
        // 最后要减一
        int len = -1;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int limit = queue.size();
            for (int i = 0; i < limit; i++) {
                int[] curr = queue.poll();
                x = curr[0];
                y = curr[1];
                // 找到了1
                if (arr[x][y] == 1) {
                    return len;
                }
                // 如果周围的节点是-1的话,没必要入队
                if (x - 1 >= 0 && !visited[x - 1][y] && arr[x - 1][y] != -1) {
                    queue.offer(new int[]{x - 1, y});
                    visited[x - 1][y] = true;
                }
                if (x + 1 < arr.length && !visited[x + 1][y] && arr[x + 1][y] != -1) {
                    queue.offer(new int[]{x + 1, y});
                    visited[x + 1][y] = true;
                }
                if (y - 1 >= 0 && !visited[x][y - 1] && arr[x][y - 1] != -1) {
                    queue.offer(new int[]{x, y - 1});
                    visited[x][y - 1] = true;
                }
                if (y + 1 < arr[0].length && !visited[x][y + 1] && arr[x][y + 1] != -1) {
                    queue.offer(new int[]{x, y + 1});
                    visited[x][y + 1] = true;
                }
            }
            len++;
        }
        // 一定是可以找到最短路径的,所以这里返回的是错误的
        return Integer.MAX_VALUE;
    }
}
  • 深度优先搜索
    1 引用
  • 广度优先搜索
    2 引用
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    197 引用 • 74 回帖 • 1 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    2812 引用 • 8042 回帖 • 749 关注
1 操作
matthewhan 在 2020-08-14 10:48:58 更新了该帖

赞助商 我要投放

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...