MLASERP - Laser Phones
Giới hạn- Thời gian: 0.227s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
FJ mua một hệ thống liên lạc mới cho đàn bò để chúng có thể trò chuyện với
nhau trong khi ăn cỏ. Đồng cỏ được mô tả bằng một lưới hình chữ nhật
kích thước WxH (1 <= W <= 100; 1 <= H <= 100).
Hiện tại FJ mới cung cấp điện thoại cho 2 con bò đầu đàn. Tuy nhiên
vấn đề là liên lạc giữa hai con bò chỉ thực hiện được nếu đường truyền
thông tin giữa chúng không bị chắn. Ở đây, thông tin chỉ được truyền
theo các đường thẳng và dừng lại nếu nó bị chắn bởi núi đá, cây to
(kí hiệu bằng các kí tự '*').
Do đó, FJ phải mua thêm một số gương (kí hiệu bằng các kí tự '/' và '\')
để đổi hướng đường đi của tia laser.
Xét ví dụ minh họa dưới đây :
Kích thước của đồng có là 8x7, H = 8 và W = 7. Hai con bò đầu đàn
được kí hiệu là 'C', đá và cây to kí hiệu là '*':
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
Cần xác định M - số lượng gương ít nhất FJ cần mua để có thể đảm
bảo liên lạc giữa hai con bò nói trên. Dữ liệu luôn đảm bảo có
ít nhất một cách thực hiện.
INPUT
Dòng 1: Chứa 2 số nguyên W và H cách nhau ít nhất 1 kí tự.
Dòng 2..H+1: Mô tả cánh đồng, mỗi dòng gồm W kí tự 'C' hoặc '*' hoặc '.'
Thông tin không bị chặn khi đi qua các kí tự '.' và chỉ có 2 chữ 'C'.
OUTPUT
Dòng 1: Một số nguyên duy nhất ghi giá trị M - số gương ít nhất cần mua
Ví dụ
Input 7 8 ....... ......C ......* *****.* ....*.. ....*.. .C..*.. ....... Output 3
- Người up: vdmedragon
- Nguồn bài: JAN09 SILVER Division