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 non-obstacle 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 4-directional 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

def backtrack(grid, r, c, current_zeroes, total_zeroes)
   if (r < 0 || r >= grid.size) || (c < 0 || c >= grid[0].size)
       return
   end
   
   if grid[r][c] == -1
       return
   end
   if grid[r][c] == 0
       current_zeroes += 1
   end
    
   if (grid[r][c] == 2)
       if (current_zeroes == total_zeroes) 
          @total_paths += 1
       end

       return
   end
    
   temp = grid[r][c]
   grid[r][c] = -1

   backtrack(grid, r, c+1, current_zeroes, total_zeroes) 
   backtrack(grid, r+1, c, current_zeroes, total_zeroes)
   backtrack(grid, r, c-1, current_zeroes, total_zeroes)
   backtrack(grid, r-1, c, current_zeroes, total_zeroes) 
   
   grid[r][c] = temp    
end

# @param {Integer[][]} grid
# @return {Integer}
def unique_paths_iii(grid)
   rows = grid.size
   cols = grid[0].size
    
   r = 0
   c = 0
   current_zeroes = 0 
   total_zeroes = 0
   @total_paths = 0
    
   for i in (0...rows)
      for j in (0...cols)
         if grid[i][j] == 0
             total_zeroes += 1
         end
         if grid[i][j] == 1
             r = i
             c = j
         end
      end
   end
   backtrack(grid, r, c, current_zeroes, total_zeroes)
   @total_paths 
end

Input: array of arrays (integers) Output: integer

Constraint: 1 <= grid.length * grid[0].length <= 20

Invariant: Walk over every non-obstacle 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 4-directional 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

def backtrack(grid, r, c, current_zeroes, total_zeroes)
   if (r < 0 || r >= grid.size) || (c < 0 || c >= grid[0].size)
       return
   end
   
   if grid[r][c] == -1
       return
   end
   if grid[r][c] == 0
       current_zeroes += 1
   end
    
   if (grid[r][c] == 2)
       if (current_zeroes == total_zeroes) 
          @total_paths += 1
       end

       return
   end
    
   temp = grid[r][c]
   grid[r][c] = -1
    
   backtrack(grid, r, c+1, current_zeroes, total_zeroes) 
   backtrack(grid, r+1, c, current_zeroes, total_zeroes)
   backtrack(grid, r, c-1, current_zeroes, total_zeroes)
   backtrack(grid, r-1, c, current_zeroes, total_zeroes) 
   
   grid[r][c] = temp

   return 
end

# @param {Integer[][]} grid
# @return {Integer}
def unique_paths_iii(grid)
   rows = grid.size
   cols = grid[0].size

   r = 0
   c = 0
   current_zeroes = 0 
   total_zeroes = 0
   @total_paths = 0

   # if rows == 1 && cols == 1
   #     return 0
   # end

   for i in (0...rows)
      for j in (0...cols)
         if grid[i][j] == 0
             total_zeroes += 1
         end
         if grid[i][j] == 1
             r = i
             c = j
         end
      end
   end
   backtrack(grid, r, c, current_zeroes, total_zeroes)
   @total_paths 
end

Input: array of arrays (integers) Output: integer

Constraint: 1 <= grid.length * grid[0].length <= 20

Invariant: Walk over every non-obstacle 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 4-directional 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

def backtrack(grid, r, c, current_zeroes, total_zeroes)
   if (r < 0 || r >= grid.size) || (c < 0 || c >= grid[0].size)
       return
   end
   
   if grid[r][c] == -1
       return
   end
   if grid[r][c] == 0
       current_zeroes += 1
   end

   if (grid[r][c] == 2)
       if (current_zeroes == total_zeroes) 
          @total_paths += 1
       end

       return
   end
    
   temp = grid[r][c]
   grid[r][c] = -1

   backtrack(grid, r, c+1, current_zeroes, total_zeroes) 
   backtrack(grid, r+1, c, current_zeroes, total_zeroes)
   backtrack(grid, r, c-1, current_zeroes, total_zeroes)
   backtrack(grid, r-1, c, current_zeroes, total_zeroes) 
   
   grid[r][c] = temp

   return 
end

# @param {Integer[][]} grid
# @return {Integer}
def unique_paths_iii(grid)
   rows = grid.size
   cols = grid[0].size

   r = 0
   c = 0
   current_zeroes = 0 
   total_zeroes = 0
   @total_paths = 0

   if rows == 1 && cols == 1
       return 0
   end

   for i in (0...rows)
      for j in (0...cols)
         if grid[i][j] == 0
             total_zeroes += 1
         end
         if grid[i][j] == 1
             r = i
             c = j
         end
      end
   end
   backtrack(grid, r, c, current_zeroes, total_zeroes)
   @total_paths 
end