## 11487 - Gathering Food

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### 11487 - Gathering Food

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][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?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

### Re: 11487 - Gathering food

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

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

### Re: 11487 - Gathering food

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

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

### Re: 11487 - Gathering food

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

``````

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

### Re: 11487 - Gathering food

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
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 11487 - Gathering food

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``
Last edited by Articuno on Thu Dec 04, 2008 6:20 pm, edited 1 time in total.
May be tomorrow is a better day............

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11487 - Gathering food

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
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 11487 - Gathering food

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?
May be tomorrow is a better day............

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11487 - Gathering food

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
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 11487 - Gathering food

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.
May be tomorrow is a better day............

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11487 - Gathering food

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
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm