시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 166 37 33 25.000%

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최소값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 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

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

  • .: 빈 칸
  • *: 벽
  • C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최소값을 출력한다.

예제 입력 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력 1

3

힌트

W3sicHJvYmxlbV9pZCI6IjYwODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4MDhcdWM3NzRcdWM4MDAgXHVkMWI1XHVjMmUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgMSZ0aW1lczsxXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzQgVyZ0aW1lcztIIFx1ZDA2Y1x1YWUzMFx1Yzc1OCZuYnNwO1x1YzljMFx1YjNjNFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YmU0OCBcdWNlNzhcdWM3NzRcdWFjNzBcdWIwOTggXHViY2JkXHVjNzc0XHViYTcwLCBcdWI0NTAgXHVjZTc4XHVjNzQwICYjMzk7PGNvZGU+QzxcL2NvZGU+JiMzOTtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiYjMzk7PGNvZGU+QzxcL2NvZGU+JiMzOTtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVjZTc4XHVjNzQ0IFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjg1YyBcdWQxYjVcdWMyZTBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzcwXHVjNmI4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjg1YyBcdWQxYjVcdWMyZTBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YjQ1MCBcdWNlNzhcdWM3NDQgXHViODA4XHVjNzc0XHVjODAwXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODA4XHVjNzc0XHVjODAwXHViMjk0IENcdWM1ZDBcdWMxMWNcdWI5Y2MgXHViYzFjXHVjMGFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YmU0OCBcdWNlNzhcdWM1ZDAgXHVhYzcwXHVjNmI4KCYjMzk7PGNvZGU+XC88XC9jb2RlPiYjMzk7LCAmIzM5Ozxjb2RlPlxcPFwvY29kZT4mIzM5OylcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTc0XHVjMTFjIFx1YmMyOVx1ZDVhNVx1Yzc0NCA5MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBIID0gOCwgVyA9IDdcdWM3NzggXHVhY2JkXHVjNmIwXHVjNzc0XHVhY2UwLCBcdWJlNDggXHVjZTc4XHVjNzQwICYjMzk7PGNvZGU+LjxcL2NvZGU+JiMzOTssIFx1YmNiZFx1Yzc0MCAmIzM5Ozxjb2RlPio8XC9jb2RlPiYjMzk7XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1YjJlNC4gXHVjNjdjXHVjYWJkXHVjNzQwIFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGMsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHVjNzU4IFx1YWM3MFx1YzZiOFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHViNDUwICYjMzk7PGNvZGU+QzxcL2NvZGU+JiMzOTtcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTVjIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuNyAuIC4gLiAuIC4gLiAuICAgICAgICAgNyAuIC4gLiAuIC4gLiAuXHJcbjYgLiAuIC4gLiAuIC4gQyAgICAgICAgIDYgLiAuIC4gLiAuIFwvLUNcclxuNSAuIC4gLiAuIC4gLiAqICAgICAgICAgNSAuIC4gLiAuIC4gfCAqXHJcbjQgKiAqICogKiAqIC4gKiAgICAgICAgIDQgKiAqICogKiAqIHwgKlxyXG4zIC4gLiAuIC4gKiAuIC4gICAgICAgICAzIC4gLiAuIC4gKiB8IC5cclxuMiAuIC4gLiAuICogLiAuICAgICAgICAgMiAuIC4gLiAuICogfCAuXHJcbjEgLiBDIC4gLiAqIC4gLiAgICAgICAgIDEgLiBDIC4gLiAqIHwgLlxyXG4wIC4gLiAuIC4gLiAuIC4gICAgICAgICAwIC4gXFwtLS0tLS0tXC8gLlxyXG4gIDAgMSAyIDMgNCA1IDYgICAgICAgICAgIDAgMSAyIDMgNCA1IDZcclxuPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgV1x1YzY0MCBIXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBXLCBIICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEhcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWFjMDEgXHViYjM4XHVjNzkwXHVhYzAwIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT4uPFwvY29kZT46IFx1YmU0OCBcdWNlNzg8XC9saT5cclxuXHQ8bGk+PGNvZGU+KjxcL2NvZGU+OiBcdWJjYmQ8XC9saT5cclxuXHQ8bGk+PGNvZGU+QzxcL2NvZGU+OiBcdWI4MDhcdWM3NzRcdWM4MDBcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNlNzg8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mIzM5Ozxjb2RlPkM8XC9jb2RlPiYjMzk7XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWI0NTAgXHVhYzFjXHVjNzc0XHVhY2UwLCBcdWI4MDhcdWM3NzRcdWM4MDBcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzg1XHViODI1XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIENcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMxMjRcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3MFx1YzZiOCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MDg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFzZXJwaG9uZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb3dzIGhhdmUgYSBuZXcgbGFzZXItYmFzZWQgc3lzdGVtIHNvIHRoZXkgY2FuIGhhdmUgY2FzdWFsIGNvbnZlcnNhdGlvbnMgd2hpbGUgb3V0IGluIHRoZSBwYXN0dXJlIHdoaWNoIGlzIG1vZGVsZWQgYXMgYSBXIHggSCBncmlkIG9mIHBvaW50cyAoMSAmbHQ7PSBXICZsdDs9IDEwMDsgMSAmbHQ7PSBIICZsdDs9IDEwMCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzeXN0ZW0gcmVxdWlyZXMgYSBzb3J0IG9mIGxpbmUtb2Ytc2lnaHQgY29ubmVjdGl2aXR5IGluIG9yZGVyIHRvIHN1c3RhaW4gY29tbXVuaWNhdGlvbi4gVGhlIHBhc3R1cmUsIG9mIGNvdXJzZSwgaGFzIHJvY2tzIGFuZCB0cmVlcyB0aGF0IGRpc3J1cHQgdGhlIGNvbW11bmljYXRpb24gYnV0IHRoZSBjb3dzIGhhdmUgcHVyY2hhc2VkIGRpYWdvbmFsIG1pcnJvcnMgKCYjMzk7XC8mIzM5OyBhbmQgJiMzOTtcXCYjMzk7IGJlbG93KSB0aGF0IGRlZmxlY3QgdGhlIGxhc2VyIGJlYW0gdGhyb3VnaCBhIDkwIGRlZ3JlZSB0dXJuLiBCZWxvdyBpcyBhIG1hcCB0aGF0IGlsbHVzdHJhdGVzIHRoZSBwcm9ibGVtLjxcL3A+XHJcblxyXG48cD5IIGlzIDggYW5kIFcgaXMgNyBmb3IgdGhpcyBtYXAuIFRoZSB0d28gY29tbXVuaWNhdGluZyBjb3dzIGFyZSBub3RhdGVkIGFzICYjMzk7QyYjMzk7czsgcm9ja3MgYW5kIG90aGVyIGJsb2NraW5nIGVsZW1lbnRzIGFyZSBub3RhdGVkIGFzICYjMzk7KiYjMzk7czo8XC9wPlxyXG5cclxuPHByZT5cclxuNyAuIC4gLiAuIC4gLiAuICAgICAgICAgNyAuIC4gLiAuIC4gLiAuXHJcbjYgLiAuIC4gLiAuIC4gQyAgICAgICAgIDYgLiAuIC4gLiAuIFwvLUNcclxuNSAuIC4gLiAuIC4gLiAqICAgICAgICAgNSAuIC4gLiAuIC4gfCAqXHJcbjQgKiAqICogKiAqIC4gKiAgICAgICAgIDQgKiAqICogKiAqIHwgKlxyXG4zIC4gLiAuIC4gKiAuIC4gICAgICAgICAzIC4gLiAuIC4gKiB8IC5cclxuMiAuIC4gLiAuICogLiAuICAgICAgICAgMiAuIC4gLiAuICogfCAuXHJcbjEgLiBDIC4gLiAqIC4gLiAgICAgICAgIDEgLiBDIC4gLiAqIHwgLlxyXG4wIC4gLiAuIC4gLiAuIC4gICAgICAgICAwIC4gXFwtLS0tLS0tXC8gLlxyXG4gIDAgMSAyIDMgNCA1IDYgICAgICAgICAgIDAgMSAyIDMgNCA1IDZcclxuPFwvcHJlPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtaXJyb3JzIE0gdGhhdCBtdXN0IGJlIGluc3RhbGxlZCB0byBtYWludGFpbiBsYXNlciBjb21tdW5pY2F0aW9uIGJldHdlZW4gdGhlIHR3byBjb3dzLCBhIGZlYXQgd2hpY2ggaXMgYWx3YXlzIHBvc3NpYmxlIGluIHRoZSBnaXZlbiB0ZXN0IGRhdGEuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2VyczogVyBhbmQgSDxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5IKzE6IFRoZSBlbnRpcmUgcGFzdHVyZS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBNPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=