파일 업로드

레이저폰

profile
실행 시간 제한메모리 제한
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을 결정하세요. 이는 주어진 테스트 데이터에서 항상 가능한 기능입니다.

💻 입력
  • 첫째 줄 : 두 개의 공백으로 구분된 정수 : W와 H
  • 2번째 줄부터 H+1번째 줄까지 : 전체 목장.
🖨️ 출력
  • 첫 번째 줄 : 한 개의 정수 : M

💻 예제 입력 1
7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......
🖨️ 예제 출력 1
3

출처: USACO 2009 January Silver 3