Untitled
unknown
plain_text
2 years ago
2.3 kB
2
Indexable
#include<iostream> using namespace std; int N, G; int M[25][25]; int visit[25][25]; int A[6][2]; int visit_mv[6]; int f=-1, r=-1; int Qx[100000]; int Qy[100000]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; void push(int x,int y) { f++; Qx[f] =x; Qy[f] =y; } void pop(int &x,int &y) { r++; x= Qx[r]; y= Qy[r]; } void bfs(int x,int y) { f=r=-1; push(x,y); visit[x][y] =0; while(f != r) { 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 && visit[xx][yy]==-1 && M[xx][yy] != 0) { push(xx,yy); visit[xx][yy] = visit[x][y] +1; } } } } void reset() { for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) visit[i][j]=-1; } } int main() { freopen("Text.txt" , "r" , stdin); int t; cin >> t; for(int stt=1; stt<=t; stt++) { cin >> N >> G; for(int i=1; i<=G; i++) { cin >> A[i][0] >> A[i][1]; } for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { cin >> M[i][j]; } } for(int i=1; i<=G; i++) { M[A[i][0]][A[i][1]]=2; } ///////////////////////// int count_mv, s_max; int max_mv=0; int min_s =10000; for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { if(M[i][j] ==1 ){ count_mv =0; s_max =0; reset(); bfs(i,j); for(int q=1; q<=G; q++) { if(visit[A[q][0]][A[q][1]] != -1){ count_mv ++; } if(visit[A[q][0]][A[q][1]] > s_max){ s_max = visit[A[q][0]][A[q][1]]; } } ////////////////////////// if(count_mv > max_mv || (count_mv == max_mv && s_max < min_s)) { max_mv = count_mv; min_s = s_max; for(int k=1; k<=4; k++) { visit_mv[k]= visit[A[k][0]][A[k][1]]; } } } } } ////////////////////////////////////////////////////// if(max_mv == G) cout << "Case #" << stt <<endl << min_s << endl; else if(max_mv ==0) cout << "Case #" << stt << endl << "-1" << endl; else { cout << "Case #" << stt << endl << min_s<< endl; for(int i=1; i<=G; i++) { if(visit_mv[i] == -1) { cout << A[i][0] << " " << A[i][1] << endl; } } } } return 0; }
Editor is loading...