Count Unguarded Cells in the Grid (recursion)

Question

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

Answer 1

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

Answer 2

This code is the problem:

# Recursive call
dfs(grid, row + 1, col)
dfs(grid, row - 1, col)

On the very first call from the main function, dfs iscalled with row=0.

Here is a crude flow of the subsequent recursive calls, with recursion levels represented by indentation:

With row=0, dfs calls itself with row + 1

    With row=1, dfs calls itself with row + 1

        With row=2, dfs calls itself with row + 1

            With row=3, dfs calls itself with row + 1

                With row=4, it is out of bounds (no more calls)

            With row=3, dfs calls itself with row - 1

                With row=2, dfs calls itself with row + 1

                    With row=3, dfs calls itself with row + 1

                        With row=4, it is out of bounds (no more calls)

                    With row=3, dfs calls itself with row - 1

                        With row=2, dfs calls itself with row + 1

... and so on and so on. row just keeps cycling back and forth at 2,3,4,2,3,4,2,3,4.... forever.

I don't understand why you are calling dfs with row-1 anyway, because that row will either be out of bounds, or it will be a row you have already checked on a previous call.