Leetcode 2328. Number of Increasing Paths in a Grid

[Woodyiiiiiii]

2328. Number of Increasing Paths in a Grid

https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/
BFS题解

类似题目：

• 329. Longest Increasing Path in a Matrix
• 2713. Maximum Strictly Increasing Cells in a Matrix

直接用DFS。重点是，使用缓存。不需要使用访问数组v，因为路径path是严格递增的，不会形成环。

class Solution {
    
    int[] X = new int[]{1, 0, -1, 0};
    int[] Y = new int[]{0, 1, 0, -1};
    long mod = 1000000007;

    public int countPaths(int[][] grid) {

        long res = 0;
        int m = grid.length;
        int n = grid[0].length;
        long[][] cache = new long[m][n];

        for (int i = 0; i < m; i++) {
            Arrays.fill(cache[i], -1);
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res = (res + dfs(grid, cache, i, j)) % mod;
            }
        }

        return (int) res;

    }

    private long dfs(int[][] grid, long[][] cache, int i, int j) {
        
        if (cache[i][j] != -1) {
            return cache[i][j];
        }

        cache[i][j] = 1;
        for (int k = 0; k < 4; ++k) {
            int x = i + X[k];
            int y = j + Y[k];
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
                continue;
            }
            if (grid[x][y] <= grid[i][j]) {
                continue;
            }
            cache[i][j] = (cache[i][j] + dfs(grid, cache, x, y)) % mod;
        }

        return cache[i][j];

    }
    
    
}

另一种方法是使用多源BFS + 优先队列：

class Solution {

    public int countPaths(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int[] row : dp) Arrays.fill(row, 1);
        final int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        final int MOD = (int) 1e9 + 7;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                pq.add(new int[]{i, j, grid[i][j]});
            }
        }

        int ans = 0;
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], val = cur[2];
            for (int[] dir : dirs) {
                int nx = dir[0] + x, ny = dir[1] + y;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] < val) {
                    dp[x][y] = (dp[x][y] + dp[nx][ny]) % MOD;
                }
            }
            ans = (ans + dp[x][y]) % MOD;
        }
        return ans;
    }
    
}

速度稍微慢一些。因为是O(mnlgmn)复杂度，比上面的方法O(mn)更耗时。