2684. 矩阵中移动的最大次数(中等)

Posted on In Views:

1，问题描述

2684. 矩阵中移动的最大次数

难度：中等

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

  • 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动 的 最大 次数。

示例 1：

img

1
2
3
4
5
6
7
输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2：

1
2
3
输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^6

2，初步思考

​ 广度优先搜索、深度优先搜索都可以完成

​ 深度优先搜索理论上相较于广度只会更快，因为我们已知边界（极值），不需要全部遍历完

3，代码处理

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package questions;

import java.util.Deque;
import java.util.LinkedList;

public class _2684矩阵中移动的最大次数 {

    // 动态规划求解
    public int maxMoves_dp(int[][] grid) {
        int n = grid.length, m = grid[0].length, max = 0;
        int[][] dp = new int[n][m];
        return max;
    }

    // 广度优先搜索求解，添加visited访问标记
    public int maxMoves_bfs(int[][] grid) {
        int n = grid.length, m = grid[0].length, max = 0;
        boolean[][] visited = new boolean[n][m];
        Deque<int[]> queue = new LinkedList<>();// 广度优先搜索
        for (int i = 0; i < n; i++) {
            queue.addLast(new int[]{i, 0});
        }
        while (!queue.isEmpty()) {// 广度遍历
            int[] ints = queue.pollFirst();
            int i = ints[0];
            int j = ints[1];
            if (!visited[i][j]) {
                visited[i][j] = true;
                max = Math.max(max, j);
                if (j == m - 1) {// 提前退出
                    return max;
                }
                if (grid[i][j] < grid[i][j + 1]) {
                    queue.addLast(new int[]{i, j + 1});
                }
                if (i - 1 >= 0 && grid[i][j] < grid[i - 1][j + 1]) {
                    queue.addLast(new int[]{i - 1, j + 1});
                }
                if (i + 1 < n && grid[i][j] < grid[i + 1][j + 1]) {
                    queue.addLast(new int[]{i + 1, j + 1});
                }
            }
        }
        return max;
    }

    // 深度优先搜索
    // 可以更快一些，要做剪枝操作，性能比广度只会更快
    public int maxMoves(int[][] grid) {
        int n = grid.length, m = grid[0].length, max = 0;
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < grid.length; i++) {
            int dfs = dfs(grid, visited, i, 0);
            if (dfs == m - 1) return dfs;
            max = Math.max(max, dfs);
        }
        return max;
    }

    private int dfs(int[][] grid, boolean[][] visited, int i, int j) {
        if (j == grid[0].length - 1) return 0;
        if (visited[i][j]) return 0;
        visited[i][j] = true;
        int temp1 = 0, temp2 = 0, temp3 = 0;
        if (grid[i][j] < grid[i][j + 1]) {
            temp1 = 1 + dfs(grid, visited, i, j + 1);
        }
        if (i - 1 >= 0 && grid[i][j] < grid[i - 1][j + 1]) {
            temp2 = 1 + dfs(grid, visited, i - 1, j + 1);
        }
        if (i + 1 < grid.length && grid[i][j] < grid[i + 1][j + 1]) {
            temp3 = 1 + dfs(grid, visited, i + 1, j + 1);
        }
        return Math.max(temp1, Math.max(temp2, temp3));
    }

    public static void main(String[] args) {
        _2684矩阵中移动的最大次数 q = new _2684矩阵中移动的最大次数();

        System.out.println(q.maxMoves_bfs(new int[][]{
                {3, 2, 4},
                {2, 1, 9},
                {1, 1, 7}
        }));
//        System.out.println(q.maxMoves(new int[][]{
//                {2, 4, 3, 5},
//                {5, 4, 9, 3},
//                {3, 4, 2, 11},
//                {10, 9, 13, 15}}));
//        System.out.println(q.maxMoves(new int[][]{{1000000, 92910, 1021, 1022, 1023, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035, 1036, 1037, 1038, 1039, 1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 1048, 1049, 1050, 1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063, 1064, 1065, 1066, 1067, 1068}, {1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080, 1081, 1082, 1083, 1084, 1085, 1086, 1087, 1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095, 1096, 1097, 1098, 1099, 1100, 1101, 1102, 1103, 1104, 1105, 1106, 1107, 1108, 1109, 1110, 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118}}));
//        System.out.println(q.maxMoves(new int[][]{{5, 1, 2, 3, 4}, {4, 2, 3, 4, 5}, {3, 2, 1, 4, 5}, {2, 3, 4, 5, 1}, {1, 2, 3, 4, 5}}));
    }
}