공기 청정기

시간제한 3초

문제

강의실의 쾌적한 공기 상태를 보장하기 위해 공기청정기를 설치했다. 어느날, 공기청정기가 제대로 동작하는지 궁금해진 영진은 현재 강의실의 공기상태를 알아내는 프로그램을 만들었다. 편의상 강의실 내부는 격자판으로 그려지고, 각 칸에는 공기의 나쁨 정도를 숫자로 표현하도록 제작되었다. 매초 확산이 먼저 일어나고 공기청정기가 작동한다 가정하자.

[그림 1]

해당 프로그램에서 공기의 확산 특징은 다음과 같다.

• 공기는 현재 위치에서 x, y좌표와의 거리가 1이상 k이하인 위치들로 확산된다. 두 점 (x1, y1), (x2, y2)의 거리는 |x1-x2| + |y1-y2|로 구한다. 만약 확산할 좌표가 존재하지 않거나, 공기청정기 위치일 경우 해당 위치로는 퍼지지 않는다.
• 공기의 나쁨 정도가 2k2 + 2k + 1보다 작을 경우 확산이 일어나지 않는다.
• 공기의 확산이 일어났을때, 퍼지는 나쁨 정도는 기준 위치에서 2kk + 2*k + 1로 나눈 몫이다.
• 확산을 일으킨 후의 기준 위치의 공기의 나쁨 정도는 (현재 공기의 나쁨 정도) - (퍼진 공기의 나쁨 정도)*(확산된 칸의 수)이다.
• 하나의 칸에 두 공기가 확산되어 왔을 경우, 확산된 나쁨 정도를 합한다.
• 공기는 1초에 한 번씩 확산이 된다.

[그림 2]

공기청정기의 동작 방식 및 특징은 다음과 같다.

• 공기청정기는 항상 강의실 오른쪽 벽면에 설치되어있고, 그 크기는 격자판 기준 가로 1칸, 세로 2칸을 차지한다.
• 공기청정기는 총 2곳에서 바람을 내뿜고 있는데, 세로 칸 중 윗 칸에서는 시계 방향으로 공기를 순환시키는 바람이 나오고, 아랫칸에서는 반시계 방향으로 바람이 나온다.
• 바람에 의해 공기가 이동하며, 격자판 기준 1초당 이동하는 칸 수는 1칸이다.
• 바람의 시작점은 공기청정기의 위치이며, 바람은 벽면을 타고 이동한다.
• 공기가 바람을 타고 공기청정기의 위치에 도착할 경우, 정화되어 다시 바람을 타고 나오게 된다. 이때, 정화된 공기의 나쁨 정도는 0이다.

[그림 3]

강의실 정보가 주어졌을때, S초가 지난 후 공기의 나쁨 정도를 모두 합한 값을 알아내보자. 공기청정기는 항상 공기가 확산된 후에 동작한다.
예를 들어, [그림 1]의 상황에서 1초가 지난 모습은 다음과 같다.

[그림 4] 공기가 확산되고, 공기청정기에 의해 순환되는 모습

 

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄부터 T개의 테스트 케이스에 대한 정보가 주어진다.

각각의 테스트 케이스의 첫 번째 줄에 강의실 크기 R, C 와 시간 S, 퍼지는 거리 K 가 공백을 통해 구분하여 주어진다.

두 번째 줄부터 R 개의 줄에 걸쳐 강의실 공기 정보가 주어진다. 각 줄에는 C 개의 숫자가 공백을 통해 구분하여 주어지며, 각 숫자는 -1 이상 1000 이하의 정수이다. -1은 공기청정기를 뜻하며 세로로 인접하게 2개 주어진다. 또한, 첫번째 행과 마지막 행에 -1이 존재할 수 없다.

(5 ≤ R, C ≤ 100, 1 ≤ S ≤ 1000, 1 ≤ K ≤ 3)

 

출력

각 테스트 케이스에 대해 S초가 지난 후 공기의 나쁨 정도를 모두 합한 값을 출력한다. 각 테스트 케이스의 출력 양식은 "#t r"이다. t는 테스트 케이스의 번호이며, 1부터 시작한다. r은 문제에 대한 결과값을 뜻한다.

 

예제 입력

2

5 7 1 1

0 9 0 8 0 0 0

0 0 0 0 0 0 0

0 0 0 0 11 19 -1

0 17 14 0 13 0 -1

0 0 0 1 0 0 16

6 9 4 2

15 10 0 0 3 0 18 0 14

20 2 0 0 0 4 0 9 17

0 0 0 0 0 0 14 12 0

0 0 0 0 0 12 0 0 -1

0 0 0 0 0 7 0 0 -1

0 0 3 17 5 0 0 15 0

예제 출력

#1 95

#2 153

 

#코드

import sys
# 매초 확산이 먼저 일어나고 공기청정기가 작동한다 가정하자.
# 재 위치에서 x, y좌표와의 거리가 1이상 k이하인 위치들로 확산
# 두 점 (x1, y1), (x2, y2)의 거리는 |x1-x2| + |y1-y2|로 구한다. 
# 만약 확산할 좌표가 존재하지 않거나, 공기청정기 위치일 경우 해당 위치로는 퍼지지 않는다.
# 확산
# 공기의 나쁨 정도가 2k^2 + 2k + 1보다 작을 경우 확산이 일어나지 않는다.
# 공기의 확산이 일어났을때, 퍼지는 나쁨 정도는 기준 위치에서 2kk + 2*k + 1로 나눈 몫이다.
# 확산을 일으킨 후의 기준 위치의 공기의 나쁨 정도는 (현재 공기의 나쁨 정도) - (퍼진 공기의 나쁨 정도)*(확산된 칸의 수) 이다.
# 하나의 칸에 두 공기가 확산되어 왔을 경우, 확산된 나쁨 정도를 합한다.
# 공기는 1초에 한 번씩 확산이 된다.
'''
0   0   0
0   17  14
0   0   -1
-> 5
17//5 = 3
14//5 = 2
0  3  0
3  0  3
0  3  -1
0  0  2
0  2  0
0  0 -1
=================
0 3 2
3 7 13
0 3 -1
17 - 3*4 = 5
14 - 2*2 = 10
'''
# ============================================================================================================================================
#확산
def spread(row, col):
  global getArr, matrix, r, c, k, tempArr  
  givenValue = (2*k*k) + (2*k) + 1
  spreadVal  = getArr[row][col]//givenValue
  if getArr[row][col] < givenValue: return # 공기의 나쁨 정도가 2k^2 + 2k + 1보다 작을 경우 확산이 일어나지 않는다.
  cnt = 0
  # side_given_val = []
  for i in range((row-k), (row+k)+1):
    if i < 0 or i >= r: continue # 범위를 넘어갈 때
    for j in range((col-k), (col+k)+1):
      if j < 0 or j >= c: continue # 범위를 넘어갈 때
      if i == row and j == col: continue # 자기 자신의 값이 중복될 수 있으므로 제외 시켜준뒤 마지막에 따로 처리해준다.
      if getArr[i][j] == -1: continue
      dist = abs(row-i) + abs(col-j) # 두 점 (x1, y1), (x2, y2)의 거리는 |x1-x2| + |y1-y2|로 구한다.
      if dist >= 1 and dist <= k:
        tempArr[i][j] += spreadVal
        cnt += 1
  getArr[row][col] = getArr[row][col] - (spreadVal*cnt) 
  '''
  # 음수가 발생할 경우?
  if getArr[row-1][col-1] < 0:
    getArr[row-1][col-1] = 0
  '''    
  
# 공기청정기
# 공기청정기는 항상 강의실 오른쪽 벽면에 설치되어있고, 그 크기는 격자판 기준 가로 1칸, 세로 2칸을 차지한다.
# 공기청정기는 총 2곳에서 바람을 내뿜고 있는데, 세로 칸 중 윗 칸에서는 시계 방향으로 공기를 순환시키는 바람이 나오고,
# 아랫칸에서는 반시계 방향으로 바람이 나온다.
# 바람에 의해 공기가 이동하며, 격자판 기준 1초당 이동하는 칸 수는 1칸이다.
# 바람의 시작점은 공기청정기의 위치이며, 바람은 벽면을 타고 이동한다.
# 공기가 바람을 타고 공기청정기의 위치에 도착할 경우, 정화되어 다시 바람을 타고 나오게 된다. 
# 이때, 정화된 공기의 나쁨 정도는 0이다.
# 공기청정기는 항상 공기가 확산된 후에 동작한다
def clean(u, d):
  global getArr, matrix, r, c
  # 0 ~ u     : 시계방향 공기 순환
  # d ~ (r-1) : 반 시계방향 공기 순환
  # *********************** 첫 번째 시계 방향 밀기 ***********************
  # 1.우측 세로
  for i in range(u-1, 0, -1): # u부터 시작할 필요가 없다. -1이기 때문에 밀기를 할 필요가 없다
    getArr[i][c-1] = getArr[i-1][c-1]
  # 2.상단
  for i in range(c-1, 0, -1):
    getArr[0][i] = getArr[0][i-1]
  # 3.좌측 세로
  for i in range(u):
    getArr[i][0] = getArr[i+1][0]
  # 4.하단
  for i in range(c-1):
    getArr[u][i] = getArr[u][i+1]
  getArr[u][c-2] = 0
  # ********************** 두 번째 반시계 방향 밀기 **********************
  # 1. 우측 세로
  for i in range(d+1, r-1): # d번째 요소는 -1이기 때문에 밀기를 할 필요가 없다.
    getArr[i][c-1] = getArr[i+1][c-1]
  # 2. 하단
  for i in range(c-1, 0, -1):
    getArr[r-1][i] = getArr[r-1][i-1]
  # 3. 좌측세로
  for i in range(r-1, d, -1):
    getArr[i][0] = getArr[i-1][0]
  # 4. 상단
  for i in range(c-1):
    getArr[d][i] = getArr[d][i+1]
  getArr[d][c-2] = 0
  # ============================================================================================================================================
def abs(x):
  if x > 0: return x
  else: return -x
def updateMatrix():
  global getArr, matrix, r, c
  for i in range(r):
    for j in range(c):
      matrix[i+1][j+1] = getArr[i][j] 
# ============================================================================================================================================  
if __name__ == "__main__":
  input = sys.stdin.readline
  t = int(input())
  for ts in range(t):
    # 각각의 테스트 케이스의 첫 번째 줄에 강의실 크기 R, C 와 시간 S, 퍼지는 거리 K 가 공백을 통해 구분하여 주어진다.
    r, c, s, k = map(int, input().split())
    # -1은 공기청정기를 뜻하며 세로로 인접하게 2개 주어진다.
    # 첫번째 행과 마지막 행에 -1이 존재할 수 없다.
    getArr = [list(map(int, input().split())) for _ in range(r)]  
    matrix = [[0]*(c+2) for _ in range(r+2)]
    tempArr = [[0]*110 for _ in range(110)]
    updateMatrix()
    # guid_list : 이디까지가 시계방향이고, 어디서부터가 반시계방향인지를 알아야 한다.
    # 0 ~ guid_list[0]     : 시계방향 공기 순환
    # guid_list[1] ~ (r-1) : 반 시계방향 공기 순환
    guid_list = list()
    for i in range(1, len(getArr)-1): # 첫번째 행과 마지막 행에 -1이 존재할 수 없다.
      if getArr[i][c-1] == -1:
        guid_list.append(i)
    # 공기청정기는 항상 공기가 확산된 후에 동작한다
    for tt in range(s): # 시간만큼 확산시킨다.
      for row in range(r):
        for col in range(c):
          if getArr[row][col] == -1: continue
          spread(row, col)
      
      for i in range(r):
        for j in range(c):
          if getArr[i][j] == -1: continue
          getArr[i][j] += tempArr[i][j]
          tempArr[i][j] = 0 
      clean(guid_list[0], guid_list[1])    
    
     
    sum = 0 
    for i in getArr:
      for j in i:
        if j != -1:
          sum += j  
    print('#'+str((ts+1)), sum)