980. Unique Paths III

 一刷 06/2022

Version #1 DFS

Time - The fanout factor is 3, the depth is MN, so O(3^(MN))

Space O(MN)

Runtime: 1 ms, faster than 88.78% of Java online submissions for Unique Paths III.

Memory Usage: 39.9 MB, less than 81.76% of Java online submissions for Unique Paths III.

class Solution {

    private static int START = 1;

    private static int END = 2;

    private static int SPACE = 0;

    private static int OBSTACLE = -1;

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

        int rows = grid.length;

        int cols = grid[0].length;

        boolean[][] visited = new boolean[rows][cols];

        int spaceCount = 0;

        int startX = 0, startY = 0;

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (grid[y][x] == SPACE) {

                    spaceCount++;

                }

                if (grid[y][x] == START) {

                    startX = x;

                    startY = y;

                }

            }

        }

        // TODO

        visited[startY][startX] = true;

        return dfs(grid, visited, startX, startY, 0, spaceCount);

    }

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    

    // Stading at current point, how many ways are there to reach target grid and visit all unvisited squares

    private int dfs(int[][] grid, boolean[][] visited, int x, int y, int stepCount, int spaceCount) {

        if (grid[y][x] == END) {

            // + 1 because the last step to the END is also included

            if (stepCount == spaceCount + 1) {

                return 1;

            }

            return 0;

        }

        int cnt = 0;

        for (int i = 0; i < 4; i++) {

            int nX = x + dx[i];

            int nY = y + dy[i];

            // out of boundary

            if (nX < 0 || nY < 0 || nX >= grid[0].length || nY >= grid.length) {

                continue;

            }

            if (visited[nY][nX] || grid[nY][nX] == OBSTACLE) {

                continue;

            }

            visited[nY][nX] = true;

            cnt += dfs(grid, visited, nX, nY, stepCount + 1, spaceCount);

            visited[nY][nX] = false;

        }

        return cnt;

    }

}