hugo_daovang1_c2
duyvan
plain_text
10 months ago
2.7 kB
11
Indexable
Never
#include <iostream> using namespace std; int N, G; int gold[5][3]; int map[21][21], visited[21][21]; int ans, x_min, y_min, maxCnt; int front, rear; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; void reset(){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ visited[i][j] = 0; } } for(int j = 0; j < G; j++){ gold[j][2] = 0; } } bool check(){ for(int i = 0; i < G; i++){ if(gold[i][2] == 1) return true; } return false; } struct Node{ int r, c; }; Node queue[10000]; void push(int x, int y){ Node node; node.r = x; node.c = y; rear++; queue[rear] = node; } Node pop(){ front++; return queue[front]; } void BFS(int x, int y){ reset(); front = rear = -1; push(x,y); visited[x][y] = 1; while(front != rear){ Node node = pop(); for(int k = 0; k < 4; k++){ int nx = node.r + dx[k]; int ny = node.c + dy[k]; if(nx >= 0 && nx < N && ny >= 0 && ny < N){ if(visited[nx][ny] == 0){ if(map[nx][ny] != 0){ push(nx, ny); visited[nx][ny] = visited[node.r][node.c] + 1; } } } } } } void solve(){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(map[i][j] == 1){ BFS(i,j); int max = 0; int cnt = 0; for(int k = 0; k < G; k++){ if(visited[gold[k][0]][gold[k][1]] != 0){ max = (visited[gold[k][0]][gold[k][1]] - 1) > max ? (visited[gold[k][0]][gold[k][1]] - 1) : max; gold[k][2] = 1; cnt++; } } if(max == 0) continue; if(maxCnt < cnt){ maxCnt = cnt; ans = 10000; } if(maxCnt == cnt){ if(ans > max){ ans = max; x_min = i; y_min = j; } } } } } } int main(){ freopen("input.txt", "r", stdin); int t; cin >> t; for(int tc = 0; tc < t; tc++){ cin >> N >> G; for(int i = 0; i < G; i++){ int r, c; cin >> r >> c; r--; c--; gold[i][0] = r; gold[i][1] = c; gold[i][2] = 0; } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ cin >> map[i][j]; visited[i][j] = 0; } } for(int i = 0; i < G; i++){ map[gold[i][0]][gold[i][1]] = 2; } ans = 10000; x_min = -1; y_min = -1; maxCnt = 0; solve(); reset(); BFS(x_min, y_min); for(int k = 0; k < G; k++){ if(visited[gold[k][0]][gold[k][1]] != 0){ gold[k][2] = 1; } } cout << "Case #" << tc+1 << endl; if(ans != 10000){ cout << ans << endl; for(int i = 0; i < G; i++){ if(gold[i][2] == 0){ cout << gold[i][0]+1 << " " << gold[i][1]+1 << endl; } } } else cout << "-1" << endl; } while(1){} }
Leave a Comment