[ create a new paste ] login | about

Link: http://codepad.org/c57LWTtz    [ raw code | output | fork ]

hoaithu.melody - C++, pasted on Jul 5:
// quan ma

#include <iostream>
using namespace std;

int T, M, N, mang[105][105], check[105][105]; 
int	toadox[105], toadoy[105], d[105][105], visit[105];

int queue[1000000];
int r, l,c, minx;

void push(int n){
	queue[++r]=n;
}

int pop(){
	return queue[++l];
}

int dx[8]={-1,-1,1,1,-2,-2,2,2};
int dy[8]={-2,2,-2,2,-1,1,-1,1};

int BFS(int x, int y){
	int x1=toadox[x];
	int y1=toadoy[x];
	int x2=toadox[y];
	int y2=toadoy[y];
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			check[i][j]=0;
		}
	}
	r=-1;
	l=-1;
	push(x1*1000+y1);
	check[x1][y1]=1;
	while(r!=l){
		int tmp = pop();
		int yyy=tmp%1000;
		int xxx=tmp/1000;
		for (int k=0; k<8; k++){
			int yy = dy[k]+yyy;
			int xx = dx[k]+xxx;
			if(xx>0 &&yy>0 && xx<N+1 && yy<M+1){
				if(check[xx][yy]==0 ){
					if(xx==x2 && yy==y2){
						return check[xxx][yyy];
					}
					check[xx][yy]=check[xxx][yyy]+1;
					push(xx*1000+yy);
				}
			
			}	
		}
	}
}

void backtrack(int x, int t, int s){
	if(t==c){
		if(s<minx) minx=s;
		return;
	}
	else{
		for(int i=0; i<c; i++){
			if(visit[i]==0){
				visit[i]=1;
				if(s<minx){
					backtrack(i, t+1, s+d[x][i]);
				}
				visit[i]=0;
			}
		}
	}
}

int main(){
	//freopen("input.txt", "r", stdin);
	cin>>T;
	for(int t=1; t<=T; t++){
		c=1;
		minx=99999999;
		cin>>N>>M;
		for(int i=1; i<=N; i++){
			for(int j=1; j<=M; j++){
				cin>>mang[i][j];
				if(mang[i][j]==1) {
					toadox[c]=i;
					toadoy[c]=j;
					visit[c]=0;
					c++;
				}
				if(mang[i][j]==3) {
					toadox[0]=i;
					toadoy[0]=j;
				}
			}
		}
		
		for(int i=0; i<c-1; i++){
			for(int j=i+1; j<c; j++){
				d[j][i]=d[i][j]=BFS(i,j);
			}

		}
		/*for(int i=0; i<c; i++){
			for(int j=0; j<c; j++){
				cout<< d[i][j]<<" ";
			}
			cout<<endl;
		}*/
		visit[0]=1;
		backtrack(0,1,0);
		cout<<"Case #"<<t<<endl<< minx<<endl;
	}
	return 0;
}


Output:
1
2
3
In function 'void push(int)':
Line 13: error: reference to 'queue' is ambiguous
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: