Skip to content

2257. Count Unguarded Cells in the Grid 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
 public:
  int countUnguarded(int m, int n, vector<vector<int>>& guards,
                     vector<vector<int>>& walls) {
    int ans = 0;
    vector<vector<char>> grid(m, vector<char>(n));
    vector<vector<char>> left(m, vector<char>(n));
    vector<vector<char>> right(m, vector<char>(n));
    vector<vector<char>> up(m, vector<char>(n));
    vector<vector<char>> down(m, vector<char>(n));

    for (const vector<int>& guard : guards)
      grid[guard[0]][guard[1]] = 'G';

    for (const vector<int>& wall : walls)
      grid[wall[0]][wall[1]] = 'W';

    for (int i = 0; i < m; ++i) {
      char lastCell = 0;
      for (int j = 0; j < n; ++j)
        recordOrFill(grid[i][j], lastCell, left[i][j]);
      lastCell = 0;
      for (int j = n - 1; j >= 0; --j)
        recordOrFill(grid[i][j], lastCell, right[i][j]);
    }

    for (int j = 0; j < n; ++j) {
      char lastCell = 0;
      for (int i = 0; i < m; ++i)
        recordOrFill(grid[i][j], lastCell, up[i][j]);
      lastCell = 0;
      for (int i = m - 1; i >= 0; --i)
        recordOrFill(grid[i][j], lastCell, down[i][j]);
    }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 0 && left[i][j] != 'G' && right[i][j] != 'G' &&
            up[i][j] != 'G' && down[i][j] != 'G')
          ++ans;

    return ans;
  }

 private:
  void recordOrFill(char currCell, char& lastCell, char& infoCell) {
    if (currCell == 'G' || currCell == 'W')
      lastCell = currCell;
    else
      infoCell = lastCell;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
  public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
    int ans = 0;
    char[][] grid = new char[m][n];
    char[][] left = new char[m][n];
    char[][] right = new char[m][n];
    char[][] up = new char[m][n];
    char[][] down = new char[m][n];

    for (int[] guard : guards)
      grid[guard[0]][guard[1]] = 'G';

    for (int[] wall : walls)
      grid[wall[0]][wall[1]] = 'W';

    for (int i = 0; i < m; ++i) {
      char lastCell = 0;
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 'G' || grid[i][j] == 'W')
          lastCell = grid[i][j];
        else
          left[i][j] = lastCell;
      lastCell = 0;
      for (int j = n - 1; j >= 0; --j)
        if (grid[i][j] == 'G' || grid[i][j] == 'W')
          lastCell = grid[i][j];
        else
          right[i][j] = lastCell;
    }

    for (int j = 0; j < n; ++j) {
      char lastCell = 0;
      for (int i = 0; i < m; ++i)
        if (grid[i][j] == 'G' || grid[i][j] == 'W')
          lastCell = grid[i][j];
        else
          up[i][j] = lastCell;
      lastCell = 0;
      for (int i = m - 1; i >= 0; --i)
        if (grid[i][j] == 'G' || grid[i][j] == 'W')
          lastCell = grid[i][j];
        else
          down[i][j] = lastCell;
    }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 0 && left[i][j] != 'G' && right[i][j] != 'G' && up[i][j] != 'G' &&
            down[i][j] != 'G')
          ++ans;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
  def countUnguarded(
      self,
      m: int,
      n: int,
      guards: list[list[int]],
      walls: list[list[int]],
  ) -> int:
    ans = 0
    grid = [[0] * n for _ in range(m)]
    left = [[0] * n for _ in range(m)]
    right = [[0] * n for _ in range(m)]
    up = [[0] * n for _ in range(m)]
    down = [[0] * n for _ in range(m)]

    for row, col in guards:
      grid[row][col] = 'G'

    for row, col in walls:
      grid[row][col] = 'W'

    for i in range(m):
      lastCell = 0
      for j in range(n):
        if grid[i][j] == 'G' or grid[i][j] == 'W':
          lastCell = grid[i][j]
        else:
          left[i][j] = lastCell
      lastCell = 0
      for j in range(n - 1, -1, -1):
        if grid[i][j] == 'G' or grid[i][j] == 'W':
          lastCell = grid[i][j]
        else:
          right[i][j] = lastCell

    for j in range(n):
      lastCell = 0
      for i in range(m):
        if grid[i][j] == 'G' or grid[i][j] == 'W':
          lastCell = grid[i][j]
        else:
          up[i][j] = lastCell
      lastCell = 0
      for i in range(m - 1, -1, -1):
        if grid[i][j] == 'G' or grid[i][j] == 'W':
          lastCell = grid[i][j]
        else:
          down[i][j] = lastCell

    for i in range(m):
      for j in range(n):
        if (grid[i][j] == 0 and left[i][j] != 'G' and right[i][j] != 'G' and
                up[i][j] != 'G' and down[i][j] != 'G'):
          ans += 1

    return ans