시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 114 32 30 29.703%

문제

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

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

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

입력

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

출력

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

예제 입력

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

예제 출력

1

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 3번