벽 부수고 이동하기 4
면접 대비시간 제한2초메모리 제한512 MB
N×M 이진 격자에서 각 벽 칸을 부수고 그 칸에서 도달할 수 있는 열린 영역의 크기를 10으로 나눈 나머지로 출력하며, 원래 빈 칸은 0으로 둔다.
문제
N×M 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때 인접하다고 한다.
각각의 벽에 대해 다음을 구하려고 한다.
- 벽을 부수고 이동할 수 있는 곳으로 바꾼다.
- 그 위치에서 이동할 수 있는 칸의 개수를 센다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
출력
맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.