실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
농부 철수는 집 밖에 오래된 거울 몇 개를 두었고, 장난스런 강아지들은 가로 N개, 세로 M개의 직사각형 형태로 땅 위에 거울을 설치했다.
각 정사각형 안에는 두 개의 대각선 반대 모퉁이 사이에 이중면 거울이 놓여져 있다. 가능한 구성은 두 가지이다.
아래 왼쪽 모서리와 위 오른쪽 모서리를 연결 : "/" 문자
위 왼쪽 모서리와 아래 오른쪽 모서리를 연결 : "\" 문자
어느 날 저녁, 강아지 바둑이는 레이저 포인터를 들고 거울이 설치된 곳으로 갔다. 필드 밖에 서서 그녀는 빛의 광선을 필드의 가로와 세로를 따라 수평이나 수직으로 비추게 하여, 몇몇 거울에서 반사되게 한다.
거울이 대각선으로 모두 배열되어 있기 때문에, 거울에서 반사되는 수평 광선의 경우 수직으로 진행하게 되며, 반대의 경우도 마찬가지이다. 바둑이는 그녀의 빛의 광선이 동시에 반사될 수 있는 거울의 최대 수가 궁금하다. 거울 필드의 배치를 고려해서 거울의 최대 수는 몇 개일까?
문제 설명의 애매함 때문에 이 문제에 대한 대답은 두 가지였다: 최대 반사 횟수 또는 최대 거울 수. 여기에 포함된 테스트 데이터는 출력 결과에서 두 수를 모두 포함하고 있지만, USACO 서버에서의 채점은 둘 중 하나만 필요하다.
3 3 /\\ \\\ /\/
3
출처: USACO 2014 February Contest, Bronze Problem 1. Mirror Field