시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 283 93 78 34.361%

문제

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjI0MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWFkNmNcdWI5N2MgXHVjZjFjXHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgTipNIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODA0XHVjNzkwIFx1ZDY4Y1x1Yjg1Y1x1Yjk3YyBcdWI1MTRcdWM3OTBcdWM3NzggXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkNjhjXHViODVjXHVjNWQwXHViMjk0IE4qTVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGMwXHVjNzdjXHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHViYWE4XHViNDUwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWFjZmMgXHVkM2M5XHVkNTg5XHVkNTU4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVkMGMwXHVjNzdjXHVjNzQwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViOWM4XHVjOGZjXHViY2Y0XHViMjk0IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWM4MDRcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gKFx1YWRmOFx1YjliYyBcdWNjMzhcdWM4NzApPFwvcD5cclxuXHJcbjxwPlx1YzgwNFx1YzZkMFx1Yzc0MCBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1YmFhOFx1YzExY1x1YjlhY1x1YzVkMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWM4MDRcdWFkNmNcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWJhYThcdWMxMWNcdWI5YWNcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjODA0XHVhZDZjXHViMjk0ICZuYnNwO1x1YzgwNFx1YzZkMFx1YzVkMFx1YzExYyBcdWM4MDRcdWFkNmNcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjXHViOWNjIFx1YmQ4OFx1Yzc3NCBcdWNmMWNcdWM5YzRcdWIyZTQuIFx1YzgwNFx1YWQ2Y1x1YzVkMCBcdWJkODhcdWM3NDQgXHVjZjFjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YmE4N1x1YWMxY1x1Yzc1OCBcdWQwYzBcdWM3N2NcdWM3NDQgOTBcdWIzYzQgXHVkNjhjXHVjODA0IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA3XC9sYW1wLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxMHB4OyB3aWR0aDozMDdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YzgwNFx1YWQ2Y1x1YjI5NCBcdWFlYmNcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDBcdWMxMWMgMlx1YmM4OFx1YzlmOCBcdWM1ZjQgXHVjOTExIFx1YzU0NFx1YmIzNCBcdWNlNzhcdWM3NzRcdWIwOTggOTBcdWIzYzQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4XHViMmU0XHViYTc0LCBcdWM4MDRcdWM2ZDBcdWFjZmMgXHVjODA0XHVhZDZjXHViMjk0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM4MDRcdWFkNmNcdWFjMDAgXHVjZjFjXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjODA0XHVhZDZjXHVjNWQwIFx1YmQ4OFx1Yzc0NCBcdWNmMWNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjNjY1x1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODA0XHVjNzkwIFx1ZDY4Y1x1Yjg1Y1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWQwZGNcdWIyOTQgXC8gXHViNjEwXHViMjk0IFxcXHVjNzc0XHViMmU0LiAoMSZsdDs9TixNJmx0Oz01MDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODA0XHVhZDZjXHVjNWQwIFx1YmQ4OFx1Yzc0NCBcdWNmMWNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCwgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWNlNzhcdWM3NDQgXHViM2NjXHViODI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU2MFx1YjU0Y1x1YjI5NCAmcXVvdDtOTyBTT0xVVElPTiZxdW90O1x1Yzc0NCBcdWI1MzBcdWM2MzRcdWQ0NWMgXHVjNWM2XHVjNzc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNDIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3dpdGNoIHRoZSBMYW1wIE9uIiwiZGVzY3JpcHRpb24iOiI8cD5DYXNwZXIgaXMgZGVzaWduaW5nIGFuIGVsZWN0cm9uaWMgY2lyY3VpdCBvbiBhIE4gJnRpbWVzOyBNIHJlY3Rhbmd1bGFyIGdyaWQgcGxhdGUuIFRoZXJlIGFyZSBOICZ0aW1lczsgTSBzcXVhcmUgdGlsZXMgdGhhdCBhcmUgYWxpZ25lZCB0byB0aGUgZ3JpZCBvbiB0aGUgcGxhdGUuIFR3byAob3V0IG9mIGZvdXIpIG9wcG9zaXRlIGNvcm5lcnMgb2YgZWFjaCB0aWxlIGFyZSBjb25uZWN0ZWQgYnkgYSB3aXJlLjxcL3A+XHJcblxyXG48cD5BIHBvd2VyIHNvdXJjZSBpcyBjb25uZWN0ZWQgdG8gdGhlIHRvcCBsZWZ0IGNvcm5lciBvZiB0aGUgcGxhdGUuIEEgbGFtcCBpcyBjb25uZWN0ZWQgdG8gdGhlIGJvdHRvbSByaWdodCBjb3JuZXIgb2YgdGhlIHBsYXRlLiBUaGUgbGFtcCBpcyBvbiBvbmx5IGlmIHRoZXJlIGlzIGEgcGF0aCBvZiB3aXJlcyBjb25uZWN0aW5nIHBvd2VyIHNvdXJjZSB0byBsYW1wLiBJbiBvcmRlciB0byBzd2l0Y2ggdGhlIGxhbXAgb24sIGFueSBudW1iZXIgb2YgdGlsZXMgY2FuIGJlIHR1cm5lZCBieSA5MCZkZWc7IChpbiBib3RoIGRpcmVjdGlvbnMpLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA3XC9sYW1wLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxMHB4OyB3aWR0aDozMDdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGUgcGljdHVyZSBhYm92ZSB0aGUgbGFtcCBpcyBvZmYuIElmIGFueSBvbmUgb2YgdGhlIHRpbGVzIGluIHRoZSBzZWNvbmQgY29sdW1uIGZyb20gdGhlIHJpZ2h0IGlzIHR1cm5lZCBieSA5MCZkZWc7XHUwMDBlLCBwb3dlciBzb3VyY2UgYW5kIGxhbXAgZ2V0IGNvbm5lY3RlZCwgYW5kIHRoZSBsYW1wIGlzIG9uLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gXHVmYjAxbmQgb3V0IHRoZSBtaW5pbWFsIG51bWJlciBvZiB0aWxlcyB0aGF0IGhhdmUgdG8gYmUgdHVybmVkIGJ5IDkwJmRlZztcdTAwMGUgdG8gc3dpdGNoIHRoZSBsYW1wIG9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgTiBhbmQgTSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHBsYXRlLiBJbiBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyB0aGVyZSBhcmUgTSBzeW1ib2xzICZuZGFzaDsgZWl0aGVyIFxcIG9yIFwvICZuZGFzaDsgd2hpY2ggaW5kaWNhdGUgdGhlIGRpcmVjdGlvbiBvZiB0aGUgd2lyZSBjb25uZWN0aW5nIHRoZSBvcHBvc2l0ZSB2ZXJ0aWNlcyBvZiB0aGUgY29ycmVzcG9uZGluZyB0aWxlLiAoMSAmbGU7IE4sIE0gJmxlOyA1MDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlcmUgbXVzdCBiZSBleGFjdGx5IG9uZSBsaW5lIG9mIG91dHB1dC4gSWYgaXQgaXMgcG9zc2libGUgdG8gc3dpdGNoIHRoZSBsYW1wIG9uLCB0aGlzIGxpbmUgbXVzdCBjb250YWluIG9ubHkgb25lIGludGVnZXIgbnVtYmVyOiB0aGUgbWluaW1hbCBudW1iZXIgb2YgdGlsZXMgdGhhdCBoYXZlIHRvIGJlIHR1cm5lZCB0byBzd2l0Y2ggb24gdGhlIGxhbXAuIElmIGl0IGlzIG5vdCBwb3NzaWJsZSwgb3V0cHV0IHRoZSBzdHJpbmc6IE5PIFNPTFVUSU9OPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 3번

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