AcWing 687. 扫雷
原题链接
简单
作者:
喜欢日奈大可爱
,
2024-04-08 21:10:54
,
所有人可见
,
阅读 1
python3 bfs
t = int(input())
for k in range(t):
def bfs(i, j):
dist[i][j] = 1
q = []
q.append([i, j])
while (len(q)):
t = q.pop(0)
for i in range(-1, 2):
for j in range(-1, 2):
x = t[0] + i
y = t[1] + j
if (x >= 0) and (x < n) and (y >= 0) and (y < n) and (g[x][y] == 0)and (dist[x][y]==0):
q.append([x, y])
dist[x][y] = 1
def check(i, j):
for a in range(-1, 2):
for b in range(-1, 2):
x = a + i
y = b + j
if (x >= 0) and (x < n) and (y >= 0) and (y < n) and (g[x][y]==0):
return False
return True
n = int(input())
g = [[0 for i in range(n)] for j in range(n)]
str = []
dist = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
a = input()
str.append([i for i in a])
for i in range(n):
for j in range(n):
if str[i][j] == '*':
g[i][j] = -1
else:
g[i][j] = 0
for a in range(-1, 2):
for b in range(-1, 2):
x = a + i
y = b + j
if (x >= 0) and (x < n) and (y >= 0) and (y < n) and (str[x][y] == '*'):
g[i][j] += 1
res = 0
for i in range(n):
for j in range(n):
if g[i][j] == 0 and dist[i][j] == 0:
bfs(i, j)
res += 1
if g[i][j] != 0 and g[i][j] != -1:
if check(i, j):
res += 1
print(f"Case #{k+1}: {res}")