#38289: python 紀錄 BFS


BensonDC (python戰士)

學校 : 不指定學校
編號 : 240921
來源 : [1.175.217.87]
最後登入時間 :
2024-03-27 12:33:26
m372. 3. 搬家 -- 2023年10月APCS | From: [1.175.211.7] | 發表日期 : 2023-11-10 10:37

from collections import deque
def bfs(a,b):
    global visited,queue,temp
    visited[a][b]=True
    temp+=1
    queue.append((a,b))
    while queue:
        x,y=queue.popleft()
        for s,t in d[L[x][y]]:
            nx,ny=x+s,y+t
            if not 0<=nx<n or not 0<=ny<m or L[nx][ny]=='0' or visited[nx][ny]:
                continue
            elif (-s,-t) not in d[L[nx][ny]]:
                continue
            else:
                queue.append((nx,ny))
                visited[nx][ny]=True
                temp+=1
                
d={
    'X':[(1,0),(-1,0),(0,1),(0,-1)],
    'I':[(1,0),(-1,0)],
    'H':[(0,-1),(0,1)],
    'L':[(0,1),(-1,0)],
    '7':[(1,0),(0,-1)],
    'F':[(1,0),(0,1)],
    'J':[(0,-1),(-1,0)]
    }
n,m=map(int,input().split())
L=[]
for _ in range(n):
    L.append(input())
visited=[[False]*m for _ in range(n)]
queue=deque()
res=0
temp=0
for i in range(n):
    for j in range(m):
        if L[i][j]=='0' or visited[i][j]:
            continue
        temp=0
        bfs(i,j)
        res=max(res,temp)
print(res)

 
ZeroJudge Forum