Solution For Unique Paths Iii

Problem statement:
You are given an m x n integer array grid where:

• Start is a coordinate in the grid. Each move consists of moving one space in the north, east, south, or west direction. You can only move to a cell that is not blocked.
• An empty cell is marked with the value 0.
• A cell with an obstacle is marked with -1.

• Return the number of unique paths from start to finish such that:

• You can take any path in any order.

• The start and the finish cells are not blocked.
• If a cell is visited, then it must be visited exactly once.

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]] Output: 2
Explanation: We have the following two paths:
1. (0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1), (1,0), (2,0), (2,1), (2,2)
2. (0,0), (1,0), (2,0), (2,1), (1,1), (1,2), (0,2), (0,3), (1,3), (2,3)

Solution:

Approach:

We need to find a path from the start to the end point. There can be many paths that may lead to the end point, but all those paths should be unique, which means that each cell can be visited only once. We will use DFS (Depth-First Search) to check all possible paths, and we will keep a count of all unique paths that can lead us to the end. We will start from the starting point and explore all nearby cells by considering four possible directions (north, east, south, west). If we find the end point, we will increment the count of unique paths. Additionally, to consider that all cells are visited exactly once, we need to use a visited array to mark the already visited cells. We will also keep track of the count of empty cells and the starting point to calculate the total number of unique paths.

Algorithm:

Let m be the number of rows and n be the number of columns in the grid
1. Initialize the count of unique paths to 0
2. Traverse the grid and calculate the count of empty cells and the starting point
3. Initialize the visited array of size m x n, and mark all obstacles as visited
4. Call the recursive DFS function with the following parameters:
– x: row of the current cell
– y: column of the current cell
– empty: count of empty cells
5. Inside the DFS function:
– Base case: if the current cell is the end point, check if all cells are visited exactly once, and if they are, then increment the count of unique paths
– Recursive case: visit all possible directions (north, east, south, west) and increment the visited count for each visited cell
6. Return the count of unique paths

Pseudo code:

function uniquePathsIII(grid: number[][]): number {
let unique: number = 0;
let empty: number = 0;
let m: number = grid.length;
let n: number = grid[0].length;
let startRow: number;
let startCol: number;
let visited: boolean[][] = new Array(m).fill(false).map(() => new Array(n).fill(false));

// Traverse the grid to calculate the count of empty cells and the starting point
for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
        if (grid[i][j] === 0) {
            empty++;
        } else if (grid[i][j] === 1) {
            startRow = i;
            startCol = j;
        }
    }
}

// Initialize visited array and mark obstacles as visited
for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
        if (grid[i][j] === -1) {
            visited[i][j] = true;
        }
    }
}

// Recursive DFS function to traverse the grid and count unique paths
function DFS(x: number, y: number, visitedCount: number) {
    // Base case: if the current cell is the end point, check if all cells are visited exactly once, and if they are, then increment the count of unique paths
    if (grid[x][y] === 2) {
        if (visitedCount === empty + 1) {
            unique++;
        }
        return;
    }
    // Recursive case: visit all possible directions (north, east, south, west) and increment the visited count for each visited cell
    let directions: number[][] = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    for (let dir of directions) {
        let newX: number = x + dir[0];
        let newY: number = y + dir[1];
        if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
            visited[newX][newY] = true;
            DFS(newX, newY, visitedCount + 1);
            visited[newX][newY] = false;
        }
    }
}

// Call the recursive DFS function with the starting point and starting visited count
visited[startRow][startCol] = true;
DFS(startRow, startCol, 1);

return unique;

}

Time Complexity: O(3^(m * n))
– During the DFS call, for each cell, we can make three possible moves (excluding the visited cells and obstacle blocks). Hence, the number of possible paths will be 3 ^ (m * n), which is the maximum possible paths.
– But, as the number of empty cells will always be less than (m * n), the actual time complexity will be less than this worst-case scenario.

Space Complexity: O(m x n)
– We need to use the visited array, and its size will be m x n.
– Additionally, we need to use recursive space for the DFS function.

Step by Step Implementation For Unique Paths Iii

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .
Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

def uniquePathsIII(self, grid):
        # keep track of how many empty spaces are left
        # as well as the starting and ending coordinates
        empty = 1
        start = None
        end = None
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    empty += 1
                elif grid[i][j] == 1:
                    start = (i, j)
                elif grid[i][j] == 2:
                    end = (i, j)
                    
        # use backtracking to find all possible paths
        # from the starting position to the ending position
        # that go through all empty spaces
        def backtrack(i, j, empty):
            # if we reached the end, and we visited all empty spaces
            # then we have found a valid path
            if i == end[0] and j == end[1] and empty == 0:
                return 1
            
            # mark the current position as visited
            grid[i][j] = -2
            # initialize the count of paths to 0
            count = 0
            # explore all possible directions from the current position
            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                # if the new position is valid and empty
                # then recurse from that position
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] >= 0:
                    count += backtrack(x, y, empty-1)
                    
            # mark the current position as unvisited
            grid[i][j] = 0
            # return the total number of paths
            return count
        
        # start backtracking from the starting position
        return backtrack(start[0], start[1], empty)

There are a total of n^2 unique paths that can be taken.

For each cell in the grid, we can either move to the right or down.

If we reach the end of the row, we can only move down.

If we reach the end of the column, we can only move to the right.

If the current cell is visited, we can only move to the next cell if it is not visited.

int uniquePathsIII(vector>& grid) {
    int n = grid.size(), m = grid[0].size();
    int sx, sy, ex, ey, zeros = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 0) {
                ++zeros;
            }
            else if (grid[i][j] == 1) {
                sx = i; sy = j;
            }
            else if (grid[i][j] == 2) {
                ex = i; ey = j;
            }
        }
    }
    int ans = 0;
    function dfs = [&](int x, int y, int remain) {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] < 0) return;
        if (x == ex && y == ey) {
            if (remain == 0) ans++;
            return;
        }
        grid[x][y] = -2;
        dfs(x + 1, y, remain - 1);
        dfs(x - 1, y, remain - 1);
        dfs(x, y + 1, remain - 1);
        dfs(x, y - 1, remain - 1);
        grid[x][y] = 0;
    };
    dfs(sx, sy, zeros);
    return ans;
}

There are a couple different ways to approach this problem. One way would be to use a backtracking algorithm. This would involve starting at the top left corner of the grid and then trying to find a path to the bottom right corner. Along the way, you would keep track of how many empty cells you've seen and how many total empty cells there are in the grid. If you ever reach a point where you've seen all of the empty cells, then you know you've found a valid path.

Another way to approach this problem would be to use dynamic programming. This would involve creating a 2D array to store the number of paths from each cell to the bottom right corner. Then, you would fill in this array by starting at the bottom right corner and working your way back to the top left corner.

Here is some sample code using the backtracking approach:

public int UniquePathsIII(int[][] grid) { int numEmpty = 0; for (int i = 0; i < grid.Length; i++) { for (int j = 0; j < grid[0].Length; j++) { if (grid[i][j] == 0) { numEmpty++; } } } return UniquePathsIIIHelper(grid, 0, 0, numEmpty); } private int UniquePathsIIIHelper(int[][] grid, int i, int j, int numEmpty) { // If we're out of bounds or if we've already seen this cell, return 0. if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || grid[i][j] == -1) { return 0; } // If we've reached the bottom right corner, check to see if we've seen all empty cells. If so, return 1. if (i == grid.Length - 1 && j == grid[0].Length - 1) { return numEmpty == 0 ? 1 : 0; } // Mark the current cell as seen. grid[i][j] = -1; // Try all four directions from the current cell. int paths = UniquePathsIIIHelper(grid, i - 1, j, numEmpty - 1) + UniquePathsIIIHelper(grid, i + 1, j, numEmpty - 1) + UniquePathsIIIHelper(grid, i, j - 1, numEmpty - 1) + UniquePathsIIIHelper(grid, i, j + 1, numEmpty - 1); // Mark the current cell as un-seen. grid[i][j] = 0; return paths; }