시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB195813712257423.548%

문제

크기가 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
W3sicHJvYmxlbV9pZCI6IjYwODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4MDhcdWM3NzRcdWM4MDAgXHVkMWI1XHVjMmUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgMSZ0aW1lczsxXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzQgVyZ0aW1lcztIIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM5YzBcdWIzYzRcdWM3NTggXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWJlNDggXHVjZTc4XHVjNzc0XHVhYzcwXHViMDk4IFx1YmNiZFx1Yzc3NFx1YmE3MCwgXHViNDUwIFx1Y2U3OFx1Yzc0MCAmIzM5Ozxjb2RlPkM8XC9jb2RlPiYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4mIzM5Ozxjb2RlPkM8XC9jb2RlPiYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViNDUwIFx1Y2U3OFx1Yzc0NCBcdWI4MDhcdWM3NzRcdWM4MDBcdWI4NWMgXHVkMWI1XHVjMmUwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWMxMjRcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3MFx1YzZiOCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI4MDhcdWM3NzRcdWM4MDBcdWI4NWMgXHVkMWI1XHVjMmUwXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWI0NTAgXHVjZTc4XHVjNzQ0IFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjgwOFx1Yzc3NFx1YzgwMFx1YjI5NCBDXHVjNWQwXHVjMTFjXHViOWNjIFx1YmMxY1x1YzBhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWJlNDggXHVjZTc4XHVjNWQwIFx1YWM3MFx1YzZiOCgmIzM5Ozxjb2RlPlwvPFwvY29kZT4mIzM5OywgJiMzOTs8Y29kZT5cXDxcL2NvZGU+JiMzOTspXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzExYyBcdWJjMjlcdWQ1YTVcdWM3NDQgOTBcdWIzYzQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIEggPSA4LCBXID0gN1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM3NzRcdWFjZTAsIFx1YmU0OCBcdWNlNzhcdWM3NDAgJiMzOTs8Y29kZT4uPFwvY29kZT4mIzM5OywgXHViY2JkXHVjNzQwICYjMzk7PGNvZGU+KjxcL2NvZGU+JiMzOTtcdWI4NWMgXHViMDk4XHVkMGMwXHViMGM4XHViMmU0LiBcdWM2N2NcdWNhYmRcdWM3NDAgXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkYywgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQwIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NTggXHVhYzcwXHVjNmI4XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWI0NTAgJiMzOTs8Y29kZT5DPFwvY29kZT4mIzM5O1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG43IC4gLiAuIC4gLiAuIC4gICAgICAgICA3IC4gLiAuIC4gLiAuIC5cclxuNiAuIC4gLiAuIC4gLiBDICAgICAgICAgNiAuIC4gLiAuIC4gXC8tQ1xyXG41IC4gLiAuIC4gLiAuICogICAgICAgICA1IC4gLiAuIC4gLiB8ICpcclxuNCAqICogKiAqICogLiAqICAgICAgICAgNCAqICogKiAqICogfCAqXHJcbjMgLiAuIC4gLiAqIC4gLiAgICAgICAgIDMgLiAuIC4gLiAqIHwgLlxyXG4yIC4gLiAuIC4gKiAuIC4gICAgICAgICAyIC4gLiAuIC4gKiB8IC5cclxuMSAuIEMgLiAuICogLiAuICAgICAgICAgMSAuIEMgLiAuICogfCAuXHJcbjAgLiAuIC4gLiAuIC4gLiAgICAgICAgIDAgLiBcXC0tLS0tLS1cLyAuXHJcbiAgMCAxIDIgMyA0IDUgNiAgICAgICAgICAgMCAxIDIgMyA0IDUgNlxyXG48XC9wcmU+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBXXHVjNjQwIEhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFcsIEggJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgSFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOWMwXHViM2M0XHVjNzU4IFx1YWMwMSBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPi48XC9jb2RlPjogXHViZTQ4IFx1Y2U3ODxcL2xpPlxyXG5cdDxsaT48Y29kZT4qPFwvY29kZT46IFx1YmNiZDxcL2xpPlxyXG5cdDxsaT48Y29kZT5DPFwvY29kZT46IFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2U3ODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiYjMzk7PGNvZGU+QzxcL2NvZGU+JiMzOTtcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YjQ1MCBcdWFjMWNcdWM3NzRcdWFjZTAsIFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3ODVcdWI4MjVcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgQ1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzcwXHVjNmI4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjYwODciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYXNlcnBob25lcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNvd3MgaGF2ZSBhIG5ldyBsYXNlci1iYXNlZCBzeXN0ZW0gc28gdGhleSBjYW4gaGF2ZSBjYXN1YWwgY29udmVyc2F0aW9ucyB3aGlsZSBvdXQgaW4gdGhlIHBhc3R1cmUgd2hpY2ggaXMgbW9kZWxlZCBhcyBhIFcgeCBIIGdyaWQgb2YgcG9pbnRzICgxICZsdDs9IFcgJmx0Oz0gMTAwOyAxICZsdDs9IEggJmx0Oz0gMTAwKS48XC9wPlxyXG5cclxuPHA+VGhlIHN5c3RlbSByZXF1aXJlcyBhIHNvcnQgb2YgbGluZS1vZi1zaWdodCBjb25uZWN0aXZpdHkgaW4gb3JkZXIgdG8gc3VzdGFpbiBjb21tdW5pY2F0aW9uLiBUaGUgcGFzdHVyZSwgb2YgY291cnNlLCBoYXMgcm9ja3MgYW5kIHRyZWVzIHRoYXQgZGlzcnVwdCB0aGUgY29tbXVuaWNhdGlvbiBidXQgdGhlIGNvd3MgaGF2ZSBwdXJjaGFzZWQgZGlhZ29uYWwgbWlycm9ycyAoJiMzOTtcLyYjMzk7IGFuZCAmIzM5O1xcJiMzOTsgYmVsb3cpIHRoYXQgZGVmbGVjdCB0aGUgbGFzZXIgYmVhbSB0aHJvdWdoIGEgOTAgZGVncmVlIHR1cm4uIEJlbG93IGlzIGEgbWFwIHRoYXQgaWxsdXN0cmF0ZXMgdGhlIHByb2JsZW0uPFwvcD5cclxuXHJcbjxwPkggaXMgOCBhbmQgVyBpcyA3IGZvciB0aGlzIG1hcC4gVGhlIHR3byBjb21tdW5pY2F0aW5nIGNvd3MgYXJlIG5vdGF0ZWQgYXMgJiMzOTtDJiMzOTtzOyByb2NrcyBhbmQgb3RoZXIgYmxvY2tpbmcgZWxlbWVudHMgYXJlIG5vdGF0ZWQgYXMgJiMzOTsqJiMzOTtzOjxcL3A+XHJcblxyXG48cHJlPlxyXG43IC4gLiAuIC4gLiAuIC4gICAgICAgICA3IC4gLiAuIC4gLiAuIC5cclxuNiAuIC4gLiAuIC4gLiBDICAgICAgICAgNiAuIC4gLiAuIC4gXC8tQ1xyXG41IC4gLiAuIC4gLiAuICogICAgICAgICA1IC4gLiAuIC4gLiB8ICpcclxuNCAqICogKiAqICogLiAqICAgICAgICAgNCAqICogKiAqICogfCAqXHJcbjMgLiAuIC4gLiAqIC4gLiAgICAgICAgIDMgLiAuIC4gLiAqIHwgLlxyXG4yIC4gLiAuIC4gKiAuIC4gICAgICAgICAyIC4gLiAuIC4gKiB8IC5cclxuMSAuIEMgLiAuICogLiAuICAgICAgICAgMSAuIEMgLiAuICogfCAuXHJcbjAgLiAuIC4gLiAuIC4gLiAgICAgICAgIDAgLiBcXC0tLS0tLS1cLyAuXHJcbiAgMCAxIDIgMyA0IDUgNiAgICAgICAgICAgMCAxIDIgMyA0IDUgNlxyXG48XC9wcmU+XHJcblxyXG48cD5EZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1pcnJvcnMgTSB0aGF0IG11c3QgYmUgaW5zdGFsbGVkIHRvIG1haW50YWluIGxhc2VyIGNvbW11bmljYXRpb24gYmV0d2VlbiB0aGUgdHdvIGNvd3MsIGEgZmVhdCB3aGljaCBpcyBhbHdheXMgcG9zc2libGUgaW4gdGhlIGdpdmVuIHRlc3QgZGF0YS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gc3BhY2Ugc2VwYXJhdGVkIGludGVnZXJzOiBXIGFuZCBIPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLkgrMTogVGhlIGVudGlyZSBwYXN0dXJlLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE08XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO January 2009 Contest > Silver 3번