Untitled
unknown
plain_text
a year ago
2.4 kB
5
Indexable
#include<iostream> using namespace std; const int maxn = 100000; int t,n,g, mang[21][21], dis[21][21],r,c, ans; bool vt[21][21]; int rMove[] = {0,0,1,-1}; int cMove[] = {1,-1,0,0}; struct point{ int x,y; }; class Queue{ private: point arr[maxn]; int front, rear; public: Queue() { front = rear = -1; } bool isFull() { if (rear == maxn - 1) return true; return false; } bool isEmpty() { if (rear == front) return true; return false; } void enQueue(point val) { if (!isFull()) { rear++; arr[rear].x = val.x; arr[rear].y = val.y; } } point deQueue() { point s; if (!isEmpty()) { front++; s.x=arr[front].x; s.y=arr[front].y; } return s; } void reset() { front = rear = -1; } }; Queue myQueue; point vang[5]; void resets(){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ dis[i][j]=-1; vt[i][j]=true; } } myQueue.reset(); } void check(){ int maxdis =0, flag=0; for(int i=1; i<=g; i++){ if(dis[vang[i].x][vang[i].y] > maxdis) maxdis=dis[vang[i].x][vang[i].y]; else if(dis[vang[i].x][vang[i].y]==-1) flag = 1; } if(maxdis<ans && flag==0) ans = maxdis; } void bfs(int x, int y){ dis[x][y]=0; point s = {x,y}; myQueue.enQueue(s); vt[x][y]=false; while(!myQueue.isEmpty()){ s = myQueue.deQueue(); for(int i=0; i<4; i++){ int a = s.x + rMove[i]; int b = s.y + cMove[i]; if(a>=1 && b>=1 && a<=n && b<=n && dis[a][b]==-1 && vt[a][b]==true && mang[a][b]!=0){ dis[a][b] = dis[s.x][s.y] + 1; vt[a][b]=false; point p = {a,b}; myQueue.enQueue(p); } } } check(); } int main(){ freopen("Text.txt", "r" , stdin); cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n >> g; for(int i=1; i<=g; i++){ cin >> r >> c; vang[i].x=r; vang[i].y=c; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ cin >> mang[i][j]; } } ans=10000; for(int i=1; i<=g; i++){ mang[vang[i].x][vang[i].y]=2; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ resets(); if(mang[i][j]==1) bfs(i,j); } } if(ans == 10000){ cout << "Case #" << tc << endl; cout << "-1" << endl; }else{ cout << "Case #" << tc << endl; cout << ans << endl; } } return 0; }
Editor is loading...
Leave a Comment