Untitled

 avatar
unknown
plain_text
a year ago
2.4 kB
5
Indexable
#include<iostream>
using namespace std;
const int maxn = 100000;
int t,n,g, mang[21][21], dis[21][21],r,c, ans;
bool vt[21][21];

int rMove[] = {0,0,1,-1};
int cMove[] = {1,-1,0,0};

struct point{
	int x,y;
};
class Queue{
private:
	point arr[maxn];
	int front, rear;
public:
	Queue() {
		front = rear = -1;
	}

	bool isFull() {
		if (rear == maxn - 1) return true;
		return false;
	}

	bool isEmpty() {
		if (rear == front) return true;
		return false;
	}

	void enQueue(point val) {
		if (!isFull()) {
			rear++;
			arr[rear].x = val.x;
			arr[rear].y = val.y;
		}
	}

	point deQueue() {
		point s;
		if (!isEmpty()) {
			front++;
			s.x=arr[front].x;
			s.y=arr[front].y;
		}
		return s;
	}

	void reset() {
		front = rear = -1;
	}
};

Queue myQueue;
point vang[5];

void resets(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			dis[i][j]=-1;
			vt[i][j]=true;
		}
	}
	myQueue.reset();
}

void check(){
	int maxdis =0, flag=0;
	for(int i=1; i<=g; i++){
		if(dis[vang[i].x][vang[i].y] > maxdis)
			maxdis=dis[vang[i].x][vang[i].y];
		else if(dis[vang[i].x][vang[i].y]==-1)
			flag = 1;
	}
	if(maxdis<ans && flag==0)
		ans = maxdis;
}

void bfs(int x, int y){
	dis[x][y]=0;
	point s = {x,y};
	myQueue.enQueue(s);
	vt[x][y]=false;
	while(!myQueue.isEmpty()){
		s = myQueue.deQueue();
		for(int i=0; i<4; i++){
			int a = s.x + rMove[i];
			int b = s.y + cMove[i];
			if(a>=1 && b>=1 && a<=n && b<=n && dis[a][b]==-1 && vt[a][b]==true && mang[a][b]!=0){
				dis[a][b] = dis[s.x][s.y] + 1;
				vt[a][b]=false;
				point p = {a,b};
				myQueue.enQueue(p);
			}
		}
	}
	check();
}

int main(){
	freopen("Text.txt", "r" , stdin);
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> n >> g;
		for(int i=1; i<=g; i++){
			cin >> r >> c;
			vang[i].x=r;
			vang[i].y=c;
		}
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				cin >> mang[i][j];
			}
		}
		ans=10000;
		for(int i=1; i<=g; i++){
			mang[vang[i].x][vang[i].y]=2;
		}

		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				resets();
				if(mang[i][j]==1)
					bfs(i,j);
			}
		}

		if(ans == 10000){
			cout << "Case #" << tc << endl;
			cout << "-1" << endl;
		}else{
			cout << "Case #" << tc << endl;
			cout << ans << endl;
		}
	}
	return 0;
}
Editor is loading...
Leave a Comment