Gomti the Cow
All submissions for this problem are available.
Gomti is a hungry and lazy cow. Her master is fed up with her because she does nothing useful. So now he has thought of a new job for her, eating grass. She has a field in front of her with some weeds in it. Her job is to eat those weeds. But being lazy, she wants to do it as optimally as possible.
For simplicity lets assume that the field in front of her is divided in M X N squares such that she can stand exactly in one square at a time. She wants to eat all the weed with minimum number of moves between time. But like in everysitutaion of life, there are obstacles in her path.
The first line of input consists of number of test cases T.
For each test case the first line consists two values "b" followed by "l", the breadth and length of the field. "l" each containing "b" values with each value indicating the possible type of sqaures (see below for more information).
b l s11 s12 s13 ... s1b s21 s22 s23 ... s2b ... sl1 sl2 sl3 ... slb
The integers l and b are the length and breadth of the field in terms of number of sqaures. s(a,b) or sab represnts what type of sqaures it is. To state it more clearly, there are four kinds of squares,
"0" - represents an empty space that has neither a weed nor a obstacle, she can move through such a sqaure with no trouble at all
"+" - means that the square has a weed and she has to eat it and turn it into a "0"
"." - means that the square has a stone in it - its an obstacle and she cant walk through it
"c" - means that the cow starts on this position
For each "l" x "b" grid , your program should output a line containing the minimum number of moves taken by Gomti to eat all the weeds. In case there are weeds that cannot be reached, output "not possible".
No of test cases T <= 1000
Length l and breadth b <= 25
2 5 5 ....c ....+ ....+ ....+ ....0 5 5 ....c ...+. ....+ ....+ ....0
3 not possible
|Time Limit:||0.226667 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, GO, NODEJS, BF, JS|
Fetching successful submissions
If you are still having problems, see a sample solution here.