Java DFS


  • 0
    M

    DFS solution

    class Solution {
        public int findPaths(int m, int n, int N, int i, int j) {
            if (m < 0 || n < 0 || N < 0) {
                return 0;
            }
            Map<String, Integer> map = new HashMap<>();
            return dfs(m, n, N, i, j, map);
        }
        
        private int dfs(int m, int n, int N, int row, int column, Map<String, Integer> map) {
            if (row < 0 || row >= m || column < 0 || column >= n) {
                if (N >= 0) {
                    return 1;
                }
            }
            if (N <= 0) {
                return 0;
            }
            int mod = 1000000007;
            String key = String.valueOf(row) + "," + String.valueOf(column) + "," + String.valueOf(N);
            if (map.containsKey(key)) {
                return map.get(key);
            }
            int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            int sum = 0;
            for (int i = 0; i < dir.length; i++) {
                int newRow = row + dir[i][0];
                int newColumn = column + dir[i][1];
                sum += dfs(m, n, N - 1, newRow, newColumn, map) % mod;
                sum %= mod;
            }
            map.put(key, sum);
            return sum;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.