侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】最短的桥

GabrielxD
2022-10-25 / 0 评论 / 0 点赞 / 12 阅读 / 575 字 / 正在检测是否收录...

题目

934. 最短的桥


给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地,0 表示水域。

是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。grid恰好存在两座岛

你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛

返回必须翻转的 0 的最小数目。

示例 1:

输入:grid = [[0,1],[1,0]]
输出:1

示例 2:

输入:grid = [[0,1,0],[0,0,0],[0,0,1]]
输出:2

示例 3:

输入:grid = [[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]]
输出:1

提示:

  • n == grid.length == grid[i].length
  • 2 <= n <= 100
  • grid[i][j]01
  • grid 中恰有两个岛

解题

方法一:BFS

思路

首先遍历找到第一个为陆地的格子,然后 BFS 把第一座岛搜出来,然后从第一座岛再开一个 BFS 一旦搜到第二座岛的陆地就返回步数(注意:第二次搜索时要保证不能向内搜,所以在第一次搜索时要记录已访问的格子第二次直接跳过)。

代码

class Solution {
    static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int[][] grid;
    int n;
    Queue<int[]> que = new LinkedList<>();
    List<int[]> lands = new ArrayList<>();

    public int shortestBridge(int[][] _grid) {
        grid = _grid;
        n = grid.length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) return bfs1(i, j);
            }
        }
        return -1;
    }

    int bfs1(int x, int y) {
        que.offer(new int[]{x, y});
        grid[x][y] = -1;
        while (!que.isEmpty()) {
            int[] pos = que.poll();
            lands.add(pos);
            x = pos[0];
            y = pos[1];
            for (int[] dir : DIRS) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] != 1) continue;
                que.offer(new int[]{nx, ny});
                grid[nx][ny] = -1;
            }
        }
        for (int[] land : lands) que.offer(land);
        return bfs2();
    }

    int bfs2() {
        int step = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] state = que.poll();
                int x = state[0], y = state[1];
                for (int[] dir : DIRS) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == -1) continue;
                    if (grid[nx][ny] == 1) return step;
                    else {
                        que.offer(new int[]{nx, ny});
                        grid[nx][ny] = -1;
                    }
                }
            }
            ++step;
        }
        return -1;
    }
}
0

评论区