실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
소들은 그들이 광대한 목장에서 가볍게 대화할 수 있도록 새로운 레이저 기반 시스템을 가지고 있습니다. 이 목장은 W x H 그리드의 점들로 모델링됩니다 (1 <= W <= 100; 1 <= H <= 100).
시스템은 통신을 유지하기 위해 시야 연결성이 필요합니다. 물론 목초지에는 통신을 방해하는 바위와 나무가 있지만, 소들은 대각선 모양의 거울('/'와 '\')을 구입하여 레이저 빔을 90도로 반사시킬 수 있습니다. 아래에는 이 문제를 설명하는 지도가 나와 있습니다.
이 지도에서 H는 8이고, W는 7입니다. 대화하는 두 소는 'C'로 표시되며, 바위와 다른 차단 요소들은 '*'로 표시됩니다:
7 . . . . . . . 7 . . . . . . . 6 . . . . . . C 6 . . . . . /-C 5 . . . . . . * 5 . . . . . | * 4 * * * * * . * 4 * * * * * | * 3 . . . . * . . 3 . . . . * | . 2 . . . . * . . 2 . . . . * | . 1 . C . . * . . 1 . C . . * | . 0 . . . . . . . 0 . \-------/ . 0 1 2 3 4 5 6 0 1 2 3 4 5 6
두 소 사이의 레이저 통신을 유지하기 위해 설치해야 하는 거울의 최소 수 M을 결정하세요. 이는 주어진 테스트 데이터에서 항상 가능한 기능입니다.
7 8 ....... ......C ......* *****.* ....*.. ....*.. .C..*.. .......
3