MLASERP - Laser Phones

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.

Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-02-13
Thời gian chạy:0.227s
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
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.
2010-11-16 11:14:55 dpcm
rất giống bài Quân tượng :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.