Untitled
unknown
plain_text
2 years ago
2.4 kB
5
Indexable
#include<iostream> using namespace std; typedef struct{ int x; int y; }o_xy; int Map[100][100]; o_xy Queue[100000]; bool Visited[100][100]; int n; // cap cua ma tran dau vao int r =-1, f =-1; void push(o_xy value) { r++; Queue[r] = value; } o_xy pop() { f++; return Queue[f]; } void reset() { r = f = -1; for(int i = 0; i< 100; i++) for(int j =0; j< 100; j++) Visited[i][j] = false; } int dx[4] ={0,-1,0,1}; int dy[4] ={-1,0,1,0}; bool BFS(int low, int high) { if(Map[0][0] >= low && Map[0][0] <= high) { o_xy obj; obj.x = 0; obj.y = 0; push(obj); Visited[obj.x][obj.y] = true; while(r!=f) { obj = pop(); o_xy next; for(int i =0; i< 4; i++) { next.x = obj.x + dx[i]; next.y = obj.y + dy[i]; if(next.x >=0 && next.x < n && next.y >=0 && next.y < n ) { if(Map[next.x][next.y] >= low && Map[next.x][next.y] <= high && !Visited[next.x][next.y]) { if(next.x == n - 1 && next.y == n -1) { return true; } push(next); Visited[next.x][next.y] = true; } } } } } return false; } bool is_ok(int range, int minnn, int maxxx) { for (int i = minnn; i <= maxxx - range; i++) { reset(); if(BFS(i, i+ range)) return true; } return false; } int main() { //freopen("Text.txt","r",stdin); int T, maxx, minn; cin >> T; for(int tc = 1; tc <= T; tc++) { cin>>n; maxx = 0; minn = 110; reset(); for(int i =0; i<n; i++) { for(int j =0; j< n; j++) { cin>>Map[i][j]; if(Map[i][j] > maxx) { maxx = Map[i][j]; } if(Map[i][j] < minn) { minn = Map[i][j]; } } } int left = 0; int right = maxx - minn; int mid = 0; while(left <= right) { mid = (left + right)/2; if(is_ok(mid,minn, maxx)) { right = mid -1; } else left = mid +1; } cout<<"#"<<tc<<" "<<left<<endl; } return 0; } // Input 5 5 1 1 3 6 8 1 2 2 5 5 4 4 0 3 3 8 0 2 3 4 4 3 0 2 1 5 99 85 38 22 55 89 28 33 3 65 99 20 14 67 90 36 27 28 77 31 50 45 12 9 14 2 92 83 19 91 5 61 49 32 34 28 100 65 0 10 89 34 99 40 86 4 10 97 49 21 30 95 33 79 51 65 2 17 60 94 27 Output #1 2 #2 85 #3 9 #4 50 #5 43
Editor is loading...