题目描述
使用bfs给每个连通块染色,并记录连通块中点的个数,然后判断每个”*”前后左右链接了多少个连通块,求和然后加上自己这个点然后%10即可
py 代码
from collections import deque
n,m = map(int,input().split())
lis = []
res = dict()
for i in range(n):lis.append(list(input()))
idx = 0
p = [[-1 for i in range(m)] for i in range(n)]
f = [[False for i in range(m)] for i in range(n)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def bfs(x):
global idx
hh = 1
q = deque()
q.append(x)
f[x[0]][x[1]] = True
p[x[0]][x[1]] = idx
while q:
a,b = q.popleft()
for i in range(4):
xx,yy = dx[i] + a,dy[i] + b
if xx < 0 or xx >= n or yy < 0 or yy >= m:continue
if f[xx][yy]:continue
if lis[xx][yy] == '*':continue
f[xx][yy] = True
q.append([xx,yy])
p[xx][yy] = idx
hh += 1
res[idx] = hh
idx += 1
ends = []
for i in range(n):
for j in range(m):
if lis[i][j] == '.'and not f[i][j]:
bfs([i,j])
if lis[i][j] == '*':ends.append((i,j))
for i,j in ends:
tt = 0
ls = ()
for k in range(4):
xx,yy = dx[k] + i,dy[k] + j
if xx < 0 or xx >= n or yy < 0 or yy >= m:continue
if p[xx][yy] == -1:continue
if lis[xx][yy] !='.':continue
if p[xx][yy] in ls:continue
ls+=(p[xx][yy],)
tt += res[p[xx][yy]]
lis[i][j] = str((tt+1)%10)
for i in range(n):print(''.join(lis[i]))