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.

hide comments
gopikrishna_p: 2017-06-18 11:05:55

nice problem .beginners should try this problem :).learned a lot :) BFS AC 0.00

vladimira: 2017-03-02 16:27:48

RE in first go! But ac in second =)
nice problem, good bfs.
I didnt use Djikstra and I think it should give tle here bcs n^2 would be 10^8 and its quite a lot.
and I suggest testcases:
C....
*...*
C *.*.
.....
and
C...
.**.
..*.
*.*.
..*.
C**.
....

gboduljak: 2017-02-23 12:00:07

solved after three days :), nice problem

devbishnoi: 2017-01-24 18:59:37

There are always be two cows.
Nice problem. AC in 1 go.
There always be one test case in each test file.

ninhnguyenqo: 2016-12-03 04:05:39

so, if i want to count mirror types('/' & '\') as 2/ and 1\ in sample input, how should we solve?

vincealek: 2016-11-25 11:44:09

took my 5 hours. worth to try
try this test case
10 10
.........C
..........
..........
..........
**.*......
...*......
.*........
.*........
.*........
C*........
5 4
C.***
..*C.
...*.
*....
4 4
C***
.*C.
....
....
10 10
**.C*....C
*..****..*
*.****..**
*..**..***
**..**....
...******.
.**....*..
.*..***..*
..***...**
.......***

Last edit: 2016-11-25 11:47:35
tni_mdixit: 2016-11-03 15:07:41

are there gonna be two cows only, always ?

mr_bee: 2016-07-23 18:01:44

Can anybody let me know when the input will finish?
I already passed sample TC but still got WA

khaledawaled: 2016-07-12 07:44:45

good problem , try to enjoy it

iharsh234: 2016-07-07 14:30:36

a must practise bfs for begineers


Added by:~!(*(@*!@^&
Date:2009-02-13
Time limit:0.227s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:JAN09 SILVER Division