nyoj306 dfs+二分搜索
程序员文章站
2022-07-10 09:18:38
...
题目大意:中文题。
算法思路:这种思路确实对我来说很新颖,我也是看了解题报告才知道。说白了,二分最小值和最大值的差,如果这个差值能够从起点走到终点,则说明这个差值是可行的,那我们就在减小,二分左半部分,否则二分右半部分。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define MAXN 105 #define INF 0x3f3f3f3f int n; int a[MAXN][MAXN],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; int MIN,MAX; bool visited[MAXN][MAXN],ok; void dfs(int x,int y,int left,int right) { if(x==n&&y==n) { ok=true; return; } for(int i=0;i<4;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(!visited[nx][ny]&&1<=nx&&nx<=n&&1<=ny&&ny<=n&&left<=a[nx][ny]&&a[nx][ny]<=right) { visited[nx][ny]=true; dfs(nx,ny,left,right); } } return; } bool isOk(int k) { for(int i=MIN;i<=MAX;i++) { if(i+k>MAX) break; if(a[1][1]<i||a[1][1]>i+k) continue; if(a[n][n]<i||a[n][n]>i+k) continue; memset(visited,false,sizeof(visited)); ok=false; visited[1][1]=true; dfs(1,1,i,i+k); if(ok) return true; } return false; } int main() { while(~scanf("%d",&n)) { MIN=INF;MAX=-INF; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); if(MIN>a[i][j]) MIN=a[i][j]; if(MAX<a[i][j]) MAX=a[i][j]; } } int l=0,r=MAX-MIN; while(l<r) { int mid=(l+r)/2; if(isOk(mid)) r=mid; else l=mid+1; } printf("%d\n",r); } return 0; }
上一篇: HDU 1016 Prime Ring Problem
下一篇: 栈空间分配 栈