图论题1

一个很经典的图论题，写法如下

点击查看代码

first=set()
second=set()
directions=[[0,1],[1,0],[0,-1],[-1,0]]
def dfs(i,j,graph,vis,side):if vis[i][j]:returnvis[i][j]=Trueside.add((i,j))for dir in directions:new_x=i+dir[0]new_y=j+dir[1]if (0<=new_x<len(graph)and 0<=new_y<len(graph[0])and graph[i][j]<=graph[new_x][new_y]):dfs(new_x,new_y,graph,vis,side)
n,m=map(int,input().split())
graph=[]
for i in range(n):a=list(map(int,input().split()))graph.append(a)
vis=[[False]*n for _ in range(m)]
for i in range(n):dfs(i,0,graph,vis,first)
for j in range(m):dfs(0,j,graph,vis,first)
vis=[[False]*n for _ in range(m)]
for i in range(n):dfs(i,m-1,graph,vis,second)
for j in range(m):dfs(n-1,j,graph,vis,second)
res=first&second
for x,y in res:print(f"{x} {y}")