1402. 星空之夜【Python实现】
Date:3.21
Key;BFS、哈希
思路
整体框架就是BFS求连通块FloodFill操作,但是这题难点在于,如何把相似的图形映射到相同的值上,也即判断图形的同构问题:
计算构成图形的任意两个坐标之间的距离之和(float),所有同构的图形的这一值均会相同,这个规律可以观察题干中的例子来得到,并且可以通过思考为什么会对每一连通块的大小进行限制。实现细节:abs(x-y)<1e-6时,可以认为x等于y
【特别注意】不能直接用距离的平方之和(int)来做判断,会出现误判的情况,反例可自举
代码
from sys import stdin
from math import sqrt
input = lambda: stdin.readline()
W = int(input())
H = int(input())
mp = [[''for _ in range(W)]for _ in range(H)]
for i in range(H):
s = input()
for j in range(W):
mp[i][j] = s[j]
def isValid(x, y):
if x < 0 or x >= H: return False
if y < 0 or y >= W: return False
return True
def getDis(x, y, xx, yy):
return sqrt((x-xx)**2+(y-yy)**2)
def getHash(lis):
res = 0
for i in range(len(lis)):
(x, y) = lis[i]
for j in range(i + 1, len(lis)):
(xx, yy) = lis[j]
res += getDis(x, y, xx, yy)
return res
visited = [[0 for _ in range(W)]for _ in range(H)]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
M = dict()
flag = 97
for i in range(H):
for j in range(W):
if visited[i][j]: continue
if mp[i][j] == '0': continue
lis = []
q = [(i, j)]
visited[i][j] = 1
while len(q) > 0:
(x, y) = q.pop(0)
lis.append((x, y))
for k in range(8):
xx = x + dx[k]
yy = y + dy[k]
if isValid(xx, yy) is False: continue
if visited[xx][yy]: continue
if mp[xx][yy] == '0': continue
visited[xx][yy] = 1
q.append((xx, yy))
sz = getHash(lis)
hav = 0
for obj in M.keys():
if abs(obj - sz) < 1e-6:
hav = 1
sz = obj
break
if hav == 0:
M[sz] = flag
flag += 1
fl = chr(M[sz])
for x,y in lis:
mp[x][y] = str(fl)
for i in range(H):
print(''.join(mp[i][:W]))