시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
4.0 초 768 MB 425 34 (8%) 22
문제
홍준이는 $N \times M$ 직사각형 크기의 전자 회로를 디자인 하고 있다. 회로에는 $N \times M$개의 정사각형 타일이 있고, 모두 직사각형의 변과 평행하다. 모든 타일은 두 개의 마주보는 꼭지점이 전선으로 연결되어 있다. 전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결되어 있다. 전구는 전원에서 전구로 가는 경로가 있을 때만 불이 켜진다. 전구에 불을 켜기 위해서, 선영이는 몇개의 타일을 $90$도 회전 시킬 수 있다. ![lamp 예제](https://koitp.org/download_file/fe40592307a3a30e523ba3d75be1198597d827036c9b394fd93b1b138e00e14a/lamp.png/) 위의 그림에서 전구는 꺼져있다. 만약 오른쪽에서 $2$번째 열 중 아무 칸이나 $90$도 회전시킨다면, 전원과 전구는 연결되어 전구가 켜지게 된다. 전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최소값을 구하는 프로그램을 작성하시오. #### **부분 문제**
부분 문제 점수 $N, M$ 제한
1 10 $1 \le N, M \le 5$
2 20 $1 \le N, M \le 50$
3 30 $1 \le N, M \le 500$
4 40 $1 \le N, M \le 5,000$
입력
첫째 줄에 $N$과 $M$이 주어진다. 둘째 줄부터 $N$개의 줄에는 전자 회로의 상태가 주어진다. 상태는 / 또는 \이다. $(1 \le N,M \le 5,000)$
출력
첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다.
힌트
#### 입력 예제 ``` 3 5 \\/\\ \\/// /\\\\ ``` #### 출력 예제 ``` 1 ```