hugo dao vang 1
duyvan
plain_text
23 days ago
3.8 kB
2
Indexable
Never
#include <iostream> using namespace std; int A[22][22]; int visit[22][22]; int visitA[5]; int G[3][5]; int M,N; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int front, rear; int ans; int re; struct Node{ int r,c; }; Node queue[100000]; void enQueue(int x, int y){ Node node; node.r = x; node.c = y; rear++; queue[rear] = node; } Node deQueue(){ front++; return queue[front]; } int findMax(){ int max = visit[G[0][0]][G[1][0]]; for (int i = 1; i < N; i++) { if(visit[G[0][i]][G[1][i]] > max){ max = visit[G[0][i]][G[1][i]]; } } return max - 1; } void reSetvisit(){ for (int i = 1; i <= M; i++) { for (int j = 1; j <= M; j++) { if(A[i][j] == 0){ visit[i][j] = -1; }else { visit[i][j] = 0; } } } for (int i = 0; i < N; i++) { G[2][i] = 0; } } void BFS(int x, int y){ reSetvisit(); front = rear = -1; enQueue(x,y); visit[x][y] = 1; int cnt = 0; while (rear != front) { if(cnt == N){ break; } Node mid = deQueue(); for (int i = 0; i < N; i++) { if(mid.r == G[0][i] && mid.c == G[1][i]){ cnt++; G[2][i] = 1; } } for (int i = 0; i < 4; i++) { int tx = mid.r + dx[i]; int ty = mid.c + dy[i]; if (tx > 0 && tx <= M && ty > 0 && ty <= M && visit[tx][ty] == 0) { enQueue(tx,ty); visit[tx][ty] = visit[mid.r][mid.c] + 1; } } } if(cnt > ans){ ans = cnt; for (int i = 0; i < N; i++) { visitA[i] = G[2][i]; } re = findMax(); } else if (cnt == ans) { int tmp = findMax(); if(re > tmp){ re = tmp; for (int i = 0; i < N; i++) { visitA[i] = G[2][i]; } } } } int main(){ int tc, T; freopen("input.txt", "r", stdin); cin>> T; for (tc = 1; tc <= T; tc++) { cin>> M >> N; ans = re = 0; for (int i = 0; i < N; i++) { cin >> G[0][i] >> G[1][i]; } for (int i = 1; i <= M; i++) { for (int j = 1; j <= M; j++) { cin>> A[i][j]; } } for (int i = 0; i < N; i++) { A[G[0][i]][G[1][i]] = 3; } int check = 1; for (int i = 0; i < N; i++) { if(check == 0){ break; } for (int j = 0; j < 4; j++) { int tx = G[0][i] + dx[j]; int ty = G[1][i] + dy[j]; if (tx >= 1 && tx <= M && ty >=1 && ty <= M && A[tx][ty] == 1) { check = 0; } } } if(check == 1){ cout<< "Case #" << tc << endl; cout<< "-1" << endl; continue; } for (int i = 1; i <= M; i++) { for (int j = 1; j <= M; j++) { if(A[i][j] == 1){ BFS(i,j); } } } cout<< "Case #" << tc << endl; cout<< re << endl; for (int i = 0; i < N; i++) { if(visitA[i] == 0){ cout<<G[0][i] << " " << G[1][i] << endl; } } } return 0; }
Leave a Comment