首页 > 代码库 > 第四届河南省省赛 走迷宫 二分+DFS
第四届河南省省赛 走迷宫 二分+DFS
题目思路:使用二分查找路径中最大值和最小值之间的差值,从而确定出一组minn和maxn,对此组的minn和maxn经行DFS,如果可以找到一条路径,其中的最大值,最小值在minn~maxn的范围内,则查找成功。继续向左查找,否则向右查找
#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<stdio.h>#include<queue>#include<math.h>#define INF 0x3f3f3f3f#define MAX 105using namespace std;int Map[MAX][MAX],vis[MAX][MAX],v[4][2]={{1,0},{-1,0},{0,1},{0,-1}},n;bool check(int x,int y){ if(x>=1 && x<=n && y>=1 && y<=n && !vis[x][y]) return true; return false;}bool DFS(int x,int y,int maxn,int minn)//深搜,若搜索过程中未发现 超越minn 和 maxn的值则搜索成功{ if(x==n && y==n) return true; for(int i=0;i<4;i++) { int next_x=x+v[i][0]; int next_y=y+v[i][1]; if(check(next_x,next_y) && (Map[next_x][next_y]<=maxn && Map[next_x][next_y]>=minn)) { vis[next_x][next_y]=1; if(DFS(next_x,next_y,maxn,minn)) return true; } } return false;}int main(){ int L,R,Mid,maxn,minn,ans; while(scanf("%d",&n)!=EOF) { memset(Map,0,sizeof(Map)); minn=INF; maxn=-INF; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&Map[i][j]); minn=min(minn,Map[i][j]); maxn=max(maxn,Map[i][j]); } } L=abs(Map[n][n]-Map[1][1]);//首尾你无法避免,所以将其差的绝对值定为最左端 R=maxn-minn; while(L<=R)//对差值进行二分查找 { Mid=(L+R)/2; int ok=0; for(int i=minn;i<=maxn-Mid;i++) { if(Map[1][1] < i) break; if(Map[1][1] > i+Mid) continue; memset(vis,0,sizeof(vis)); if(DFS(1,1,i+Mid,i)) { ans=Mid; R=Mid-1; ok=1; break; } } if(!ok) L=Mid+1; } printf("%d\n",ans); } return 0;}
第四届河南省省赛 走迷宫 二分+DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。