11487 - Gathering food

[andmej]

During the contest, I solved this problem using BFS with state [i, j, food] where i = row, j = column and food = letter I'm trying to grab.
To count the number of shortests paths, I filled a table paths[len][i][j][food] = number of different paths of length "len" ending at state [i, j, food].

However, my solution is rather slow. I've seen some people ranked with times < 0.010. What's the fastest method to solve this problem?

[Monsoon]

do bfs starting from 'A', then from 'B', ....
you can easily put counting number of shortest paths in bfs function

[marcadian]

I'm try counting the way in the BFS, but it gets WA, can anyone give me test case ?Thx

[FAQ]

Try these

Code: Select all

3
A..
...
..B
10
A.........
..........
..........
..........
..........
..........
..........
..........
..........
.........B
1
A
3
ABC
DEF
...
6
ABCDEF
GHIJKL
MNOPQR
STUVWX
YZ####
......
3
..A
.B.
C..
3
ABC
...
###
3
...
.A.
...
2
AC
DB
2
AC
BD
5
A....
####.
..B..
.####
C.DE.
2
A.
.B
2
A#
#B
0



Code: Select all

Case 1: 4 6
Case 2: 18 7746
Case 3: 0 1
Case 4: 7 1
Case 5: 45 1
Case 6: 4 4
Case 7: 2 1
Case 8: 0 1
Case 9: Impossible
Case 10: 4 1
Case 11: 15 1
Case 12: 2 2
Case 13: Impossible



[marcadian]

Thx I got AC, my BFS doesn't consider if food is already taken than you can pass that point

Code: Select all

3
ABC
DEF
...


[Articuno]

Hi, i am new in programming. I have learned BFS and implemented it in this problem. My program is giving correct output for the test cases those are given here. but it is WA. I think there is a problem in counting the number of shortest paths and i am confused about my technique. Can anyone please check my code and tell me what is wrong. Please help me.......

Here is my code:

Code: Select all

Removed

[sohel]

a part of your code

Code: Select all

for(i=0;i<tp;i++)
            {
               ans1=ans1+totaldist[i];
            }
            ans2=1;
            for(i=0;i<tp;i++)
            {
               ans2=ans2*totalpath[i];
            }
            ans2=ans2%20437;

in the last line, ans2 can be very big and won't fit into integer data type and thus will lead to faulty outputs.
Try to do MOD after every operation.

[Articuno]

I have changed that part of my code into this:

Code: Select all

else
         {
            ans1=0;
            for(i=0;i<tp;i++)
            {
               ans1=ans1+totaldist[i];
            }
            ans2=1;
            for(i=0;i<tp;i++)
            {
               ans2=(((ans2)%20437)*(totalpath[i]%20437))%20437;
            }
            ans2=ans2%20437;
            printf("Case %lld: %lld %lld\n",cas,ans1,ans2);
         }

But still it is WA. I had also changed the data type and used long long. But still..... WA.
Can you give me some critical test cases?

[sohel]

try these cases:
Input

Code: Select all

10
D........B
..........
..........
..........
..........
..........
..........
..........
..........
A........C
10
D#..##...B
..........
###..####.
..........
....E.....
###....##.
..........
...###....
..........
A........C
10
..........
..........
..........
..........
ACB.......
..........
..........
..........
..........
..........
0


Output

Code: Select all

Case 1: 45 2429
Case 2: 53 12876
Case 3: 5 2


[Articuno]

Thanks Sohel vai for your help. I think i have found my error. I can not figure out the way how to find the total number of distinct paths. Can you help me a little more. Please give me some hints about how to count the number of distinct paths. My program can count the shortest distance correctly but there is problem in counting the number of paths. Kindly give me some hints about the process as i am unable to figure it out. I have tried different approaches but all in vain. Thanks for ur help.

[sohel]

The total number of paths can be found by basic dynamic programming.
Suppose we have 4 letters {A B C D}.

Total Number of paths = TNP (for the sake of brevity)
Result = TNP(from A to B) * TNP(from B to C) * TNP(from C to D).

So basically, what we need is to find the total number of paths from a point to that of another.
Suppose are going from A to B and let the shortest path be equal to 10.
Lets make a move from A. If the shortest path from the new position to B is equal to 9, then that point must be a part of the path. You can use dp to memoize repeated states.

I suggest you solve some easy dynamic programming problems first, then you will be able to get a good grasp of this problem.

[Articuno]

Thanks a lot Sohel vai. Thanks a lot for your suggestion. Got AC