레이팅 미적용농부 존이 낡은 거울 몇 개를 집 밖에 놓아두었는데, 소들이 그것을 훔쳐 갔다!
소들은 N x M 칸 크기의 직사각형 들판 (1 <= N, M <= 1,000)에 거울들을 설치해 놓았다. 각 칸에는 그 칸의 마주 보는 두 꼭짓점 사이에 양면 거울을 하나씩 놓았다. 이 두 가지 배치는 '/' 문자(왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점을 잇는 거울)와 '\' 문자(왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점을 잇는 거울)로 표현된다.
어느 저녁, 베시가 레이저 포인터를 들고 거울 들판으로 나왔다. 들판 밖에 서서, 베시는 들판의 어떤 행이나 열을 따라 수평 또는 수직으로 광선을 쏘고, 광선은 몇 개의 거울에 반사된다. 거울이 모두 대각선 방향으로 놓여 있으므로, 거울에 반사된 수평 광선은 수직으로 이동하게 되고 그 반대도 마찬가지이다. 베시는 자신의 광선이 최대 몇 개의 거울에 반사될 수 있는지 궁금해한다. 거울 들판의 배치가 주어질 때, 베시가 이 수를 계산하는 것을 도와주시오.
첫째 줄에 공백으로 구분된 정수 N과 M이 주어진다.
둘째 줄부터 1+N번째 줄까지, 각 줄에 거울 들판의 한 행을 나타내는 M개의 '/' 또는 '\' 문자가 주어진다.
거울 들판 밖에서 출발한 수평 또는 수직 광선이 반사될 수 있는 최대 횟수를 나타내는 정수 하나를 출력한다. 무한히 반사될 수 있다면 -1을 출력한다.
mirror.in · 출력을 쓸 파일 mirror.out3 3
/\\
\\\
/\/3Output details: Bessie can shine the beam downwards above the middle column to have it reflected 3 times.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > February > Bronze