## 10496 - Collecting Beepers

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Dmytro Chernysh
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 NP-complete. Therefore, there is not better way to solve it, exept for backtraching...

Can somebody post some inputs and outputs?

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
I just solved it !!!
But for the future be aware of a tricky input like
1
10 10
1 1
1
1 1

the answer is 0, sure

Harun (IIUC)
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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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.
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.

Harun (IIUC)
New poster
Posts: 6
Joined: Thu Apr 17, 2003 1:06 pm
Thaks, i must recode it.

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China
I think the method of backtrack can solve the problem. I use it and get
Accepted!

bigbit
New poster
Posts: 4
Joined: Fri Jun 27, 2003 3:39 pm

### 10496

What is output for:

1
10 10
1 1
1
1 1

trival case? 0?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
That's what I get.

Zyaad Jaunnoo
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!

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### 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.

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);
}
}
}
}
``````
Plz, some1 hlp. (I/O,Suggetions, anything.....)

-Shihab
Shihab
CSE,BUET

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
If I'm not mistaken Karel is confronting NP-complete 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.
Last edited by serur on Sat Apr 14, 2012 3:32 pm, edited 1 time in total.

shu
New poster
Posts: 6
Joined: Sat Jul 16, 2005 1:43 pm
Contact:

### 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:

Code: Select all

``````1
20 20
1 10
3
1 11
1 8
1 15
``````
It should return 14, but my code return 16!!

rejudge? =)
best regards,
shu

newton
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.

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;
}``````
Thanks in advanced.

newton
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?

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, 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.
May be tomorrow is a better day............