시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 78 22 21 28.378%

문제

  성지는 몰래 열심히 붕어빵타이쿤을 즐기는 중이었다. 하지만 이것은 기존의 붕어빵타이쿤 게임과는 조금 다르다.
  M*N 격자에 붕어빵이 들어가 있다. (현재 앞면이 위로 굽히는 것도 있고 뒷면이 위로 굽히는 것도 있다.) 그리고 어떤 한 격자를 누른다면 그 격자를 포함해서 4방에 위치한 붕어빵들도(물론 가장자리에서는 주변에 2개 또는 3개이다) 동시에 뒤집히게 된다.
  붕어빵이 노릇하게 익어 모두 꺼낼 때가 되었다. 단 규칙이 있는데 앞면이 위로 보이는 상태에서만 꺼낼 수 있다는 것이다. 느긋하게 뒤집다간 붕어빵이 타고 손님들은 화를 내고 게임은 종료되게 된다. 이에 최소한의 격자만을 눌러 모든 붕어빵이 앞면이 위로 보이게 하려한다. 우리는 이런 성지를 도와주자.

입력

  첫째 줄에는 격자의 세로, 가로 크기를 나타내는 두 정수 M과 N이 주어진다. 두 번째부터 M+1번째 줄까지 N개의 0 또는 1의 숫자가 주어지는데 0은 현재 앞면이 위로 보이는 붕어빵이고 1은 현재 앞면이 뒤로 보이는 붕어빵이다. (N<=15, M<=15)

출력

  M개의 줄에 N개의 숫자를 출력한다. 이 숫자는 (M, N) 번째 격자를 최종적으로 몇 번 뒤집어야 하는지 나타내는 숫자이다. 단 답이 존재하지 않을 경우 "IMPOSSIBLE"을 출력하고 답이 여러 개 존재할 경우 위에서부터 오른쪽으로 읽을 때 한 줄씩 읽을 때 사전 순으로 가장 빠른 것을 출력한다.

예제 입력

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

힌트

처음에 (2,1)을 누르게 되면, 아래와 같이 변하고
0 0 0 1
1 0 1 0
1 1 1 0
1 0 0 1
여기서 (2,4)를 누르게 되면, 아래와 같이 변한다.
0 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1
여기서 (3,1)를 누르게 되면, 아래와 같이 변한다.
0 0 0 0
0 0 0 1
0 0 1 1
0 0 0 1
여기서 (3,4)를 누르게 되면, 아래와 같이 변하고 끝난다.
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

물론 아래의 있는 해 역시 가능하지만 아래 답은 사전순으로 더 뒤에 있으므로 예제 출력이 답이 된다.

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

 

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 3번