세상에서 가장 뜨거운 바다는? timer 1s memory 32MB

어느날 수업을 하던 권수쌤이 학생에게 물었다.

"세상에서 가장 뜨거운 바다는?"

학생은 대답이 없었다.

"정답은 열바다야~!"

권수쌤이 자문자답을 하였다.

학생은 열이 받았다.

열바다는 온도가 100도인 아주 뜨거운 바다다.

우리는 학생의 열을 식혀주진 못하지만 열바다의 열은 식혀줄 수가 있다.

방법은 간단하게도 얼음을 넣으면 된다!

권수쌤은 친절하게도 뛰어난 코딩실력을 발휘하여 열바다를 RxC 크기의 격자판으로 나타냈다. 각 칸의 크기는  1x1로 이루어져있고, 가장 왼쪽 윗 칸은 (1,1)의 좌표를 갖고, 오른쪽 아랫 칸은 (R,C)의 좌표를 갖는다.

​

우리는 N번에 걸쳐 N개의 얼음을 열바다에 집어넣을 예정이다.

얼음의 크기는 1x1로 아주 차갑기에 얼음이 들어간 위치를 기준으로 해당 위치와 상하좌우 네 칸을 포함한 총 다섯 칸의 온도를 낮추고 녹아 없어진다.

얼음이 떨어진 칸은 4도의 온도가 떨어지고, 주변 네 칸은 2도가 떨어진다.

그러나 열바다의 가장자리에 얼음이 떨어지게 된다면 범위를 벗어나는 주변 칸에 영향을 주어야 했으나 못 준 만큼의 절반에 해당하는 만큼 얼음이 떨어진 칸에 추가로 온도를 감소시킨다.

만약 (1,1)에 얼음이 떨어진다면 위와 왼쪽 칸은 범위를 벗어나기에 얼음이 떨어진 칸은 두 칸에 영향을 못준 4도의 절반에 해당하는 2도가 추가적으로 적용되어 (1,1)칸의 온도를 총 6만큼 감소시키고, (1,2)와 (2,1)은 다를바 없이 2도가 감소한다.

열바다가 아무리 뜨겁더라도 온도가 0이 되면 얼어버리기 때문에 온도는 0도에서 더이상 떨어지지 않는다. 또한 이미 0도가 되어 얼어버린 곳에 얼음이 추가로 들어가도 아무런 영향을 끼치지 않으며, 이 경우엔 주변에도 영향을 줄 수가 없다. 가장자리에 떨어진 것과 같이 주변 칸이 얼음인 경우에도 얼음인 주변 칸에는 영향을 줄 수 없기에 얼음이 떨어진 칸에 추가로 영향이 주어진다.

열바다에 N개의 얼음이 들어간 후 각 칸의 온도를 출력하자.