Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
2
Indexable
Never
#include<iostream>
using namespace std;
int n, g, check;
int gold[5][2];
int visgold[5];
int visitgold[5];
int arr[21][21];
int visit[21][21];
int Qx[1000000];
int Qy[1000000];
int front, rear;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int Answer, cntgold;

void push(int x, int y) {
	rear++;
	Qx[rear]=x;
	Qy[rear]=y;
}

void pop(int &x, int &y) {
	front++;
	x=Qx[front];
	y=Qy[front];
}
void bfs(int x, int y) {
	front = rear = -1;
	push(x,y);
	visit[x][y] = 0;
	while (front < rear) {
		pop(x,y);
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= n && yy >= 1 && yy <= n) {
				if (visit[xx][yy] == 0 && arr[xx][yy] != 0) {
					visit[xx][yy] = visit[x][y] + 1;
					push(xx,yy);
				}
			}
		}	
	}
	int cnt = 0;
	int min = 0;
	for (int i = 1; i <= g; i++) {
		visitgold[i]=0;
	}
	for (int i = 1; i <= g; i++) {
		if (visit[gold[i][0]][gold[i][1]] > 0) {
			cnt++;
			visitgold[i]=1;
			if (min < visit[gold[i][0]][gold[i][1]]) {
				min = visit[gold[i][0]][gold[i][1]];
			}
		}
	}
	
	if (cnt>0) {
		check = 1;
		if (cnt>cntgold) {
			cntgold=cnt;
			Answer=min;
			for (int i = 1; i <= g; i++) {
				visgold[i] = visitgold[i];
			}
		} else if (cnt==cntgold) {
			if (min < Answer) {
				Answer = min;
				for (int i = 1; i <= g; i++) {
					visgold[i] = visitgold[i];
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visit[i][j] = 0;
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	freopen("input.txt", "r", stdin);
	cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
		check = 0;
		cntgold=0;
		Answer = 100000;
		cin >> n >> g;
		for (int i = 1; i <= g; i++) {
			cin >> gold[i][0] >> gold[i][1];
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> arr[i][j];
			}
		}
		for (int i = 1; i <= g; i++) {
			arr[gold[i][0]][gold[i][1]] = 2;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (arr[i][j] == 1 && visit[i][j] == 0) {
					bfs(i, j);
				}
			}
		}
		cout << "Case #" << test_case << endl;
		if (check == 0) cout << "-1" << endl;
		else {
			cout << Answer << endl;
			if (cntgold != g) {
				for (int i = 1; i <= g; i++) {
					if (visgold[i] == 0) {
						cout << gold[i][0] << ' ' << gold[i][1] << endl;
					}
				}
			}
		}
	}
	return 0;//Your program should return 0 on normal termination.
}