붕어빵 타이쿤
시간 제한2초메모리 제한128 MB
M행 N열 격자에서 칸을 누르면 상하좌우와 함께 뒤집히는 붕어빵 퍼즐을 모두 앞면으로 만드는 최소 횟수의 사전순 최소 누름 배치를 구합니다.
문제
성지는 몰래 붕어빵 타이쿤 게임을 즐기고 있다. 이 게임은 조금 특별하다.
격자는 M행 N열로 이루어져 있고, 각 칸에는 붕어빵 하나가 놓여 있다. 각 붕어빵은 앞면이 위를 향하거나 뒷면이 위를 향한다. 한 칸을 누르면 그 칸의 붕어빵과 상하좌우로 인접한 붕어빵들이 동시에 뒤집힌다. 격자 밖에 있는 칸은 무시한다.
모든 붕어빵을 꺼내려면 모든 붕어빵의 앞면이 위를 향해야 한다. 가능한 한 적은 칸을 눌러 모든 붕어빵을 앞면이 위로 보이게 만드는 방법을 구하자.
입력
첫째 줄에 격자의 세로 크기 M과 가로 크기 N이 주어진다. (1 ≤ M ≤ 15, 1 ≤ N ≤ 15)
둘째 줄부터 M개의 줄에는 각 줄마다 N개의 정수 0 또는 1이 주어진다. 0은 현재 앞면이 위로 보이는 붕어빵, 1은 현재 뒷면이 위로 보이는 붕어빵을 의미한다.
출력
모든 붕어빵의 앞면을 위로 만들 수 있다면 M개의 줄에 N개의 숫자를 출력한다. 각 숫자는 해당 칸을 누르면 1, 누르지 않으면 0이다.
출력하는 방법은 누르는 칸의 개수가 최소여야 한다. 최소 방법이 여러 개라면 위쪽 행부터, 같은 행에서는 왼쪽 칸부터 읽었을 때 사전순으로 가장 앞서는 방법을 출력한다.
가능한 방법이 없으면 IMPOSSIBLE을 출력한다.
힌트
처음에 (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
다음 방법도 가능하지만, 사전순으로 더 뒤에 있으므로 정답으로 출력하지 않는다.
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0