content: package codingquestions.leetcode;
  
  /**
   * 2257. Count Unguarded Cells in the Grid
   * Solved
   * Medium
   * Topics
   * Companies
   * Hint
   * 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.
   * <p>
   * 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.
   * <p>
   * Return the number of unoccupied cells that are not guarded.
   * <p>
   * <p>
   * <p>
   * Example 1:
   * <p>
   * <p>
   * 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:
   * <p>
   * <p>
   * 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.
   * <p>
   * <p>
   * Constraints:
   * <p>
   * 1 <= m, n <= 105
   * 2 <= m * n <= 105
   * 1 <= guards.length, walls.length <= 5 * 104
   * 2 <= guards.length + walls.length <= m * n
   * guards[i].length == walls[j].length == 2
   * 0 <= rowi, rowj < m
   * 0 <= coli, colj < n
   * All the positions in guards and walls are unique.
   */
  
  public class CountUnguardedCellsintheGrid {
  
      public static void main(String[] args) {
          CountUnguardedCellsintheGrid cuc = new CountUnguardedCellsintheGrid();
          System.out.println(cuc.countUnguarded(4, 6, new int[][]{{0, 0}, {1, 1}, {2, 3}}, new int[][]{{0, 1}, {1, 0}, {2, 1}, {1, 2}}));
      }
  
      public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
          // Initialize grid with zeros
          int[][] g = new int[m][n];
  
          // Mark guards and walls as 2
          for (int[] e : guards) {
              g[e[0]][e[1]] = 2;
          }
          for (int[] e : walls) {
              g[e[0]][e[1]] = 2;
          }
  
          // Directions: up, right, down, left
          int[] dirs = {-1, 0, 1, 0, -1};
  
          // Process each guard's line of sight
          for (int[] e : guards) {
              for (int k = 0; k < 4; ++k) {
                  int x = e[0], y = e[1];
                  int dx = dirs[k], dy = dirs[k + 1];
  
                  // Check cells in current direction until hitting boundary or obstacle
                  while (x + dx >= 0 && x + dx < m && y + dy >= 0 && y + dy < n && g[x + dx][y + dy] < 2) {
                      x += dx;
                      y += dy;
                      g[x][y] = 1;
                  }
              }
          }
  
          // Count unguarded cells (cells with value 0)
          int unguardedCount = 0;
          for (int i = 0; i < m; i++) {
              for (int j = 0; j < n; j++) {
                  if (g[i][j] == 0) {
                      unguardedCount++;
                  }
              }
          }
          return unguardedCount;
  
      }
  }
  