1970. 你能穿过矩阵的最后一天Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天，整个矩阵都是陆地。但每一天都会有一块新陆地被水淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [ri, ci] 表示在第 i 天，第 ri 行 ci 列（下标都是从 1 开始）的陆地会变成水域（也就是 0 变成 1 ）。

你想知道从矩阵最上面一行走到最下面一行，且只经过陆地格子的最后一天是哪一天。你可以从最上面一行的任意格子出发，到达最下面一行的任意格子。你只能沿着四个基本方向移动（也就是上下左右）。

请返回只经过陆地格子能从最上面一行走到最下面一行的最后一天。

示例 1：

输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。

示例 2：

输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]] 输出：1 解释：上图描述了矩阵从第 0 天开始是如何变化的。可以从最上面一行到最下面一行的最后一天是第 1 天。示例 3：

输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。

提示：

2 <= row, col <= 2 * 10⁴
4 <= row * col <= 2 * 10⁴
cells.length == row * col
1 <= ri <= row
1 <= ci <= col
cells 中的所有格子坐标都是唯一的。

# 思路

dfs

# 解法

class Solution {
    
    private int[][] move = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    
    public int latestDayToCross(int row, int col, int[][] cells) {
        int[][] arr = new int[row][col];
        int day = 0;
        int j = 0;
        for (int[] cell : cells) {
            if (arr[cell[0] - 1][cell[1] - 1] == 1) {
                day++;
                continue;
            }
            arr[cell[0] - 1][cell[1] - 1] = 1;
            int count = 0;
            for (; j < col; j++) {
                if (arr[0][j] != 1) {
                    boolean[][] visited = new boolean[row][col];
                    if (dfs(row, col, arr, 0, j, visited)) {
                        break;
                    } else {
                        arr[0][j] = 1;
                    }
                }
            }
            if (j == col) return day;
            day++;
        }
        return day;
    }
    
    private boolean dfs(int row, int col, int[][] arr, int i, int j, boolean[][] visited) {
        if (i == row) return true;
        if (i < 0 || j < 0 || j >= col || arr[i][j] == 1 || visited[i][j]) return false;
        visited[i][j] = true;
        for (int[] m : move) {
            if (dfs(row, col, arr, i + m[0], j + m[1], visited)) return true;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 总结

分析出几种情况，然后分别对各个情况实现

#Java