Untitled
unknown
plain_text
2 years ago
2.1 kB
5
Indexable
#include <iostream> #define MAX 10000 using namespace std; struct Point{ int x,y; }; class Queue{ public: Point data[MAX]; int rear,front; Queue(){ rear=0; front=0; } bool IsEmpty(){ return rear==front; } bool IsFull(){ return front==(rear+1)%MAX; } void enQueue(int a,int b){ if(!IsFull()){ rear=(rear+1)%MAX; data[rear].x=a; data[rear].y=b; } } Point deQueue(){ if(!IsEmpty()){ front=(front+1)%MAX; return data[front]; }else return Point(); } }; bool danhdau[101][101]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,-1,1}; int main() { //freopen("input.txt","r",stdin); int TC; cin >> TC; int mang[101][101]; for(int tc=1;tc<=TC;tc++) { int N; cin >> N; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) { cin >> mang[i][j]; danhdau[i][j]=false; } int docaomax=0; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) if(mang[i][j]>docaomax) docaomax=mang[i][j]; bool ans; int l=0; int r=docaomax; while(l<=r) { int mid = (l+r)/2; for(int k=0; k<=docaomax-mid; k++) { for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) danhdau[i][j]=false; int minx=k; int maxx=k+mid; Queue walk; ans=false; if(mang[1][1]>=minx && mang[1][1]<=maxx) { walk.enQueue(1,1); danhdau[1][1]=true; } while(!walk.IsEmpty() && ans==false) { Point a=walk.deQueue(); for(int h=0;h<4;h++) { int newx=a.x + dx[h]; int newy=a.y + dy[h]; if(newx>=1 && newx<=N && newy>=1 && newy<=N && mang[newx][newy]>=minx && mang[newx][newy]<=maxx) { if(newx==N && newy==N) { ans=true; break; } if(danhdau[newx][newy]==false) { danhdau[newx][newy]=true; walk.enQueue(newx,newy); } } } } if(ans) break; } if(ans) r = mid - 1; else l = mid + 1; } cout << "#"<<tc<<" "<<l<<endl; } return 0; }
Editor is loading...