지뢰찾기

문제 정보

문제

2020년, 전세계에서 유일한 분단국가인 남한과 북한이 통일을 선언했다. 남북은 통일이 되면서 DMZ (남한과 북한의 경계에 있는 비무장지대) 에 묻혀 있는 지뢰를 모두 제거하기로 했다. 지뢰는 H*W 격자로 이루어진 땅에 묻혀 있고, 각 칸에 최대 한 개가 묻혀 있다. 우리는 지뢰가 어디에 묻혀 있는지는 정확히 알 수 없으나, 센서를 이용해서 각 칸의 위험도를 알 수 있다. 지뢰가 묻혀 있는 칸에 인접한 상하좌우 네 칸은 각각 위험도가 U, D, L, R 만큼 증가한다. 이 때 U, D, L, R 은 서로 다른 자연수이다.

(a) (b)
(c) (d)

예를 들어, 그림 (a) 와 같이 3*3 크기의 격자로 이루어진 땅이 있고, U=1, D=2, L=3, R=4 라고 하자. 만약 (2,2) 에 지뢰가 있다면, 각 칸의 위험도는 그림 (b) 와 같이 된다. 그림 (c) 와 (d) 는 (1,2) 와 (1,1) 에 순서대로 지뢰를 추가했을 때의 각 칸의 위험도를 보여준다.

모든 칸의 위험도가 주어졌을 때, 지뢰가 어디에 있는지 찾아내는 프로그램을 작성하라.

입력

입력의 첫번째 줄에는 테스트 케이스의 개수 C 가 주어진다. (1<= C<=20) 각 테스트 케이스의 첫번째 줄에는 정수 H 와 W 가 주어지며, (2<= H<=20, 2<= W<=1,000) 두번째 줄에는 서로 다른 네 개의 정수 U, D, L, R 이 주어진다. (1<= U,D,L,R<=10) 그 후 H 줄에 걸쳐 각각 W 개의 정수로, 각 칸의 위험도가 주어진다. 지도 바깥에는 지뢰가 존재하지 않는다.

답이 여러 가지인 경우는 주어지지 않는다.

출력

각 테스트 케이스에 대해 지뢰가 있는 지점은 1 로 표시하고, 지뢰가 없는 지점은 0 으로 표시한 H*W 크기의 격자 지도를 출력한다.

예제 입력

2 
3 3 
8 1 2 7 
0 9 0 
9 0 9 
0 9 0
3 4 
1 2 3 4 
4 1 5 0 
3 10 4 4
5 2 6 0

예제 출력

1 0 1 
0 0 0 
1 0 1
0 1 0 0 
1 1 1 0 
0 1 0 0

노트

5개의 댓글이 있습니다.