10496 - Collecting Beepers

[Dmytro Chernysh]

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]

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)]

Hello,
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.

[Harun (IIUC)]

Thaks, i must recode it.

[sunhong]

I think the method of backtrack can solve the problem. I use it and get
Accepted!

[bigbit]

What is output for:

1
10 10
1 1
1
1 1

trival case? 0?

[Larry]

That's what I get.

[Zyaad Jaunnoo]

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]

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

[serur]

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.

[shu]

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? =)

[newton]

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]

Nobody here to see my code?
Humm?

[Articuno]

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.