Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.0 kB
3
Indexable
Never
#include<iostream>
using namespace std;

int T, n, g;
int gold[105][2], arr[105][105], visit[105][105];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int r;
int kt1 = 0, kt2 = 0;

int rear, front;
struct toado{
	int x, y;
};
toado queue[1000000];
void init(){
	rear = 0;
	front = 0;
}
void push(int x, int y){
	queue[rear].x = x;
	queue[rear].y = y;
	rear++;
}
toado pop(){
	toado t = queue[front];
	front++;
	return t;
}

void nhap(){
	cin >> n >> g;
	for(int i = 0; i < g; i ++) {
		cin >> gold[i][0] >> gold[i][1];
		gold[i][0] --;
		gold[i][1] --;
	}

	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) {
			arr[i][j] = 0;
		}
	}
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) {
			cin >> arr[i][j];
		}
	}
}

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

bool cdk(int x, int y) {
	if(x >= 0 && x < n && y >= 0 && y < n) return true;
	return false;
}

void BFS(int x, int y) {
	init();
	push(x,y);
	visit[x][y] = 0;
	while(front < rear) {
		toado t = pop();
		for(int i = 0; i < 4; i ++) {
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			if(cdk(xx,yy) && arr[xx][yy]) {
				if(visit[xx][yy]==100000) {
					push(xx,yy);
					visit[xx][yy] = visit[t.x][t.y] + 1;
				}
				else if(visit[xx][yy] > visit[t.x][t.y] + 1) visit[xx][yy] = visit[t.x][t.y] + 1;
			}
		}
	}
}

bool check(int x, int y) {
	for(int i = 0; i < g; i ++) {
		if(x == gold[i][0] && y == gold[i][1]) return false;
	}
	return true;
}

void in() {
	kt1 = 0; kt2 = 0;
	int sav = 0;
	for(int i = 0; i < g; i ++) {
		int x = gold[i][0];
		int y = gold[i][1];
		if(visit[x][y] == 100000) {
			kt1 ++;
		}
		else {
			kt2++;
			if(visit[x][y] > sav) sav = visit[x][y];
		}
	}
	if(kt2 == g) {
		if(r > sav) r = sav;
	}
}
int main() {
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++) {
		nhap();
		r = 100000;
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < n; j ++) {
				if(check(i,j) && arr[i][j]) {
					reset();
					BFS(i,j);
					in();
					/*cout << r << endl;
					for(int i = 0; i < n; i ++) {
						for(int j = 0; j < n; j ++) {
							cout << visit[i][j] << "\t";
						}
						cout << endl;
					}
					cout << endl << endl;*/
				}
			}
		}
		cout << "Case #" << tc << endl;
		if(r == 100000) cout << -1 << endl;
		else cout << r << endl;
	}
	return 0;
}

3
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 4
3 4
4 3
4 5
6 10
1 0 0 1 1 0 0 0 1 0 
1 1 1 1 0 1 1 0 1 0 
1 0 0 1 0 1 1 1 0 1 
1 0 1 0 1 1 1 1 1 0 
0 1 0 0 1 1 1 1 0 0 
1 1 0 0 1 1 1 0 1 1 
1 0 0 1 0 1 0 1 1 0 
1 0 1 1 0 0 1 1 0 0 
1 1 1 1 1 1 1 1 0 1 
1 1 1 1 1 0 0 1 1 1 


Case #1
1
Case #2
2
Case #11
1
4 3
4 5
6 10