시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB137354740437.581%

문제

선영이는 N × M 직사각형 크기의 전자 회로를 디자인 하고 있다. 회로에는 N × M개의 정사각형 타일이 있고, 모두 직사각형의 변과 평행하다. 모든 타일은 두 개의 마주보는 꼭짓점이 전선으로 연결되어 있다. (그림 참조)

전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결되어 있다. 전구는  전원에서 전구로 가는 경로가 있을 때만 불이 켜진다. 전구에 불을 켜기 위해서, 선영이는 몇개의 타일을 90도 회전 시킬 수 있다.

위의 그림에서 전구는 꺼져있다. 만약 오른쪽에서 2번째 열 중 아무 칸이나 90도 회전시킨다면, 전원과 전구는 연결되어 전구가 켜지게 된다. 전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 전자 회로의 상태가 주어진다. 상태는 / 또는 \이다. (1 ≤ N, M ≤ 500)

출력

첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다.

예제 입력 1

3 5
\\/\\
\\///
/\\\\

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjI0MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWFkNmNcdWI5N2MgXHVjZjFjXHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgTiAmdGltZXM7IE0gXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWM4MDRcdWM3OTAgXHVkNjhjXHViODVjXHViOTdjIFx1YjUxNFx1Yzc5MFx1Yzc3OCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ2OGNcdWI4NWNcdWM1ZDBcdWIyOTQgTiAmdGltZXM7IE1cdWFjMWNcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBjMFx1Yzc3Y1x1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YmFhOFx1YjQ1MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViY2MwXHVhY2ZjIFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDBjMFx1Yzc3Y1x1Yzc0MCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YjljOFx1YzhmY1x1YmNmNFx1YjI5NCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgXHVjODA0XHVjMTIwXHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIChcdWFkZjhcdWI5YmMgXHVjYzM4XHVjODcwKTxcL3A+XHJcblxyXG48cD5cdWM4MDRcdWM2ZDBcdWM3NDAgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWJhYThcdWMxMWNcdWI5YWNcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHVjODA0XHVhZDZjXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHViYWE4XHVjMTFjXHViOWFjXHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzgwNFx1YWQ2Y1x1YjI5NCAmbmJzcDtcdWM4MDRcdWM2ZDBcdWM1ZDBcdWMxMWMgXHVjODA0XHVhZDZjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjljYyBcdWJkODhcdWM3NzQgXHVjZjFjXHVjOWM0XHViMmU0LiBcdWM4MDRcdWFkNmNcdWM1ZDAgXHViZDg4XHVjNzQ0IFx1Y2YxY1x1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJhODdcdWFjMWNcdWM3NTggXHVkMGMwXHVjNzdjXHVjNzQ0IDkwXHViM2M0IFx1ZDY4Y1x1YzgwNCBcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC80NmM5ZWQ5ZS0yN2UzLTRlMzItYTE0NC0wOTYyYjgxMzM0N2VcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI4OXB4OyBoZWlnaHQ6IDE5NXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YzgwNFx1YWQ2Y1x1YjI5NCBcdWFlYmNcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDBcdWMxMWMgMlx1YmM4OFx1YzlmOCBcdWM1ZjQgXHVjOTExIFx1YzU0NFx1YmIzNCBcdWNlNzhcdWM3NzRcdWIwOTggOTBcdWIzYzQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4XHViMmU0XHViYTc0LCBcdWM4MDRcdWM2ZDBcdWFjZmMgXHVjODA0XHVhZDZjXHViMjk0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM4MDRcdWFkNmNcdWFjMDAgXHVjZjFjXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjODA0XHVhZDZjXHVjNWQwIFx1YmQ4OFx1Yzc0NCBcdWNmMWNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjNjY1x1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODA0XHVjNzkwIFx1ZDY4Y1x1Yjg1Y1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWQwZGNcdWIyOTQgPGNvZGU+XC88XC9jb2RlPiBcdWI2MTBcdWIyOTQgPGNvZGU+XFw8XC9jb2RlPlx1Yzc3NFx1YjJlNC4gKDEgJmxlOyBOLCBNICZsZTsgNTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgwNFx1YWQ2Y1x1YzVkMCBcdWJkODhcdWM3NDQgXHVjZjFjXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQsIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjZTc4XHVjNzQ0IFx1YjNjY1x1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NjBcdWI1NGNcdWIyOTQgJnF1b3Q7Tk8gU09MVVRJT04mcXVvdDtcdWM3NDQgXHViNTMwXHVjNjM0XHVkNDVjIFx1YzVjNlx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjQyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN3aXRjaCB0aGUgTGFtcCBPbiIsImRlc2NyaXB0aW9uIjoiPHA+Q2FzcGVyIGlzIGRlc2lnbmluZyBhbiBlbGVjdHJvbmljIGNpcmN1aXQgb24gYSBOICZ0aW1lczsgTSByZWN0YW5ndWxhciBncmlkIHBsYXRlLiBUaGVyZSBhcmUgTiAmdGltZXM7IE0gc3F1YXJlIHRpbGVzIHRoYXQgYXJlIGFsaWduZWQgdG8gdGhlIGdyaWQgb24gdGhlIHBsYXRlLiBUd28gKG91dCBvZiBmb3VyKSBvcHBvc2l0ZSBjb3JuZXJzIG9mIGVhY2ggdGlsZSBhcmUgY29ubmVjdGVkIGJ5IGEgd2lyZS48XC9wPlxyXG5cclxuPHA+QSBwb3dlciBzb3VyY2UgaXMgY29ubmVjdGVkIHRvIHRoZSB0b3AgbGVmdCBjb3JuZXIgb2YgdGhlIHBsYXRlLiBBIGxhbXAgaXMgY29ubmVjdGVkIHRvIHRoZSBib3R0b20gcmlnaHQgY29ybmVyIG9mIHRoZSBwbGF0ZS4gVGhlIGxhbXAgaXMgb24gb25seSBpZiB0aGVyZSBpcyBhIHBhdGggb2Ygd2lyZXMgY29ubmVjdGluZyBwb3dlciBzb3VyY2UgdG8gbGFtcC4gSW4gb3JkZXIgdG8gc3dpdGNoIHRoZSBsYW1wIG9uLCBhbnkgbnVtYmVyIG9mIHRpbGVzIGNhbiBiZSB0dXJuZWQgYnkgOTAmZGVnOyAoaW4gYm90aCBkaXJlY3Rpb25zKS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC80NmM5ZWQ5ZS0yN2UzLTRlMzItYTE0NC0wOTYyYjgxMzM0N2VcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI4OXB4OyBoZWlnaHQ6IDE5NXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGUgcGljdHVyZSBhYm92ZSB0aGUgbGFtcCBpcyBvZmYuIElmIGFueSBvbmUgb2YgdGhlIHRpbGVzIGluIHRoZSBzZWNvbmQgY29sdW1uIGZyb20gdGhlIHJpZ2h0IGlzIHR1cm5lZCBieSA5MCZkZWc7XHUwMDBlLCBwb3dlciBzb3VyY2UgYW5kIGxhbXAgZ2V0IGNvbm5lY3RlZCwgYW5kIHRoZSBsYW1wIGlzIG9uLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gXHVmYjAxbmQgb3V0IHRoZSBtaW5pbWFsIG51bWJlciBvZiB0aWxlcyB0aGF0IGhhdmUgdG8gYmUgdHVybmVkIGJ5IDkwJmRlZztcdTAwMGUgdG8gc3dpdGNoIHRoZSBsYW1wIG9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgTiBhbmQgTSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHBsYXRlLiBJbiBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyB0aGVyZSBhcmUgTSBzeW1ib2xzICZuZGFzaDsgZWl0aGVyIDxjb2RlPlxcPFwvY29kZT4gb3IgPGNvZGU+XC88XC9jb2RlPiAmbmRhc2g7IHdoaWNoIGluZGljYXRlIHRoZSBkaXJlY3Rpb24gb2YgdGhlIHdpcmUgY29ubmVjdGluZyB0aGUgb3Bwb3NpdGUgdmVydGljZXMgb2YgdGhlIGNvcnJlc3BvbmRpbmcgdGlsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGVyZSBtdXN0IGJlIGV4YWN0bHkgb25lIGxpbmUgb2Ygb3V0cHV0LiBJZiBpdCBpcyBwb3NzaWJsZSB0byBzd2l0Y2ggdGhlIGxhbXAgb24sIHRoaXMgbGluZSBtdXN0IGNvbnRhaW4gb25seSBvbmUgaW50ZWdlciBudW1iZXI6IHRoZSBtaW5pbWFsIG51bWJlciBvZiB0aWxlcyB0aGF0IGhhdmUgdG8gYmUgdHVybmVkIHRvIHN3aXRjaCBvbiB0aGUgbGFtcC4gSWYgaXQgaXMgbm90IHBvc3NpYmxlLCBvdXRwdXQgdGhlIHN0cmluZzogTk8gU09MVVRJT048XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOLCBNICZsZTsgNTAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 3번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013