题目传送门
解题思路:
二分答案,然后bfs验证,如果从一个路标可以达到其它所有路标,则答案可行.知道找到最佳答案.
AC代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 7 using namespace std; 8 9 int m,n,a[501][501],l,r,num,sum,ans,mid; 10 int dx[] = {-1,1,0,0},dy[] = {0,0,1,-1}; 11 bool vis[501][501],v[501][501],flag,pp; 12 13 inline bool check(int len,int x,int y) { 14 queue<int> q,q1; 15 q.push(x); 16 q1.push(y); 17 v[x][y] = 1; 18 while(!q.empty()) { 19 x = q.front(); 20 y = q1.front(); 21 q.pop(); 22 q1.pop(); 23 if(vis[x][y] == 1) num++; 24 if(num == sum) return true; 25 for(int i = 0;i < 4; i++) { 26 int xx = x + dx[i]; 27 int yy = y + dy[i]; 28 if(abs(a[xx][yy] - a[x][y]) > len) continue; 29 if(xx < 1 || xx > m || yy < 1 || yy > n) continue; 30 if(!v[xx][yy]) { 31 q.push(xx); 32 q1.push(yy); 33 v[xx][yy] = 1; 34 } 35 } 36 } 37 return false; 38 } 39 40 int main() { 41 int x,y; 42 scanf("%d%d",&m,&n); 43 for(int i = 1;i <= m; i++) 44 for(int j = 1;j <= n; j++){ 45 scanf("%d",&a[i][j]); 46 r = max(r,a[i][j]); 47 } 48 for(int i = 1;i <= m; i++) 49 for(int j = 1;j <= n; j++) { 50 int u; 51 scanf("%d",&u); 52 if(u == 1) 53 vis[i][j] = 1,sum++,x = i,y = j; 54 } 55 while(l < r) { 56 mid = (l + r) / 2; 57 memset(v,0,sizeof(v)); 58 flag = false; 59 num = 0; 60 if(check(mid,x,y)) 61 r = mid,ans = mid; 62 else 63 l = mid + 1; 64 } 65 printf("%d",ans); 66 return 0; 67 }