10496  Collecting Beepers
Moderator: Board moderators

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
10496  Collecting Beepers
This problem is variation of "Traveling Salesman Problem", so it's NPcomplete. Therefore, there is not better way to solve it, exept for backtraching...
Can somebody post some inputs and outputs?
Can somebody post some inputs and outputs?

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am

 New poster
 Posts: 6
 Joined: Thu Apr 17, 2003 1:06 pm
10496
Hello,
i got TLE for this program.
i use BFS to find the shortest path.
is my algorithm is wrong?
pls help me.
i got TLE for this program.
i use BFS to find the shortest path.
is my algorithm is wrong?
pls help me.
Not BFS.
As there is at most 10 objects to collect, you just permutate the order of collections, then take the one that use shortest length.
As there is at most 10 objects to collect, you just permutate the order of collections, then take the one that use shortest length.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 am
Prune early as we are doing the search.
Keep a variable <min> which keeps the shortest round trip found so far
If travels more that <min>, its uuseles to continue the search.
If a new shortest distance has been found for the round trip, set <min> to the new shortes distance.
Hope that may help...
Cheers!
Keep a variable <min> which keeps the shortest round trip found so far
If travels more that <min>, its uuseles to continue the search.
If a new shortest distance has been found for the round trip, set <min> to the new shortes distance.
Hope that may help...
Cheers!
10496. WA!!!!
I've used BFS to solve this prob. What i've done is:
1. Find the location nearest to the starting location.(USING BFS and the starting location as source)
2. Use this location as source and find the location nearest to this. (I've used the flag array to ensure that a location is not used as source more than once.) And do this untill all the locations except one is used as source.
3. From the locaton not used as source find the shortest path to the starting location.
And the total shortest path is the sum of the intermidiate shortest paths.
But I'm getting WA with this.
Plz, some1 hlp. (I/O,Suggetions, anything.....)
Shihab
1. Find the location nearest to the starting location.(USING BFS and the starting location as source)
2. Use this location as source and find the location nearest to this. (I've used the flag array to ensure that a location is not used as source more than once.) And do this untill all the locations except one is used as source.
3. From the locaton not used as source find the shortest path to the starting location.
And the total shortest path is the sum of the intermidiate shortest paths.
But I'm getting WA with this.
Code: Select all
/*@JUDGE_ID; 55485HX 10496 C++*/
#include<stdio.h>
#include<queue>
using namespace std;
#define INF 9999999
typedef struct Cell{
int r,c;
bool operator !=(Cell C){
return r!=C.r && c!=C.c;
}
} Cell;
int change[2][4];
bool visited[25][25];
int d[25][25];
int row,col;
queue<Cell> Q;
void init(){
change[0][0]=0;change[1][0]=1;
change[0][1]=0;change[1][1]=1;
change[0][2]=1;change[1][2]=0;
change[0][3]=1;change[1][3]=0;
}
void init_source(Cell);
void BFS(Cell);
void main(){
int i,j,k,n,caseno,length,min;
Cell beeper[15],so,start;
bool flag[15];
init();
scanf("%d",&caseno);
for(;caseno;caseno){
scanf("%d %d",&row,&col);
scanf("%d %d",&start.r,&start.c);
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d %d",&beeper[i].r,&beeper[i].c);flag[i]=false;
}
length=0;
k=0;
so=start;
for(i=1;i<n;i++){
BFS(so);
min=INF;
for(j=1;j<=n;j++){
if(beeper[j]!=so && !flag[j] && min>d[beeper[j].r][beeper[j].c]){
min=d[beeper[j].r][beeper[j].c];
k=j;
}
}
length+=d[beeper[k].r][beeper[k].c];
so=beeper[k];
flag[k]=true;
}
BFS(so);
length+=d[start.r][start.c];
printf("The shortest path has length %d\n",length);
}
}
void init_source(Cell s){
int i,j;
for(i=1;i<=row;i++){
for(j=1;j<=col;j++){
visited[i][j]=false;
d[i][j]=INF;
}
}
d[s.r][s.c]=0;
visited[s.r][s.c]=true;
}
void BFS(Cell s){
int i;
Cell t1,t2;
while(!Q.empty()) Q.pop();
init_source(s);
Q.push(s);
while(!Q.empty()){
t1=Q.front();
Q.pop();
for(i=0;i<4;i++){
t2.r=t1.r+change[0][i];
t2.c=t1.c+change[1][i];
if(t2.r>0 && t2.r<=row && t2.c>0 && t2.c<=col && !visited[t2.r][t2.c]){
visited[t2.r][t2.c]=true;
d[t2.r][t2.c]=d[t1.r][t1.c]+1;
Q.push(t2);
}
}
}
}
Shihab
Shihab
CSE,BUET
CSE,BUET
If I'm not mistaken Karel is confronting NPcomplete problem,
so you can use BFS only after you picked up all the beepers(or whatever he collects  or acorns?) to return to initial position.
I think my algo which gives AC is not correct  while doing backtrack to find a shortest path to collect all the beepers I also remember locations of last beepers and then do BFS to return from that position to the initial. But I think this problem has nothing to do with BFS at all. And there is uneasiness on that score.
so you can use BFS only after you picked up all the beepers(or whatever he collects  or acorns?) to return to initial position.
I think my algo which gives AC is not correct  while doing backtrack to find a shortest path to collect all the beepers I also remember locations of last beepers and then do BFS to return from that position to the initial. But I think this problem has nothing to do with BFS at all. And there is uneasiness on that score.
Last edited by serur on Sat Apr 14, 2012 3:32 pm, edited 1 time in total.
10496 Should Be Rejudged...
Strange!! I try to use greedy & bfs to solve this problem, but WHY i got AC??
My code failed for this input:
It should return 14, but my code return 16!!
rejudge? =)
My code failed for this input:
Code: Select all
1
20 20
1 10
3
1 11
1 8
1 15
rejudge? =)
best regards,
shu
shu

 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10496  Collecting Beepers
i think there is no need to use BFS.
as the limit is at most 20x20.
My algorithm:
1. Take all the points to a structure.
2. store source
3. get next close point from source
for this i count the ( abs(sx  node.x) + abs(sy  node.y) ) upto all beepers point and return the expected pont.
4. next i used the same process considering the close point as source.
5. i used a flag array to keep track that the point is taken or not.
But unfortunately i got WA.
Now please check my code.
Thanks in advanced.
as the limit is at most 20x20.
My algorithm:
1. Take all the points to a structure.
2. store source
3. get next close point from source
for this i count the ( abs(sx  node.x) + abs(sy  node.y) ) upto all beepers point and return the expected pont.
4. next i used the same process considering the close point as source.
5. i used a flag array to keep track that the point is taken or not.
But unfortunately i got WA.
Now please check my code.
Code: Select all
#include <cstdio>
#include <algorithm>
#define MAX 20
#define INF 1<<29
using namespace std;
typedef struct{
int x,y;
}Node;
bool notTaken[MAX];
Node node[MAX];
int pos,nBeep;
int abs(int n){
if(n < 0)
return n;
return n;
}
int sx,sy;
int getNext(int x,int y){
int min = INF,dist,i;
for(i = 0; i<nBeep; i++){
dist = abs(x  node[i].x) + abs(y  node[i].y);
if(min > dist && notTaken[i]){
min = dist;
pos = i;
}
}
notTaken[pos] = false;
return min;
}
bool hasNext(){
int i;
for(i = 0; i<nBeep; i++){
if(notTaken[i])
return true;
}
return false;
}
int main(){
int a,b,dist,m,n,test,x,y,i;
//freopen("in.txt","rt",stdin);
scanf("%d",&test);
while(test){
scanf("%d%d",&m,&n);
scanf("%d%d",&sx,&sy);
scanf("%d",&nBeep);
for(i = 0; i<nBeep; i++){
scanf("%d%d",&a,&b);
node[i].x = a;
node[i].y = b;
}
fill(notTaken,notTaken + nBeep, true);
int cnt = 0;
x = sx;
y = sy;
for(i = 0; hasNext(); i++){
dist = getNext(x,y);
cnt += dist;
x = node[pos].x;
y = node[pos].y;
}
dist = abs(sx  x) + abs(sy  y);
cnt += dist;
printf("The shortest path has length %d\n",cnt);
}
return 0;
}
http://www.newton.0fees.net is enough!

 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10496  Collecting Beepers
Nobody here to see my code?
Humm?
Humm?
http://www.newton.0fees.net is enough!

 Learning poster
 Posts: 78
 Joined: Sun Nov 30, 2008 5:00 pm
 Location: IUTOIC, Dhaka, Bangladesh
Re: 10496  Collecting Beepers
Please someone tell me whether this problem can be solved using BFS and greedy. I was trying to do so instead of backtracking. But WA. Can someone give me some critical test cases ? Please someone help me.
Thanks in advance.
Thanks in advance.
May be tomorrow is a better day............