시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 134 37 35 29.167%

문제

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

입력

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

출력

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

예제 입력 1

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

예제 출력 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

 

W3sicHJvYmxlbV9pZCI6IjE3MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkOTVcdWM1YjRcdWJlNzVcdWQwYzBcdWM3NzRcdWNmZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdCZuYnNwOyBcdWMxMzFcdWM5YzBcdWIyOTQgXHViYWIwXHViNzk4IFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWJkOTVcdWM1YjRcdWJlNzVcdWQwYzBcdWM3NzRcdWNmZTRcdWM3NDQgXHVjOTkwXHVhZTMwXHViMjk0IFx1YzkxMVx1Yzc3NFx1YzVjOFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWFlMzBcdWM4NzRcdWM3NTggXHViZDk1XHVjNWI0XHViZTc1XHVkMGMwXHVjNzc0XHVjZmU0IFx1YWM4Y1x1Yzc4NFx1YWNmY1x1YjI5NCBcdWM4NzBcdWFlMDggXHViMmU0XHViOTc0XHViMmU0LjxiciBcLz5cclxuXHQmbmJzcDsgTSpOIFx1YWNhOVx1Yzc5MFx1YzVkMCBcdWJkOTVcdWM1YjRcdWJlNzVcdWM3NzQgXHViNGU0XHVjNWI0XHVhYzAwIFx1Yzc4OFx1YjJlNC4gKFx1ZDYwNFx1YzdhYyBcdWM1NWVcdWJhNzRcdWM3NzQgXHVjNzA0XHViODVjIFx1YWQ3ZFx1ZDc4OFx1YjI5NCBcdWFjODNcdWIzYzQgXHVjNzg4XHVhY2UwIFx1YjRiN1x1YmE3NFx1Yzc3NCBcdWM3MDRcdWI4NWMgXHVhZDdkXHVkNzg4XHViMjk0IFx1YWM4M1x1YjNjNCBcdWM3ODhcdWIyZTQuKSBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNWI0XHViNWE0IFx1ZDU1YyBcdWFjYTlcdWM3OTBcdWI5N2MgXHViMjA0XHViOTc4XHViMmU0XHViYTc0IFx1YWRmOCBcdWFjYTlcdWM3OTBcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTc0XHVjMTFjIDRcdWJjMjlcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTVjIFx1YmQ5NVx1YzViNFx1YmU3NVx1YjRlNFx1YjNjNChcdWJiM2NcdWI4NjAgXHVhYzAwXHVjN2E1XHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzhmY1x1YmNjMFx1YzVkMCAyXHVhYzFjIFx1YjYxMFx1YjI5NCAzXHVhYzFjXHVjNzc0XHViMmU0KSBcdWIzZDlcdWMyZGNcdWM1ZDAgXHViNGE0XHVjOWQxXHVkNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC48YnIgXC8+XHJcblx0Jm5ic3A7IFx1YmQ5NVx1YzViNFx1YmU3NVx1Yzc3NCBcdWIxNzhcdWI5ODdcdWQ1NThcdWFjOGMgXHVjNzc1XHVjNWI0IFx1YmFhOFx1YjQ1MCBcdWFlYmNcdWIwYmMgXHViNTRjXHVhYzAwIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHViMmU4IFx1YWRkY1x1Y2U1OVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVjNTVlXHViYTc0XHVjNzc0IFx1YzcwNFx1Yjg1YyBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjXHViOWNjIFx1YWViY1x1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMjkwXHVhZTBiXHVkNTU4XHVhYzhjIFx1YjRhNFx1YzlkMVx1YjJlNFx1YWMwNCBcdWJkOTVcdWM1YjRcdWJlNzVcdWM3NzQgXHVkMGMwXHVhY2UwIFx1YzE5MFx1YjJkOFx1YjRlNFx1Yzc0MCBcdWQ2NTRcdWI5N2MgXHViMGI0XHVhY2UwIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWM4ODVcdWI4Y2NcdWI0MThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzRcdWM1ZDAgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YWNhOVx1Yzc5MFx1YjljY1x1Yzc0NCBcdWIyMGNcdWI3ZWMgXHViYWE4XHViNGUwIFx1YmQ5NVx1YzViNFx1YmU3NVx1Yzc3NCBcdWM1NWVcdWJhNzRcdWM3NzQgXHVjNzA0XHViODVjIFx1YmNmNFx1Yzc3NFx1YWM4YyBcdWQ1NThcdWI4MjRcdWQ1NWNcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHVjMTMxXHVjOWMwXHViOTdjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdCZuYnNwOyBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWMxMzhcdWI4NWMsIFx1YWMwMFx1Yjg1YyBcdWQwNmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggTVx1YWNmYyBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOFx1YmQ4MFx1ZDEzMCBNKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIE5cdWFjMWNcdWM3NTggMCBcdWI2MTBcdWIyOTQgMVx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIDBcdWM3NDAgXHVkNjA0XHVjN2FjIFx1YzU1ZVx1YmE3NFx1Yzc3NCBcdWM3MDRcdWI4NWMgXHViY2Y0XHVjNzc0XHViMjk0IFx1YmQ5NVx1YzViNFx1YmU3NVx1Yzc3NFx1YWNlMCAxXHVjNzQwIFx1ZDYwNFx1YzdhYyBcdWM1NWVcdWJhNzRcdWM3NzQgXHViNGE0XHViODVjIFx1YmNmNFx1Yzc3NFx1YjI5NCBcdWJkOTVcdWM1YjRcdWJlNzVcdWM3NzRcdWIyZTQuIChOJmx0Oz0xNSwgTSZsdDs9MTUpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0Jm5ic3A7IE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCAoTSwgTikgXHViYzg4XHVjOWY4IFx1YWNhOVx1Yzc5MFx1Yjk3YyBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHViYTg3IFx1YmM4OCBcdWI0YTRcdWM5ZDFcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YjJlOCBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjYmRcdWM2YjAgJnF1b3Q7SU1QT1NTSUJMRSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjODc0XHVjN2FjXHVkNTYwIFx1YWNiZFx1YzZiMCBcdWM3MDRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3ZFx1Yzc0NCBcdWI1NGMgXHVkNTVjIFx1YzkwNFx1YzUyOSBcdWM3N2RcdWM3NDQgXHViNTRjIFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHRcdWNjOThcdWM3NGNcdWM1ZDAgKDIsMSlcdWM3NDQgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWJjYzBcdWQ1NThcdWFjZTA8YnIgXC8+XHJcblx0MCAwIDAgMTxiciBcLz5cclxuXHQxIDAgMSAwPGJyIFwvPlxyXG5cdDEgMSAxIDA8YnIgXC8+XHJcblx0MSAwIDAgMTxiciBcLz5cclxuXHRcdWM1ZWNcdWFlMzBcdWMxMWMgKDIsNClcdWI5N2MgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWJjYzBcdWQ1NWNcdWIyZTQuPGJyIFwvPlxyXG5cdDAgMCAwIDA8YnIgXC8+XHJcblx0MSAwIDAgMTxiciBcLz5cclxuXHQxIDEgMSAxPGJyIFwvPlxyXG5cdDEgMCAwIDE8YnIgXC8+XHJcblx0XHVjNWVjXHVhZTMwXHVjMTFjICgzLDEpXHViOTdjIFx1YjIwNFx1Yjk3NFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViY2MwXHVkNTVjXHViMmU0LjxiciBcLz5cclxuXHQwIDAgMCAwPGJyIFwvPlxyXG5cdDAgMCAwIDE8YnIgXC8+XHJcblx0MCAwIDEgMTxiciBcLz5cclxuXHQwIDAgMCAxPGJyIFwvPlxyXG5cdFx1YzVlY1x1YWUzMFx1YzExYyAoMyw0KVx1Yjk3YyBcdWIyMDRcdWI5NzRcdWFjOGMgXHViNDE4XHViYTc0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YmNjMFx1ZDU1OFx1YWNlMCBcdWIwNWRcdWIwOWNcdWIyZTQuPGJyIFwvPlxyXG5cdDAgMCAwIDA8YnIgXC8+XHJcblx0MCAwIDAgMDxiciBcLz5cclxuXHQwIDAgMCAwPGJyIFwvPlxyXG5cdDAgMCAwIDA8XC9wPlxyXG48cD5cclxuXHRcdWJiM2NcdWI4NjAgXHVjNTQ0XHViNzk4XHVjNzU4IFx1Yzc4OFx1YjI5NCBcdWQ1NzQgXHVjNWVkXHVjMmRjIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YzljMFx1YjljYyBcdWM1NDRcdWI3OTggXHViMmY1XHVjNzQwIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWIzNTQgXHViNGE0XHVjNWQwIFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWM2MDhcdWM4MWMgXHVjZDljXHViODI1XHVjNzc0IFx1YjJmNVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0MCAxIDEgMDxiciBcLz5cclxuXHQwIDAgMCAwPGJyIFwvPlxyXG5cdDAgMCAwIDA8YnIgXC8+XHJcblx0MCAxIDEgMDxcL3A+XHJcbjxwPlxyXG5cdCZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTcwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZsaXB0aWxlIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBrbm93cyB0aGF0IGFuIGludGVsbGVjdHVhbGx5IHNhdGlzZmllZCBjb3cgaXMgYSBoYXBweSBjb3cgd2hvIHdpbGwgZ2l2ZSBtb3JlIG1pbGsuIEhlIGhhcyBhcnJhbmdlZCBhIGJyYWlueSBhY3Rpdml0eSBmb3IgY293cyBpbiB3aGljaCB0aGV5IG1hbmlwdWxhdGUgYW4gTSB4IE4gZ3JpZCAoMSAmbHQ7PSBNICZsdDs9IDE1OyAxICZsdDs9IE4gJmx0Oz0gMTUpIG9mIHNxdWFyZSB0aWxlcywgZWFjaCBvZiB3aGljaCBpcyBjb2xvcmVkIGJsYWNrIG9uIG9uZSBzaWRlIGFuZCB3aGl0ZSBvbiB0aGUgb3RoZXIgc2lkZS48XC9wPlxyXG5cclxuPHA+QXMgb25lIHdvdWxkIGd1ZXNzLCB3aGVuIGEgc2luZ2xlIHdoaXRlIHRpbGUgaXMgZmxpcHBlZCwgaXQgY2hhbmdlcyB0byBibGFjazsgd2hlbiBhIHNpbmdsZSBibGFjayB0aWxlIGlzIGZsaXBwZWQsIGl0IGNoYW5nZXMgdG8gd2hpdGUuIFRoZSBjb3dzIGFyZSByZXdhcmRlZCB3aGVuIHRoZXkgZmxpcCB0aGUgdGlsZXMgc28gdGhhdCBlYWNoIHRpbGUgaGFzIHRoZSB3aGl0ZSBzaWRlIGZhY2UgdXAuIEhvd2V2ZXIsIHRoZSBjb3dzIGhhdmUgcmF0aGVyIGxhcmdlIGhvb3ZlcyBhbmQgd2hlbiB0aGV5IHRyeSB0byBmbGlwIGEgY2VydGFpbiB0aWxlLCB0aGV5IGFsc28gZmxpcCBhbGwgdGhlIGFkamFjZW50IHRpbGVzICh0aWxlcyB0aGF0IHNoYXJlIGEgZnVsbCBlZGdlIHdpdGggdGhlIGZsaXBwZWQgdGlsZSkuIFNpbmNlIHRoZSBmbGlwcyBhcmUgdGlyaW5nLCB0aGUgY293cyB3YW50IHRvIG1pbmltaXplIHRoZSBudW1iZXIgb2YgZmxpcHMgdGhleSBoYXZlIHRvIG1ha2UuPFwvcD5cclxuXHJcbjxwPkhlbHAgdGhlIGNvd3MgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBmbGlwcyByZXF1aXJlZCwgYW5kIHRoZSBsb2NhdGlvbnMgdG8gZmxpcCB0byBhY2hpZXZlIHRoYXQgbWluaW11bS4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHdheXMgdG8gYWNoaWV2ZSB0aGUgdGFzayB3aXRoIHRoZSBtaW5pbXVtIGFtb3VudCBvZiBmbGlwcywgcmV0dXJuIHRoZSBvbmUgd2l0aCB0aGUgbGVhc3QgbGV4aWNvZ3JhcGhpY2FsIG9yZGVyaW5nIGluIHRoZSBvdXRwdXQgd2hlbiBjb25zaWRlcmVkIGFzIGEgc3RyaW5nLiAmbmJzcDtJZiB0aGUgdGFzayBpcyBpbXBvc3NpYmxlLCBwcmludCBvbmUgbGluZSB3aXRoIHRoZSB3b3JkICZxdW90O0lNUE9TU0lCTEUmcXVvdDsuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTSBhbmQgTjxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk0rMTogTGluZSBpKzEgZGVzY3JpYmVzIHRoZSBjb2xvcnMgKGxlZnQgdG8gcmlnaHQpIG9mIHJvdyBpIG9mIHRoZSBncmlkIHdpdGggTiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgd2hpY2ggYXJlIDEgZm9yIGJsYWNrIGFuZCAwIGZvciB3aGl0ZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZXMgMS4uTTogRWFjaCBsaW5lIGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBlYWNoIHNwZWNpZnlpbmcgaG93IG1hbnkgdGltZXMgdG8gZmxpcCB0aGF0IHBhcnRpY3VsYXIgbG9jYXRpb24uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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