전구를 켜라
시간 제한1초메모리 제한128 MB
N×M 격자의 각 타일이 '/' 또는 '\' 대각선을 가질 때, 좌상단에서 우하단까지 대각선이 연결되도록 뒤집어야 하는 타일의 최소 개수를 0/1 가중치 최단경로로 구하는 문제입니다.
문제
선영이는 세로 N, 가로 M인 직사각형 전자 회로를 설계하고 있다. 회로는 N × M개의 정사각형 타일로 이루어져 있으며, 각 타일의 변은 직사각형의 변과 평행하다. 각 타일에는 두 개의 마주 보는 꼭짓점을 잇는 전선이 하나 놓여 있다.
전원은 회로의 왼쪽 위 모서리에, 전구는 오른쪽 아래 모서리에 연결되어 있다. 전원에서 전구까지 전선을 따라 이동할 수 있는 경로가 있을 때에만 전구가 켜진다. 선영이는 전구를 켜기 위해 필요한 만큼의 타일을 각각 90도 회전시킬 수 있다.
위 그림에서는 전구가 꺼져 있다. 오른쪽에서 두 번째 열에 있는 타일 중 하나를 90도 회전시키면 전원과 전구가 연결되어 전구가 켜진다. 전구를 켜기 위해 회전해야 하는 타일 수의 최솟값을 구하시오.
입력
첫째 줄에 정수 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 전자 회로의 현재 상태가 주어진다. 각 줄은 길이가 M이며, 각 문자는 / 또는 \이다.
1 ≤ N, M ≤ 500
출력
전구를 켤 수 있다면 회전해야 하는 타일 수의 최솟값을 출력한다. 전구를 켤 수 없다면 NO SOLUTION을 출력한다.