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.

&nbsp;
Example 1:

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.


Example 2:

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.


&nbsp;
Constraints:


	1 &lt;= m, n &lt;= 105
	2 &lt;= m * n &lt;= 105
	1 &lt;= guards.length, walls.length &lt;= 5 * 104
	2 &lt;= guards.length + walls.length &lt;= m * n
	guards[i].length == walls[j].length == 2
	0 &lt;= rowi, rowj &lt; m
	0 &lt;= coli, colj &lt; n
	All the positions in guards and walls are unique.


class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        dp = [[0] * n for _ in range(m)]
        for x, y in guards+walls:
            dp[x][y] = 1
               
        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
        
        for x, y in guards:
            for dx, dy in directions:
                curr_x = x
                curr_y = y
                
                while 0 <= curr_x+dx < m and 0 <= curr_y+dy < n and dp[curr_x+dx][curr_y+dy] != 1:
                    curr_x += dx
                    curr_y += dy
                    dp[curr_x][curr_y] = 2
                    
        return sum(1 for i in range(m) for j in range(n) if dp[i][j] == 0)                    
class Solution
{
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls)
    {
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        char[][] grid= new char[m][n];
        int count = m*n - guards.length - walls.length;
        for(int[] wall : walls)
        {
            int x = wall[0], y = wall[1];
            grid[x][y] = 'W';
        }
        for(int[] guard : guards)
        {
            int x = guard[0], y = guard[1];
            grid[x][y] = 'G';
        }
        for(int[] point : guards)
        {
            for(int dir[] : dirs)
            {
                int x = point[0] + dir[0];
                int y = point[1] + dir[1];
                while(!(x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == 'G' || grid[x][y] == 'W'))
                {
                    if(grid[x][y] != 'P')
                        count--;
                    grid[x][y] = 'P';
                    x += dir[0];
                    y += dir[1];
                }
            }
        }
        return count;
    }
}
class Solution {
public:
    void dfs( vector<vector<int>> &grid,int x,int y,int m,int n,int dir){
        if(x<0 || y<0 || x>=m || y>=n) return;
        if(grid[x][y]==2 || grid[x][y]==1) return;
        grid[x][y]=3;
        if(dir==1){
            dfs(grid,x+1,y,m,n,dir);
        }
        else if(dir==2){
            dfs(grid,x,y+1,m,n,dir);
        }
        else if(dir==3){
            dfs(grid,x-1,y,m,n,dir);
        }
        else{
            dfs(grid,x,y-1,m,n,dir);
        }
    }
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
         vector<vector<int>> grid(m,vector<int>(n,0));
        //marking guards
        for(int i=0;i<guards.size();i++){
            int x=guards[i][0];
            int y=guards[i][1];
            grid[x][y]=1;
        }
        // marking walls
         for(int i=0;i<walls.size();i++){
            int x=walls[i][0];
            int y=walls[i][1];
            grid[x][y]=2;
        }
        // dfs in each of 4 directions
          for(int i=0;i<guards.size();i++){
            int x=guards[i][0];
            int y=guards[i][1];
              dfs(grid,x+1,y,m,n,1);
              dfs(grid,x,y+1,m,n,2);
              dfs(grid,x-1,y,m,n,3);
              dfs(grid,x,y-1,m,n,4);
          }
        long long int cnt=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0) cnt++;
            }
        }
        return cnt;
    }
};
var countUnguarded = function(m, n, guards, walls) {
    let board = new Array(m).fill(0).map(_=>new Array(n).fill(0))
    
    // 0 - Empty
    // 1 - Guard
    // 2 - Wall
    // 3 - Guard view
    
    const DIRECTIONS = [
        [-1, 0],
        [0, 1],
        [1, 0],
        [0, -1]
    ]
    
    for(let [guardRow, guardCol] of guards) board[guardRow][guardCol] = 1
    
    for(let [wallRow, wallCol] of walls) board[wallRow][wallCol] = 2
    
    for(let [guardRow, guardCol] of guards){
        //Loop through row with the same col
        //Go down from current row
        let row = guardRow + 1
        while(row < m){
            //Stop if you encounter a wall or guard
            if(board[row][guardCol] == 1 || board[row][guardCol] == 2) break
            board[row][guardCol] = 3
            row++
        }
        //Go up from current row
        row = guardRow - 1
        while(row >= 0){
            if(board[row][guardCol] == 1 || board[row][guardCol] == 2) break
            board[row][guardCol] = 3
            row--
        }
        
        
        //Loop through col with the same row
        //Go right from current col
        let col = guardCol + 1
        while(col < n){
            if(board[guardRow][col] == 1 || board[guardRow][col] == 2) break
            board[guardRow][col] = 3
            col++
        }
        
        //Go left from current col
        col = guardCol - 1
        while(col >= 0){
            if(board[guardRow][col] == 1 || board[guardRow][col] == 2) break
            board[guardRow][col] = 3
            col--
        }
    }
    
	//Count the free cells
    let freeCount = 0
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(board[i][j] == 0) freeCount++
        }
    }
    
    return freeCount
};
Count Unguarded Cells in the Grid