daovang1

avatar
quoc14
c_cpp
a year ago
6.3 kB
13
Indexable
caidat
#include <iostream>

using namespace std;


int n, g;
int a[50][50];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};


int maxx(int a, int b) {
	if (a > b) return a;
	return b;
}

struct point {
	int r;
	int c;
};




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

point movang[100];
point queue[1000000];
int last, start;
int visit[100][100];
int cur;
int ans, re;
int oo = 99999999;

int check[100];
int check1[100];
int ok;
int visitgold[6];

int findMax() {
	int res = visit[movang[1].r][movang[1].c] - 1;
	for (int k = 2; k <= g; k++) {
		res = maxx(res, visit[movang[k].r][movang[k].c] - 1);
	}

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

void bfs(int x, int y) {
	
	resetvisit();
	last = 0;
	start = 0;
	point tmp;
	tmp.r = x;
	tmp.c = y;
	queue[last++] = tmp;
	visit[x][y] = 1;
	int cnt = 0;
	while (start != last) {
		if (cnt == g) {
			break;
		}
		point cur = queue[start++];
		int x_cur = cur.r;
		int y_cur = cur.c;

		for (int k = 0; k < g; k++) {
			if (movang[k].r == x_cur && movang[k].c == y_cur) {
				cnt++;
				check1[k] = 1;
			}
		}

		for (int i = 0; i < 4; i++) {
			int x_next = x_cur + dx[i];
			int y_next = y_cur + dy[i];
			if (inside(x_next, y_next) && a[x_next][y_next] != 0) {
				if (visit[x_next][y_next] == 0) {
					visit[x_next][y_next] = visit[x_cur][y_cur] + 1;
					point tmp1;
					tmp1.r = x_next;
					tmp1.c = y_next;
					queue[last++] = tmp1;
					
				}
			
			}
			
		}
		
	}

	if (cnt > ans) {
		ans = cnt;
		for (int k = 1; k <= g; k++) {
			visitgold[k] = check1[k];
		}
		re = findMax();
	}
	
	else if (cnt == ans) {
		int dis = findMax();
		if (re > dis) {
			re = dis;
			for (int k = 1; k <= g; k++) {
				visitgold[k] = check1[k];
			}
		}
	}
		
}

void solve(int testcase) {
	ans = re = 0;
	cin >> n >> g;

	for (int i = 1; i <= g; i++) {
		cin >> movang[i].r >> movang[i].c;

	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	cur = 1;
	for (int k = 1; k <= g; k++) {
		cur++;
		a[movang[k].r][movang[k].c] = cur;
		
	}

	int ok = 1;

	for (int k = 1; k <= g; k++) {
		if (ok == 0) {
			break;
		}
		for (int i = 0; i < 4; i++) {
			int new_r = movang[k].r + dx[i];
			int new_c = movang[k].c + dy[i];
			if (inside(new_r, new_c) && a[new_r][new_c] == 1) {
				ok = 0;
			}
		}
	}

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

	cout << "Case #" << testcase << endl;
	if (ok == 1) {
		cout << -1 << endl;
	}
	else {
		cout << re << endl;
		for (int k = 1; k <= g; k++) {
			if (visitgold[k] == 0) {
				cout << movang[k].r << " " << movang[k].c << endl;
			}
		}
	}
	
	

	

}

int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}

#include <iostream>

using namespace std;


int n, g;
int a[50][50];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};


int maxx(int a, int b) {
	if (a > b) return a;
	return b;
}

struct point {
	int r;
	int c;
};




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

point movang[100];
point queue[1000000];
int last, start;
int visit[100][100];
int cur;
int ans, re;
int oo = 99999999;

int check[100];
int check1[100];
int ok;
int visitgold[6];

int findMax() {
	int res = visit[movang[1].r][movang[1].c] - 1;
	for (int k = 2; k <= g; k++) {
		res = maxx(res, visit[movang[k].r][movang[k].c] - 1);
	}

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

void bfs(int x, int y) {
	
	resetvisit();
	last = 0;
	start = 0;
	point tmp;
	tmp.r = x;
	tmp.c = y;
	queue[last++] = tmp;
	visit[x][y] = 1;
	int cnt = 0;
	while (start != last) {
		if (cnt == g) {
			break;
		}
		point cur = queue[start++];
		int x_cur = cur.r;
		int y_cur = cur.c;

		for (int k = 0; k < g; k++) {
			if (movang[k].r == x_cur && movang[k].c == y_cur) {
				cnt++;
				check1[k] = 1;
			}
		}

		for (int i = 0; i < 4; i++) {
			int x_next = x_cur + dx[i];
			int y_next = y_cur + dy[i];
			if (inside(x_next, y_next) && a[x_next][y_next] != 0) {
				if (visit[x_next][y_next] == 0) {
					visit[x_next][y_next] = visit[x_cur][y_cur] + 1;
					point tmp1;
					tmp1.r = x_next;
					tmp1.c = y_next;
					queue[last++] = tmp1;
					
				}
			
			}
			
		}
		
	}

	if (cnt > ans) {
		ans = cnt;
		for (int k = 1; k <= g; k++) {
			visitgold[k] = check1[k];
		}
		re = findMax();
	}
	
	else if (cnt == ans) {
		int dis = findMax();
		if (re > dis) {
			re = dis;
			for (int k = 1; k <= g; k++) {
				visitgold[k] = check1[k];
			}
		}
	}
		
}

void solve(int testcase) {
	ans = re = 0;
	cin >> n >> g;

	for (int i = 1; i <= g; i++) {
		cin >> movang[i].r >> movang[i].c;

	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	cur = 1;
	for (int k = 1; k <= g; k++) {
		cur++;
		a[movang[k].r][movang[k].c] = cur;
		
	}

	int ok = 1;

	for (int k = 1; k <= g; k++) {
		if (ok == 0) {
			break;
		}
		for (int i = 0; i < 4; i++) {
			int new_r = movang[k].r + dx[i];
			int new_c = movang[k].c + dy[i];
			if (inside(new_r, new_c) && a[new_r][new_c] == 1) {
				ok = 0;
			}
		}
	}

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

	cout << "Case #" << testcase << endl;
	if (ok == 1) {
		cout << -1 << endl;
	}
	else {
		cout << re << endl;
		for (int k = 1; k <= g; k++) {
			if (visitgold[k] == 0) {
				cout << movang[k].r << " " << movang[k].c << endl;
			}
		}
	}
	
	

	

}

int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}
Editor is loading...
Leave a Comment