import sys
input = sys.stdin.readline
from collections import *
N,M,H = map(int,input().split())
tank = [[H]*M for i in range(N)]
column = [[*map(int,input().split())] for i in range(N+1)]
row = [[*map(int,input().split())] for i in range(N)]
dq = [deque() for i in range(H+1)]
for y in range(N):
if row[y][0]!=-1:
dq[row[y][0]].append((y,0))
if row[y][-1]!=-1:
dq[row[y][-1]].append((y,M-1))
for x in range(M):
if column[0][x]!=-1:
dq[column[0][x]].append((0,x))
if column[-1][x]!=-1:
dq[column[-1][x]].append((N-1,x))
for h in range(H+1):
while dq[h]:
y,x = dq[h].pop()
if tank[y][x] <= h:
continue
tank[y][x] = h
if row[y][x]!=-1 and x:
if row[y][x]<=h:
dq[h].append((y,x-1))
else:
dq[row[y][x]].append((y,x-1))
if row[y][x+1]!=-1 and x+1<M:
if row[y][x+1]<=h:
dq[h].append((y,x+1))
else:
dq[row[y][x+1]].append((y,x+1))
if column[y][x]!=-1 and y:
if column[y][x]<=h:
dq[h].append((y-1,x))
else:
dq[column[y][x]].append((y-1,x))
if column[y+1][x]!=-1 and y+1<N:
if column[y+1][x]<=h:
dq[h].append((y+1,x))
else:
dq[column[y+1][x]].append((y+1,x))
print(sum(map(sum,tank)))
BFS로 해결하였다.
수영장 사장님 [백준 15730번] 수영장 사장님 (Python3) (tistory.com) 과 사실상 완전히 똑같은 방식으로 해결할 수 있다. 수영장 사장님 문제에서는 각 좌표가 그 자체로서 벽의 역할을 했다면, 이 문제에서는 벽이 각 좌표의 4방향에 존재한다는 것이 차이점이다.
풀이를 설명하면,
1. 높이 0~H까지 H+1개의 deque를 만든다.
2. 가장 바깥쪽을 높이 0의 물이라고 생각하고 h=0~H까지 H+1번 BFS를 실행한다.
3. 각 좌표에서 4방향에 대해서 경계를 이루는 벽의 높이가 현재 높이 h보다 작은 경우 해당 좌표를 현재 deque에 넣고, 더 큰 경우, 해당 높이의 deque에 넣는다.
4. 물 높이의 합을 출력한다.
다른 사람들 풀이를 보니 우선순위 큐를 이용한 풀이가 많아보였다. 우선순위 큐를 이용한 풀이도 나쁜 방법은 아니지만 우선순위 큐의 사용으로 인해 시간복잡도가 O(NMlogNM)이 되는 반면, 내 풀이는 O(NM)으로 해결가능하다.
파이썬 기준, 성능에서 우선순위 큐를 이용한 다른 사람들 풀이보다 압도적으로 빠른 것을 알 수 있다.