2684. Maximum Number of Moves in a Grid

DFS

class Solution {
    private static class Result {
        private int maxMoves;
    }

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

        Result result = new Result();

        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < grid.length; i++) {
            dfs(result, grid, visited, i, 0);
        }

        return result.maxMoves;
    }

    private void dfs(Result result, int[][] grid, boolean[][] visited, int i, int j) {
        visited[i][j] = true;
        result.maxMoves = Math.max(result.maxMoves, j);
        if (j == grid[0].length - 1) {
            // 已到达最右列，防止下方 for 循环越界
            return;
        }

        for (int k = Math.max(i - 1, 0); k <= Math.min(i + 1, grid.length - 1); k++) {
            if (visited[k][j + 1]) {
                continue;
            }
            if (grid[k][j + 1] > grid[i][j]) {
                dfs(result, grid, visited, k, j + 1);
            }
        }
    }
}

BFS

class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        int maxMoves = 0;

        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            queue.offer(new int[]{i, 0});
        }

        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int[] cell = queue.poll();
                int r = cell[0], c = cell[1];
                if (c == n - 1) {
                    return n - 1;
                }
                for (int k = Math.max(r - 1, 0); k <= Math.min(r + 1, m - 1); k++) {
                    if (visited[k][c + 1]) {
                        continue;
                    }
                    if (grid[k][c + 1] > grid[r][c]) {
                        queue.offer(new int[]{k, c + 1});
                        visited[k][c + 1] = true;
                    }
                }
            }

            if (!queue.isEmpty()) {
                maxMoves++;
            }
        }

        return maxMoves;
    }
}

DP

class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        int maxMoves = 0;

        int[][] dp = new int[m][n];
        for (int j = n - 2; j >= 0; j--) {
            for (int i = 0; i < m; i++) {
                int curr = grid[i][j];
                int rightUp = i == 0 ? Integer.MIN_VALUE : grid[i - 1][j + 1];
                int right = grid[i][j + 1];
                int rightDown = i == m - 1 ? Integer.MIN_VALUE : grid[i + 1][j + 1];

                if (curr < rightUp) {
                    dp[i][j] = dp[i - 1][j + 1] + 1;
                }
                if (curr < right) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
                }
                if (curr < rightDown) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j + 1] + 1);
                }

                if (j == 0) {
                    maxMoves = Math.max(maxMoves, dp[i][j]);
                }
            }
        }

        return maxMoves;
    }
}

以上解法为从右到左，该解法不能剪枝，效率偏低。

DP

class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int maxMoves = 0; // 注意是移动次数而不是路径长度

        int[][] dp = new int[m][n];

        for (int j = 1; j < n; j++) {
            for (int i = 0; i < m; i++) {
                if (grid[i][j] > grid[i][j - 1]) {
                    dp[i][j] = dp[i][j - 1] + 1;
                }
                if (i - 1 >= 0 && grid[i][j] > grid[i - 1][j - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
                if (i + 1 < m && grid[i][j] > grid[i + 1][j - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 1);
                }
                maxMoves = Math.max(maxMoves, dp[i][j]);
            }

            // 如无法到达当前列，则提前剪枝
            if (maxMoves < j) {
                break;
            }
        }

        return maxMoves;
    }
}

以上解法为从左到右，可提前剪枝，效率更高。

References

2684. Maximum Number of Moves in a Grid