Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MLASERP - Laser Phones

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274506/problem/P
{assign var="code" value="MLASERP"} {if $par==""} {assign var=par value=$locale} {/if}
{if $par=="vn"} {literal}

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 '*' , và '.'. 
Thông tin không bị chặn khi đi qua các kí tự '.' và chỉ có 2 chữ 'C'.

Ví dụ :

7 8
.......
......C
......*
*****.*
....*..
....*..
.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ụ :

3
{/literal}{elseif ($par=="en" || $par=="")}{literal}
The cows have a new laser-based system so they can have casual
conversations while out in the pasture which is modeled as a W x H
grid of points (1 <= W <= 100; 1 <= H <= 100).

The system requires a sort of line-of-sight connectivity in order
to sustain communication. The pasture, of course, has rocks and
trees that disrupt the communication but the cows have purchased
diagonal mirrors ('/' and '\' below) that deflect the laser beam
through a 90 degree turn. Below is a map that illustrates the
problem.

H is 8 and W is 7 for this map.  The two communicating cows are
notated as 'C's; rocks and other blocking elements are notated as
'*'s:

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

Determine the minimum number of mirrors M that must be installed
to maintain laser communication between the two cows, a feat which
is always possible in the given test data.

INPUT

* Line 1: Two space separated integers: W and H

* Lines 2..H+1: The entire pasture.

SAMPLE INPUT  

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......
OUTPUT
* Line 1: A single integer: M

SAMPLE OUTPUT 

3
Any suggestted testcase will be welcomed. {/literal} {/if}

Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-02-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:JAN09 SILVER Division

hide comments
2020-02-28 17:23:19
holy shit làm hoài vẫn sai
2016-01-11 19:40:26 Sơn Tùng M-TP
Hứ! :D
2015-08-12 10:26:40 Trần Dũng
test yếu quá. đề nghị tăng lên 1000x1000 =))
2014-06-26 20:36:42 Thcs Ðặng Chánh Kỷ
cứ code như qbbishop, chỉ có thêm tý xíu là ac
2014-06-26 16:43:00 Lollipop
UKM :3
2014-06-26 16:05:57 Kraken
bài này làm kiểu quân tượng sau đó lấy số đường rẽ -1 à?
2013-09-13 12:52:40 Doraemon Grapes
giống hệt quân tượng :)))
2012-09-11 14:40:05 Erik
Có cách làm Dijsktra :) nhưng rất bựa :D các bác đừng nghĩ theo hướng này :D
2012-08-07 18:50:12 KHD
tư tưởng hệt bài quân tượng :D
2012-08-04 15:27:37 Nguyễn Tính
ai giúp mình về thuật toán bài này.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.