from collections import deque
def f():
N,M=map(int,input().split())
mat=[]
sums=0
directions=[(0,1),(0,-1),(1,0),(-1,0)]
for _ in range(N):
mat.append(list(map(int,input().split())))
sums+=sum(mat[-1])
def bfs(i,j,N,M):
q=deque([(i,j)])
idx=[]
cnt=0
while q:
cur=q.popleft()
mat[cur[0]][cur[1]]=2
cnt+=1
idx.append(cur)
for dx,dy in directions:
x,y=cur[0]+dx,cur[1]+dy
if 0<=x<N and 0<=y<M and mat[x][y]==1:
q.append((x,y))
return (cnt,idx)
lands=[]
for i in range(N):
for j in range(M):
if mat[i][j]==1:
lands.append(bfs(i,j,N,M))
lands.sort()
mat2=[[(0,-1) for _ in range(M)] for _ in range(N)]
for i,(cnt,idx) in enumerate(lands):
for x,y in idx:
mat2[x][y]=(cnt,i)
# for l in mat2:
# print(l)
res=0
for i in range(N):
for j in range(M):
if mat2[i][j]==(0,-1):
tmp=1
appeared=set()
for dx, dy in directions:
x, y = i + dx, j + dy
if 0 <= x < N and 0 <= y < M and mat2[x][y][1] not in appeared:
tmp+=mat2[x][y][0]
appeared.add(mat2[x][y][1])
# if res==10:print(i,j)
# print(tmp)
res=max(res,tmp)
res=min(res,sums)
print(res)
f()
拜托了，另一个我
全部评论
(1) 回帖