it's a semi-popular leetcode question. And I know there are a lot of solutions online, but I am practicing by solving all these problems myself to really master recursion. I am wondering what's wrong with my current approach; I keep maxing out the call stack. I would appreciate feedback! Here's the question:
"You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [rowi, coli] and walls[j] = [rowj, colj] represent the positions of the ith guard and jth wall respectively.
A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.
Return the number of unoccupied cells that are not guarded.
Example
Input:
m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output:
"7"
Here's the code I've written so far:
def countUnguarded(m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
def dfs(grid, row, col):
if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] == 'W':
return
# Mark cell as watched
print("marking")
grid[row][col] = '1'
# Recursive call
dfs(grid, row + 1, col)
dfs(grid, row - 1, col)
dfs(grid, row, col + 1)
dfs(grid, row, col - 1)
grid = [['0'] * n for _ in range(m)]
# Update grid to mark guards as 'G'
for guard in guards:
row, col = guard
grid[row][col] = 'G'
# Update grid to mark walls as 'W'
for wall in walls:
row, col = wall
grid[row][col] = 'W'
# Run dfs for each cell with Guard
for row in range(m):
for col in range(n):
if grid[row][col] == 'G':
print(f"running DFS at point {row, col}")
dfs(grid, row, col)
# count result
unguarded_count = 0
for row in range(m):
for col in range(n):
if grid[row][col] == '0':
unguarded_count += 1
return unguarded_count
For the comments saying dfs isn't necessary, sure I guess it isn't. But technically the only necessary solution is the most perfect and most optimized. The solution I propose below beats 75% of submissions on leetcode. As I said, this was to practice recursion and not just to solve the problem.
Here's the modified code of what I submitted in the question. The key mistake I was making was trying to recursively move in all directions in a single iteration. By doing that, my recursive function may not return to the point of the current G being iterated over which may yield to incorrect results or a maximized call stack. That and the fact that my base case was not correct.
Recursively moving in just one direction, exiting the call stack with a return and then recursively moving in the next direction, yields the correct and efficient result.
def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
def dfs(grid, row, col, direction):
nonlocal unguarded
if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] in ['W', 'G']:
return
# Mark cell as watched
if grid[row][col] != 'G' and grid[row][col] != '1':
grid[row][col] = '1'
unguarded -= 1
# Recursive calls in just one direction
if direction == "up":
dfs(grid, row - 1, col, direction)
elif direction == "down":
dfs(grid, row + 1, col, direction)
elif direction == "right":
dfs(grid, row, col + 1, direction)
elif direction == "left":
dfs(grid, row, col - 1, direction)
grid = [['0'] * n for _ in range(m)]
#init unguarded count to total area of grid then decrease
#based on wall, guard and eye-path of guard (dfs on g)
unguarded = m * n
# Update grid to mark guards as 'G'
for guard in guards:
row, col = guard
grid[row][col] = 'G'
unguarded -= 1
# Update grid to mark walls as 'W'
for wall in walls:
row, col = wall
grid[row][col] = 'W'
unguarded -= 1
# Run dfs for each cell with Guard
for row in range(m):
for col in range(n):
if grid[row][col] == 'G':
dfs(grid, row-1, col, "up")
dfs(grid, row+1, col, "down")
dfs(grid, row, col-1, "left")
dfs(grid, row, col+1, "right")
return unguarded