Untitled
unknown
plain_text
a year ago
2.7 kB
6
Indexable
#include <iostream> using namespace std; int T, N, G; int R, C; int ans; int posX[4]; int posY[4]; bool gold[25][25]; int arr[25][25]; int visited[25][25]; int tmp[25][25]; class Queue{ int front, rear; int q[100000]; public: Queue(); void enQueue(int value); int deQueue(); void reset(); bool is_Empty(); }; Queue::Queue(){ front = rear = -1; } void Queue::enQueue(int value){ q[++rear] = value; } int Queue::deQueue(){ return q[++front]; } void Queue::reset(){ front = rear = -1; } bool Queue::is_Empty(){ return front == rear; } int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, -1, 1}; Queue rQueue, cQueue; int check; void BFS(int row, int col){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(arr[i][j] == 0){ visited[i][j] = -5; }else{ visited[i][j] = -1; } } } rQueue.reset(); cQueue.reset(); visited[row][col] = 0; rQueue.enQueue(row); cQueue.enQueue(col); while(rQueue.is_Empty() == false){ int cr = rQueue.deQueue(); int cc = cQueue.deQueue(); for(int i = 0; i < 4; i++){ int nr = cr + X[i]; int nc = cc + Y[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < N && visited[nr][nc] == -1){ visited[nr][nc] = visited[cr][cc] + 1; rQueue.enQueue(nr); cQueue.enQueue(nc); } } } for(int i = 0; i < G; i++){ int a = posX[i]; int b = posY[i]; if(visited[a][b] == -1){ check = 1; } } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(tmp[i][j] < visited[i][j] && gold[i][j] == false){ tmp[i][j] = visited[i][j]; } } } } int main(){ freopen("input.txt", "rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> G; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ gold[i][j] = false; } } for(int i = 0; i < G; i++){ cin >> R >> C; R--; C--; posX[i] = R; posY[i] = C; gold[R][C] = true; } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ cin >> arr[i][j]; } } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(arr[i][j] == 0){ tmp[i][j] = -5; }else{ tmp[i][j] = -1; } } } for(int i = 0; i < G; i++){ check = 0; BFS(posX[i], posY[i]); if(check == 1){ break; } } int ans = 10000000; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(tmp[i][j] != -5 && tmp[i][j] != -1 && gold[i][j] == false){ if(ans > tmp[i][j]){ ans = tmp[i][j]; } } } } cout << "Case #" << tc << endl; if( check == 1 || ans == 10000000){ cout << -1 << endl; }else{ cout << ans << endl; } } return 0; }
Editor is loading...
Leave a Comment