Informatica Online Judge

  타일뒤집기 [2337 / 0921]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 5   Total Tried : 8


The Champion of this Problem (C++) : gs18115 - ms / 1502byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

$M × N$ 크기의 $(1 ≤ M ≤ 15, 1 ≤ N ≤ 15)$ 정사각형 타일 뒤집기 놀이를 하고자 한다.

각 타일은 한면에는 검정색으로, 다른면에는 흰색으로 칠해져 있다.

흰색타일과 검은색 타일은 뒤집을때마다 서로 색이 바뀌게 된다. 그리고, 하나의 타일을 뒤집으면, 그 타일을 포함해서 상, 하, 좌, 우에 있는 타일들도 동시에 뒤집히게 된다.

최소한의 타일만 뒤집어서 모두 흰색면을 위로 보이는 프로그램을 작성하시오.

단, 답이 존재하지 않을 경우 "IMPOSSIBLE", 답이 여러개 존재할 경우에는 위에서부터 오른쪽으로 읽을 때 한줄씩 읽을 때 사전순으로 가장 빠른것을 출력한다.

Input

첫번째 줄에는 타일의 가로, 세로 크기(M, N)를 입력한다.

두번째 줄부터 M+1번째 줄까지 N개의 0 또는 1의 숫자가 주어지는데 0은 현재 앞면이 위로 보이는 타일이고 1은 현재 앞면이 뒤로 보이는 타일이다. (N ≤ 15, M ≤ 15)

Output

M개의 줄에 N개의 숫자를 출력한다.

이 숫자는 (M, N) 번째 격자를 최종적으로 몇 번 뒤집어야 하는지 나타내는 숫자이다.

단 답이 존재하지 않을 경우 "IMPOSSIBLE"을 출력하고 답이 여러 개 존재할 경우 위에서부터 오른쪽으로 한 줄씩 읽을 때 사전 순으로 가장 빠른 것을 출력한다.

IO Example

<입력 예>
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1


<출력 예>
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]