Untitled

mail@pastecode.io avatar
unknown
plain_text
21 days ago
2.0 kB
1
Indexable
Never
#include<iostream>
using namespace std;

int mover[4]={-1,0,1,0};
int movec[4]={0,1,0,-1};

struct point{
	int x,y;
};

class queue{
	int rear,front;
	point mang[400];
public:
	queue(){
		rear=front=-1;
	}
	void push(int i, int j){
		rear++;
		mang[rear].x=i; mang[rear].y=j;
	}
	point pop(){
		front++;
		return mang[front];
	}
	bool isempty(){
		return (rear==front);
	}
	void reset(){
		rear=front=-1;
	}
};

queue q;
int t,n,g,a,b,index,ans,flag;
point gold[4];
int map[20][20];
int visit[20][20];
int res[20][20];

void resetvisit(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++) visit[i][j]=-1;
	}
}

void resetres(){
	for(int i=0;i<n;i++) 
		for(int j=0;j<n;j++) res[i][j]=100000;
}

void bfs(int x, int y){
	resetvisit();
	q.reset();
	q.push(x,y);
	visit[x][y]=0;
	while(!q.isempty()){
		point u=q.pop();
		for(int h=0;h<4;h++){
			int nx=u.x+mover[h]; int ny=u.y+movec[h];
			if(nx>=0 && nx<n && ny>=0 && ny<n && visit[nx][ny]==-1 && map[nx][ny]!=0){
				visit[nx][ny]=visit[u.x][u.y]+1;
				q.push(nx,ny);
			}
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> n >> g;
		for(int i=0;i<g;i++){
			cin >> a >> b;
			gold[i].x=a-1; gold[i].y=b-1;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) cin >> map[i][j];
		}
		for(int i=0;i<g;i++){
			map[gold[i].x][gold[i].y]=2;
		}
		flag=0; resetres();
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(map[i][j]!=0 && map[i][j]!=2){
					bfs(i,j);
					int max=0;
					for(int i=0;i<g;i++){
						if(visit[gold[i].x][gold[i].y]>max) max=visit[gold[i].x][gold[i].y];
						if(visit[gold[i].x][gold[i].y]==-1) flag=1;
					}
					res[i][j]=max;
				}
				if(flag==1) break;
			}
			if(flag==1) break;
		}
		if(flag==1) cout << "-1" << endl;
		else{
			ans=10000;
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++) {
					if(res[i][j]<ans) ans=res[i][j];
				}
			}
			cout << ans << endl;
		}
	}


	return 0;
}


Leave a Comment