Unique Paths III
shitgpt Generates wrong answer
Input: array of arrays (integers) Output: integer
Constraint: 1 <= grid.length * grid[0].length <= 20
Invariant: Walk over every nonobstacle square exactly once.
Given:
1  starting square 2  ending square 0  we can walk over 1  cannot walk over
When we encounter an obstacle go back to the previous cell and try a different path.
Goal: Return the number of 4directional walks from the starting square to the ending square. Count the possible paths from the given source to the given target.
Counting problem. There are possibly many paths that lead from source to destination.
Similar to maze problem. Look for clues in the problem space. What approach we can take to solve this problem?
When we cannot continue and we have to back to previous position start doing something else. This indicates backtracking approach.
Problem Decomposition
Subproblem #1: How do we know we have walked over all the zeroes? Count the number of zeroes in the grid. Traversal must check it has gone through all the zeroes. We can start from (0, 0) and count the number of 0s. Add an extra condition, when we hit 1, x,y => starting point of path.
Recursive Backtracking Approach
Base cases: #1. We should terminate the recursion when we see 2. #2. If we have a grid with size 1x1 return 0.
What parameters do we need for the backtrack method?
 grid
 column  Keeps track of the position
 row
 visited array (backtracking purpose)
 current_zeroes
 total_zeroes
 total_paths
Initialize visited array grid to all false in the initialization step. The backtrack method will set the visited array value for (r, c) to true. Initialize total_paths to 0. In the base case, when we hit 2, increment the total_paths by 1. Before incrementing the path counter, make sure: current_zeroes == total_zeroes (enforce the invariant) What if we make the 0 as 1. In the backtracking step, flip the grid back to 0 from 1.
directions = (r, c) + (0,1)  going to the right cell (r, c) + (1, 0)  going to the down cell (r, c) + (0, 1)  going to the left cell (r, c) + (1, 0)  going to the top cell
We need to make 4 backtracking calls for these 4 possible directions.


Input: array of arrays (integers) Output: integer
Constraint: 1 <= grid.length * grid[0].length <= 20
Invariant: Walk over every nonobstacle square exactly once.
Given:
1  starting square 2  ending square 0  we can walk over 1  cannot walk over
When we encounter an obstacle go back to the previous cell and try a different path.
Goal: Return the number of 4directional walks from the starting square to the ending square. Count the possible paths from the given source to the given target.
Counting problem. There are possibly many paths that lead from source to destination.
Similar to maze problem. Look for clues in the problem space. What approach we can take to solve this problem?
When we cannot continue and we have to back to previous position start doing something else. This indicates backtracking approach.
Problem Decomposition
Subproblem #1: How do we know we have walked over all the zeroes? Count the number of zeroes in the grid. Traversal must check it has gone through all the zeroes. We can start from (0, 0) and count the number of 0s. Add an extra condition, when we hit 1, x,y => starting point of path.
Recursive Backtracking Approach
Base cases: #1. We should terminate the recursion when we see 2. #2. If we have a grid with size 1x1 return 0.
What parameters do we need for the backtrack method?
 grid
 column  Keeps track of the position
 row
 visited array (backtracking purpose)
 current_zeroes
 total_zeroes
 total_paths
Initialize visited array grid to all false in the initialization step. The backtrack method will set the visited array value for (r, c) to true. Initialize total_paths to 0. In the base case, when we hit 2, increment the total_paths by 1. Before incrementing the path counter, make sure: current_zeroes == total_zeroes (enforce the invariant) What if we make the 0 as 1. In the backtracking step, flip the grid back to 0 from 1.
directions = (r, c) + (0,1)  going to the right cell (r, c) + (1, 0)  going to the down cell (r, c) + (0, 1)  going to the left cell (r, c) + (1, 0)  going to the top cell
We need to make 4 backtracking calls for these 4 possible directions.


Input: array of arrays (integers) Output: integer
Constraint: 1 <= grid.length * grid[0].length <= 20
Invariant: Walk over every nonobstacle square exactly once.
Given:
1  starting square 2  ending square 0  we can walk over 1  cannot walk over
When we encounter an obstacle go back to the previous cell and try a different path.
Goal: Return the number of 4directional walks from the starting square to the ending square. Count the possible paths from the given source to the given target.
Counting problem. There are possibly many paths that lead from source to destination.
Similar to maze problem. Look for clues in the problem space. What approach we can take to solve this problem?
When we cannot continue and we have to back to previous position start doing something else. This indicates backtracking approach.
Problem Decomposition
Subproblem #1: How do we know we have walked over all the zeroes? Count the number of zeroes in the grid. Traversal must check it has gone through all the zeroes. We can start from (0, 0) and count the number of 0s. Add an extra condition, when we hit 1, x,y => starting point of path.
Recursive Backtracking Approach
Base cases: #1. We should terminate the recursion when we see 2. #2. If we have a grid with size 1x1 return 0.
What parameters do we need for the backtrack method?
 grid
 column  Keeps track of the position
 row
 visited array (backtracking purpose)
 current_zeroes
 total_zeroes
 total_paths
Initialize visited array grid to all false in the initialization step. The backtrack method will set the visited array value for (r, c) to true. Initialize total_paths to 0. In the base case, when we hit 2, increment the total_paths by 1. Before incrementing the path counter, make sure: current_zeroes == total_zeroes (enforce the invariant) What if we make the 0 as 1. In the backtracking step, flip the grid back to 0 from 1.
directions = (r, c) + (0,1)  going to the right cell (r, c) + (1, 0)  going to the down cell (r, c) + (0, 1)  going to the left cell (r, c) + (1, 0)  going to the top cell
We need to make 4 backtracking calls for these 4 possible directions.

