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
ajay_5097: 2018-08-31 06:36:10

phewww.....

kiran321: 2018-08-12 00:08:22

For those who have implemented bfs correctly and still getting wrong answer on 9th test case, JUST INCREASE THE QUEUE SIZE TO 30000.I have wasted a lot of time bcoz of that silly mistake...

Arpit Varshneya: 2018-07-31 14:08:08

Getting WA for 9th tc. Any idea how to solve this?

ankitraj7217: 2018-06-14 16:57:36

vshl869
Remove visited matrix if u have made one...I was also getting wrong answer on 9th test case bcz of that...

Last edit: 2018-06-14 16:58:11
vshl869: 2018-04-01 04:47:17

i have tested so many test cases, but i gets WA on 9th test case while submitting, is there anyone else having same issue

chetan4060: 2018-03-14 18:44:33

easy one ac in one go:)

sherlock11: 2017-12-26 05:44:20

nice and elegant problem!!
u just need to think when u will add a mirror and u will get an AC

vengatesh15: 2017-09-07 09:42:03

easy bfs silly mistake cost me 1 WA.

darshit05: 2017-09-06 17:53:33

http://www.spoj.com/submit/MLASERP/id=20107599
I am getting WA after 8th test case.

Last edit: 2017-09-06 17:57:28
kshubham02: 2017-08-31 11:00:00

4xDijkstra :P
Remember, width is given first in input. Costed me a WA.


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