import sys
input = sys.stdin.readline
from collections import deque
import copy
dy = [1,-1,0,0]
dx = [0,0,1,-1]
N,M,T = map(int,input().split())
room = []
for i in range(N):
room.append(list(map(int,input().split())))
def spread():
dq = deque()
for i in range(N):
for j in range(M):
if room[i][j]==-1 or room[i][j]==0:
continue
s = room[i][j]//5
count = 0
for k in range(4):
y = i+dy[k]
x = j+dx[k]
if y>=0 and y<N and x>=0 and x<M:
if room[y][x] == -1:
continue
count += 1
dq.append((s,y,x))
room[i][j] -= s*count
while dq:
s,y,x = dq.pop()
room[y][x] += s
def airclean(x):
dq = deque()
dq.append((x,1,0))
dq.append((x+1,1,0))
for i in range(1,M): #첫째 가로줄
dq.append((0,i-1,room[0][i]))
for i in range(1,M-1): #공기청정기 윗부분 가로줄
dq.append((x,i+1,room[x][i]))
for i in range(x): #세로줄
dq.append((i+1,0,room[i][0]))
for i in range(1,x+1): #맨끝 세로줄
dq.append((i-1,M-1,room[i][M-1]))
for i in range(1,M):
dq.append((N-1,i-1,room[N-1][i]))
for i in range(1,M-1):
dq.append((x+1,i+1,room[x+1][i]))
for i in range(x+1,N):
dq.append((i-1,0,room[i][0]))
for i in range(x+1,N-1):
dq.append((i+1,M-1,room[i][M-1]))
while dq:
y1,x1,s = dq.pop()
room[y1][x1] = s
room[x][0] = room[x+1][0] = -1
for i in range(N):
if room[i][0] == -1:
cleaner = i
break
for i in range(T):
spread()
airclean(cleaner)
result = 0
for i in room:
result += sum(i)
print(result+2)
코드가 좀 지저분해서 이게 맞나 싶었는데 맞더라
airclean 함수를 재귀함수로 좀 간단하게 할 수 없을까 고민해봤는데, 짜려면 짤 순 있는데 그거나 for문 때려박는거나 별다를게 없을거같아서 그만뒀다.
deepcopy를 안쓰려고 deque로 일단 값을 다 저장한 후에 나중에 불러오는 방법을 사용했는데 (먼지가 한번에 확산해야 하므로) 다른 사람들 풀이 보니까 그냥 0으로된 리스트 이용하는 방법이 더 나은거 같기도 하다.
오늘의 교훈) 굳이 제한이 빡빡하지 않다면 대충 지저분한 함수로 풀자