문제2005--전선 잇기

2005: 전선 잇기

실행시간 제한: 5 Sec  메모리사용 제한: 128 MB
제출: 74  통과: 17
[제출] [채점기록] [묻고답하기]

문제 설명

N×M 개의 정사각형 타일들로 이뤄진 전자회로가 주어진다. 타일은 두 개의 마주보는 꼭지점이 전선으로 이어져 있다.

아래의 그림과 같이 왼쪽 위 모서리에 전원이 연결 되어 있고, 전구는 오른쪽 아래 모서리에 연결되어있다. 전원에서 전구로 가는 전선의 연결이 존재할 때만 불이 켜진다. 초기 배치로는 전구에 불이 켜지지 않을 수 있으며, 타일들은 90도로 회전을 시킬 수 있다.

회전을 시키는 횟수를 최소화 하여 전구를 킬 수 있는 프로그램을 작성하라.

입력 설명

입력의 첫 줄에 N과 M이 주어진다(1 ≤ N,M ≤ 500).

그 다음 줄부터 N행 M열로 타일들의 상태 ‘\’(왼쪽 위 모서리 에서 오른쪽 아래 모서리로 전선이 이어진 경우) 혹은 ‘/’ (반대의 경우)가 주어진다.

출력 설명

전구를 키기 위한 최소 회전 수를 출력한다. 만약 불가능 할 경우에는 따옴표 없이 “NO SOLUTION”을 출력한다.

입력 예시 Copy

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

출력 예시 Copy

1

출처/분류