AcWing 1106. 山峰和山谷
原题链接
中等
作者:
叶枝黎曼
,
2020-11-04 21:02:42
,
所有人可见
,
阅读 369
flood fil边界值问题
利用flood fill处理边界值
问题的难度在于对于每一个连通区域,判断与之相接的边界是否满足要求
在判断边界的时候,利用是否存在,反相判断是否完全没有(例如:判断是否存在高于来判断是否完全低于)
python版本
from collections import deque
def bfs(i,j):
global hasH,hasL
queue = deque()
queue.append((i,j))
vis[i][j] = True
while queue:
sam = queue.popleft()
x = sam[0]
y = sam[1]
for var in ways:
n_x = x + var[0]
n_y = y + var[1]
if n_x >= 0 and n_x < n and n_y >= 0 and n_y < n:
if board[n_x][n_y] > board[x][y]:
hasH = True
elif board[n_x][n_y] < board[x][y]:
hasL = True
elif vis[n_x][n_y] == False:
queue.append((n_x,n_y))
vis[n_x][n_y] = True
ways = [(0,1),(0,-1),(-1,0),(1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
n = int(input())
board = []
for i in range(n):
board.append([int(i) for i in input().split()])
vis = [[False]*(n + 1) for i in range(n + 1)]
di = 0
gao = 0
for i in range(n):
for j in range(n):
hasH = False
hasL = False
if vis[i][j] == False:
bfs(i,j)
if hasH == False:
di += 1
if hasL == False:
gao += 1
print(di,gao)