시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB74514912122.744%

문제

성지는 몰래 열심히 붕어빵타이쿤을 즐기는 중이었다. 하지만 이것은 기존의 붕어빵타이쿤 게임과는 조금 다르다.

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 00
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
W3sicHJvYmxlbV9pZCI6IjE3MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkOTVcdWM1YjRcdWJlNzVcdWQwYzBcdWM3NzRcdWNmZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEzMVx1YzljMFx1YjI5NCBcdWJhYjBcdWI3OTggXHVjNWY0XHVjMmVjXHVkNzg4IFx1YmQ5NVx1YzViNFx1YmU3NVx1ZDBjMFx1Yzc3NFx1Y2ZlNFx1Yzc0NCBcdWM5OTBcdWFlMzBcdWIyOTQgXHVjOTExXHVjNzc0XHVjNWM4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzc0XHVhYzgzXHVjNzQwIFx1YWUzMFx1Yzg3NFx1Yzc1OCBcdWJkOTVcdWM1YjRcdWJlNzVcdWQwYzBcdWM3NzRcdWNmZTQgXHVhYzhjXHVjNzg0XHVhY2ZjXHViMjk0IFx1Yzg3MFx1YWUwOCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk0qTiBcdWFjYTlcdWM3OTBcdWM1ZDAgXHViZDk1XHVjNWI0XHViZTc1XHVjNzc0IFx1YjRlNFx1YzViNFx1YWMwMCBcdWM3ODhcdWIyZTQuIChcdWQ2MDRcdWM3YWMgXHVjNTVlXHViYTc0XHVjNzc0IFx1YzcwNFx1Yjg1YyBcdWFkN2RcdWQ3ODhcdWIyOTQgXHVhYzgzXHViM2M0IFx1Yzc4OFx1YWNlMCBcdWI0YjdcdWJhNzRcdWM3NzQgXHVjNzA0XHViODVjIFx1YWQ3ZFx1ZDc4OFx1YjI5NCBcdWFjODNcdWIzYzQgXHVjNzg4XHViMmU0LikgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzViNFx1YjVhNCBcdWQ1NWMgXHVhY2E5XHVjNzkwXHViOTdjIFx1YjIwNFx1Yjk3OFx1YjJlNFx1YmE3NCBcdWFkZjggXHVhY2E5XHVjNzkwXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyA0XHViYzI5XHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWJkOTVcdWM1YjRcdWJlNzVcdWI0ZTRcdWIzYzQoXHViYjNjXHViODYwIFx1YWMwMFx1YzdhNVx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM4ZmNcdWJjYzBcdWM1ZDAgMlx1YWMxYyBcdWI2MTBcdWIyOTQgM1x1YWMxY1x1Yzc3NFx1YjJlNCkgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YjRhNFx1YzlkMVx1ZDc4OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmQ5NVx1YzViNFx1YmU3NVx1Yzc3NCBcdWIxNzhcdWI5ODdcdWQ1NThcdWFjOGMgXHVjNzc1XHVjNWI0IFx1YmFhOFx1YjQ1MCBcdWFlYmNcdWIwYmMgXHViNTRjXHVhYzAwIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHViMmU4IFx1YWRkY1x1Y2U1OVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVjNTVlXHViYTc0XHVjNzc0IFx1YzcwNFx1Yjg1YyBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjXHViOWNjIFx1YWViY1x1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMjkwXHVhZTBiXHVkNTU4XHVhYzhjIFx1YjRhNFx1YzlkMVx1YjJlNFx1YWMwNCBcdWJkOTVcdWM1YjRcdWJlNzVcdWM3NzQgXHVkMGMwXHVhY2UwIFx1YzE5MFx1YjJkOFx1YjRlNFx1Yzc0MCBcdWQ2NTRcdWI5N2MgXHViMGI0XHVhY2UwIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWM4ODVcdWI4Y2NcdWI0MThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzRcdWM1ZDAgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YWNhOVx1Yzc5MFx1YjljY1x1Yzc0NCBcdWIyMGNcdWI3ZWMgXHViYWE4XHViNGUwIFx1YmQ5NVx1YzViNFx1YmU3NVx1Yzc3NCBcdWM1NWVcdWJhNzRcdWM3NzQgXHVjNzA0XHViODVjIFx1YmNmNFx1Yzc3NFx1YWM4YyBcdWQ1NThcdWI4MjRcdWQ1NWNcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHVjMTMxXHVjOWMwXHViOTdjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2E5XHVjNzkwXHVjNzU4IFx1YzEzOFx1Yjg1YywgXHVhYzAwXHViODVjIFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBNXHVhY2ZjIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4XHViZDgwXHVkMTMwIE0rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgTlx1YWMxY1x1Yzc1OCAwIFx1YjYxMFx1YjI5NCAxXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgMFx1Yzc0MCBcdWQ2MDRcdWM3YWMgXHVjNTVlXHViYTc0XHVjNzc0IFx1YzcwNFx1Yjg1YyBcdWJjZjRcdWM3NzRcdWIyOTQgXHViZDk1XHVjNWI0XHViZTc1XHVjNzc0XHVhY2UwIDFcdWM3NDAgXHVkNjA0XHVjN2FjIFx1YzU1ZVx1YmE3NFx1Yzc3NCBcdWI0YTRcdWI4NWMgXHViY2Y0XHVjNzc0XHViMjk0IFx1YmQ5NVx1YzViNFx1YmU3NVx1Yzc3NFx1YjJlNC4gKE4gJmxlOyAxNSwgTSAmbGU7IDE1KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiZuYnNwO01cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCAoTSwgTikgXHViYzg4XHVjOWY4IFx1YWNhOVx1Yzc5MFx1Yjk3YyBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHViYTg3IFx1YmM4OCBcdWI0YTRcdWM5ZDFcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YjJlOCBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjYmRcdWM2YjAgJnF1b3Q7SU1QT1NTSUJMRSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjODc0XHVjN2FjXHVkNTYwIFx1YWNiZFx1YzZiMCBcdWM3MDRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3ZFx1Yzc0NCBcdWI1NGMgXHVkNTVjIFx1YzkwNFx1YzUyOSBcdWM3N2RcdWM3NDQgXHViNTRjIFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjOThcdWM3NGNcdWM1ZDAgKDIsMSlcdWM3NDQgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWJjYzBcdWQ1NThcdWFjZTA8XC9wPlxyXG5cclxuPHByZT5cclxuMCAwIDAgMVxyXG4xIDAgMSAwXHJcbjEgMSAxIDBcclxuMSAwIDAgMTxcL3ByZT5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyAoMiw0KVx1Yjk3YyBcdWIyMDRcdWI5NzRcdWFjOGMgXHViNDE4XHViYTc0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YmNjMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMCAwIDAgMFxyXG4xIDAgMCAxXHJcbjEgMSAxIDFcclxuMSAwIDAgMTxcL3ByZT5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyAoMywxKVx1Yjk3YyBcdWIyMDRcdWI5NzRcdWFjOGMgXHViNDE4XHViYTc0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YmNjMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMCAwIDAwXHJcbjAgMCAwIDFcclxuMCAwIDEgMVxyXG4wIDAgMCAxPFwvcHJlPlxyXG5cclxuPHA+XHVjNWVjXHVhZTMwXHVjMTFjICgzLDQpXHViOTdjIFx1YjIwNFx1Yjk3NFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViY2MwXHVkNTU4XHVhY2UwIFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMCAwIDAgMFxyXG4wIDAgMCAwXHJcbjAgMCAwIDBcclxuMCAwIDAgMDxcL3ByZT5cclxuXHJcbjxwPlx1YmIzY1x1Yjg2MCBcdWM1NDRcdWI3OThcdWM3NTggXHVjNzg4XHViMjk0IFx1ZDU3NCBcdWM1ZWRcdWMyZGMgXHVhYzAwXHViMmE1XHVkNTU4XHVjOWMwXHViOWNjIFx1YzU0NFx1Yjc5OCBcdWIyZjVcdWM3NDAgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YjM1NCBcdWI0YTRcdWM1ZDAgXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWM3NzQgXHViMmY1XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMCAxIDEgMFxyXG4wIDAgMCAwXHJcbjAgMCAwIDBcclxuMCAxIDEgMDxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNzA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmxpcHRpbGUiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGtub3dzIHRoYXQgYW4gaW50ZWxsZWN0dWFsbHkgc2F0aXNmaWVkIGNvdyBpcyBhIGhhcHB5IGNvdyB3aG8gd2lsbCBnaXZlIG1vcmUgbWlsay4gSGUgaGFzIGFycmFuZ2VkIGEgYnJhaW55IGFjdGl2aXR5IGZvciBjb3dzIGluIHdoaWNoIHRoZXkgbWFuaXB1bGF0ZSBhbiBNIHggTiBncmlkICgxICZsdDs9IE0gJmx0Oz0gMTU7IDEgJmx0Oz0gTiAmbHQ7PSAxNSkgb2Ygc3F1YXJlIHRpbGVzLCBlYWNoIG9mIHdoaWNoIGlzIGNvbG9yZWQgYmxhY2sgb24gb25lIHNpZGUgYW5kIHdoaXRlIG9uIHRoZSBvdGhlciBzaWRlLjxcL3A+XHJcblxyXG48cD5BcyBvbmUgd291bGQgZ3Vlc3MsIHdoZW4gYSBzaW5nbGUgd2hpdGUgdGlsZSBpcyBmbGlwcGVkLCBpdCBjaGFuZ2VzIHRvIGJsYWNrOyB3aGVuIGEgc2luZ2xlIGJsYWNrIHRpbGUgaXMgZmxpcHBlZCwgaXQgY2hhbmdlcyB0byB3aGl0ZS4gVGhlIGNvd3MgYXJlIHJld2FyZGVkIHdoZW4gdGhleSBmbGlwIHRoZSB0aWxlcyBzbyB0aGF0IGVhY2ggdGlsZSBoYXMgdGhlIHdoaXRlIHNpZGUgZmFjZSB1cC4gSG93ZXZlciwgdGhlIGNvd3MgaGF2ZSByYXRoZXIgbGFyZ2UgaG9vdmVzIGFuZCB3aGVuIHRoZXkgdHJ5IHRvIGZsaXAgYSBjZXJ0YWluIHRpbGUsIHRoZXkgYWxzbyBmbGlwIGFsbCB0aGUgYWRqYWNlbnQgdGlsZXMgKHRpbGVzIHRoYXQgc2hhcmUgYSBmdWxsIGVkZ2Ugd2l0aCB0aGUgZmxpcHBlZCB0aWxlKS4gU2luY2UgdGhlIGZsaXBzIGFyZSB0aXJpbmcsIHRoZSBjb3dzIHdhbnQgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBmbGlwcyB0aGV5IGhhdmUgdG8gbWFrZS48XC9wPlxyXG5cclxuPHA+SGVscCB0aGUgY293cyBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGZsaXBzIHJlcXVpcmVkLCBhbmQgdGhlIGxvY2F0aW9ucyB0byBmbGlwIHRvIGFjaGlldmUgdGhhdCBtaW5pbXVtLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgd2F5cyB0byBhY2hpZXZlIHRoZSB0YXNrIHdpdGggdGhlIG1pbmltdW0gYW1vdW50IG9mIGZsaXBzLCByZXR1cm4gdGhlIG9uZSB3aXRoIHRoZSBsZWFzdCBsZXhpY29ncmFwaGljYWwgb3JkZXJpbmcgaW4gdGhlIG91dHB1dCB3aGVuIGNvbnNpZGVyZWQgYXMgYSBzdHJpbmcuICZuYnNwO0lmIHRoZSB0YXNrIGlzIGltcG9zc2libGUsIHByaW50IG9uZSBsaW5lIHdpdGggdGhlIHdvcmQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90Oy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBNIGFuZCBOPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTSsxOiBMaW5lIGkrMSBkZXNjcmliZXMgdGhlIGNvbG9ycyAobGVmdCB0byByaWdodCkgb2Ygcm93IGkgb2YgdGhlIGdyaWQgd2l0aCBOIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB3aGljaCBhcmUgMSBmb3IgYmxhY2sgYW5kIDAgZm9yIHdoaXRlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lcyAxLi5NOiBFYWNoIGxpbmUgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIGVhY2ggc3BlY2lmeWluZyBob3cgbWFueSB0aW1lcyB0byBmbGlwIHRoYXQgcGFydGljdWxhciBsb2NhdGlvbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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