MLASERP - Laser Phones



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

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