class Solution:
def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
grid = [[0] * n for _ in range(m)] # 网格状态数组
q = deque([]) # 广度优先搜索队列
# 每个方向的单位向量
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i, j in guards:
grid[i][j] = -1
for k in range(4):
# 将四个方向视线对应的状态均添加进搜索队列中
q.append((i, j, k))
for i, j in walls:
grid[i][j] = -2
while q:
x, y, k = q.popleft()
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] >= 0:
# 沿着视线方向的下一个坐标合法，且不为警卫或墙
if grid[nx][ny] & (1 << k) == 0:
# 对应状态未遍历过
grid[nx][ny] |= (1 << k)
q.append((nx, ny, k))
res = 0 # 未被保护格子数目
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
res += 1
return res
func countUnguarded(m, n int, guards, walls [][]int) (ans int) {
// 构建网格
a := make([][]int, m)
for i := range a {
a[i] = make([]int, n)
}
for _, p := range guards { a[p[0]][p[1]] = 1 }
for _, p := range walls { a[p[0]][p[1]] = 2 }
// 按行模拟
for _, row := range a {
for j := 0; j < n; j++ {
if row[j] == 2 { continue }
st, has1 := j, false
// 注意这里的 j 和外层循环的 j 是同一个变量
for ; j < n && row[j] != 2; j++ {
if row[j] == 1 {
has1 = true
}
}
if has1 {
for ; st < j; st++ {
if row[st] == 0 {
row[st] = -1 // 能被保卫
}
}
}
}
}
// 按列模拟
for j := 0; j < n; j++ {
for i := 0; i < m; i++ {
if a[i][j] == 2 { continue }
st, has1 := i, false
// 注意这里的 i 和外层循环的 i 是同一个变量
for ; i < m && a[i][j] != 2; i++ {
if a[i][j] == 1 {
has1 = true
}
}
if has1 {
for ; st < i; st++ {
if a[st][j] == 0 {
a[st][j] = -1
}
}
}
}
}
// 统计答案
for _, row := range a {
for _, v := range row {
if v == 0 {
ans++
}
}
}
return
}
