Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2257.html

2257. Count Unguarded Cells in the Grid

  • Difficulty: Medium.
  • Related Topics: Array, Matrix, Simulation.
  • Similar Questions: Bomb Enemy, Available Captures for Rook.

Problem

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 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.

  Constraints:

  • 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.

Solution (Java, C++, Python)

  • class Solution {
        public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
            char[][] matrix = new char[m][n];
            int result = 0;
            for (int i = 0; i <= guards.length - 1; i++) {
                int guardRow = guards[i][0];
                int guardCol = guards[i][1];
                matrix[guardRow][guardCol] = 'G';
            }
            for (int i = 0; i <= walls.length - 1; i++) {
                int wallRow = walls[i][0];
                int wallCol = walls[i][1];
                matrix[wallRow][wallCol] = 'W';
            }
            for (int i = 0; i <= guards.length - 1; i++) {
                int currentRow = guards[i][0];
                int currentCol = guards[i][1] - 1;
                while (currentCol >= 0) {
                    if (matrix[currentRow][currentCol] != 'W'
                            && matrix[currentRow][currentCol] != 'G') {
                        matrix[currentRow][currentCol] = 'R';
                    } else {
                        break;
                    }
                    currentCol--;
                }
                currentRow = guards[i][0];
                currentCol = guards[i][1] + 1;
                while (currentCol <= n - 1) {
                    if (matrix[currentRow][currentCol] != 'W'
                            && matrix[currentRow][currentCol] != 'G') {
                        matrix[currentRow][currentCol] = 'R';
                    } else {
                        break;
                    }
                    currentCol++;
                }
                currentRow = guards[i][0] - 1;
                currentCol = guards[i][1];
                while (currentRow >= 0) {
                    if (matrix[currentRow][currentCol] != 'W'
                            && matrix[currentRow][currentCol] != 'G') {
                        matrix[currentRow][currentCol] = 'R';
                    } else {
                        break;
                    }
                    currentRow--;
                }
                currentRow = guards[i][0] + 1;
                currentCol = guards[i][1];
                while (currentRow <= m - 1) {
                    if (matrix[currentRow][currentCol] != 'W'
                            && matrix[currentRow][currentCol] != 'G') {
                        matrix[currentRow][currentCol] = 'R';
                    } else {
                        break;
                    }
                    currentRow++;
                }
            }
            for (int i = 0; i <= m - 1; i++) {
                for (int j = 0; j <= n - 1; j++) {
                    if (matrix[i][j] != 'R' && matrix[i][j] != 'G' && matrix[i][j] != 'W') {
                        result++;
                    }
                }
            }
            return result;
        }
    }
    
  • Todo
    
  • class Solution:
        def countUnguarded(
            self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]
        ) -> int:
            g = [[None] * n for _ in range(m)]
            for r, c in guards:
                g[r][c] = 'g'
            for r, c in walls:
                g[r][c] = 'w'
            for i, j in guards:
                for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                    x, y = i, j
                    while (
                        0 <= x + a < m
                        and 0 <= y + b < n
                        and g[x + a][y + b] != 'w'
                        and g[x + a][y + b] != 'g'
                    ):
                        x, y = x + a, y + b
                        g[x][y] = 'v'
            return sum(not v for row in g for v in row)
    
    ############
    
    # 2257. Count Unguarded Cells in the Grid
    # https://leetcode.com/problems/count-unguarded-cells-in-the-grid
    
    class Solution:
        def countUnguarded(self, rows: int, cols: int, guards: List[List[int]], walls: List[List[int]]) -> int:
            grid = [[1] * cols for _ in range(rows)]
            
            for x, y in walls:
                grid[x][y] = -1
                
            def goLeft(x, y):
                dy = y - 1
                while dy >= 0 and grid[x][dy] != 2 and grid[x][dy] != -1:
                    grid[x][dy] = 2
                    dy -= 1
            
            def goRight(x, y):
                dy = y + 1
                while dy < cols and grid[x][dy] != 3 and grid[x][dy] != -1:
                    grid[x][dy] = 3
                    dy += 1
                    
            def goTop(x, y):
                dx = x - 1
                while dx >= 0 and grid[dx][y] != 4 and grid[dx][y] != -1:
                    grid[dx][y] = 4
                    dx -= 1
                    
            def goBottom(x, y):
                dx = x + 1
                while dx < rows and grid[dx][y] != 5 and grid[dx][y] != -1:
                    grid[dx][y] = 5
                    dx += 1
        
            guards.sort(key = lambda x : (-x[1], x[0]))
    
            for x, y in guards:
                goLeft(x, y)
    
            guards.sort(key = lambda x : (x[1], x[0]))
    
            for x, y in guards:
                goRight(x, y)
            
            guards.sort(key = lambda x : (-x[0], x[1]))
            for x, y in guards:
                goTop(x, y)
    
            guards.sort(key = lambda x : (x[0], x[1]))
            for x, y in guards:
                goBottom(x, y)
    
            for x, y in guards:
                grid[x][y] = -1
            
            res = 0
            
            for x in range(rows):
                for y in range(cols):
                    if grid[x][y] == 1:
                        res += 1
            
            return res
    
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions