图论

---

200. 岛屿数量

// 官解：深度优先，如果是陆地ans++，然后将周围陆地全变为'0'
class Solution {
    public int numIslands(char[][] grid) {
        int ans = 0, m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(grid, i, j);      //深度优先搜索进行消除这片岛屿
                }
            }
        }
        return ans;
    }

    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

// 官解还有广度优先，思路其实差不多，借助队列进行消除

994. 腐烂的橘子

// 借助队列使用广度优先，第一次记录下腐烂的橘子位子，每次出队que.size()个橘子，下次就不再使用，后面的时间不再起作用
// 如果影响了周围的橘子腐烂，则入队，作为下次的腐烂源头
class Solution {
    private int fresh; // 代表橘子总数
    private static final int[][] DIRECTIONS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int orangesRotting(int[][] grid) {
        int ans = 0, m = grid.length, n = grid[0].length;

        Queue<int[]> que = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                } else if (grid[i][j] == 2) {
                    que.offer(new int[] { i, j });
                }
            }
        }
        // 已经全部腐烂完，对应[[0]]、[[2]]结果为0min情况
        if (fresh == 0) {
            return 0;
        }
        while (!que.isEmpty()) {
            ans++;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] index = que.poll();
                for (int[] d : DIRECTIONS) {
                    int r = index[0] + d[0];
                    int c = index[1] + d[1];
                    if (0 <= r && r < m && 0 <= c && c < n && grid[r][c] == 1) {
                        fresh--;
                        grid[r][c] = 2;
                        que.offer(new int[] { r, c });
                    }
                }
            }
        }
        return fresh == 0 ? ans - 1 : -1;
    }
}