nyoj306 走迷宫(搜索+二分)
发布时间：2020-12-13 21:09:22 所属栏目：PHP教程 来源：网络整理
导读：题目306 题目信息 运行结果 本题排行 讨论区 走迷宫 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 5 描写 Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩
走迷宫时间限制：1000 ms | 内存限制：65535 KB
难度：5
这类思路的确是没想到 由于这道题的难度范围是0⑴20 可以对难度2分的方法 由于我深搜超时了 百度找到的思路。 也就是找到1个肯定的难度 #include <stdio.h>
#include <string.h>
int map[105][105];
bool vis[105][105];
int max,min,n;
bool ok;
int dir[4][2]={1,⑴,1,⑴};
bool limit(int x,int y)
{
if(vis[x][y]||x<0||y<0||x==n||y==n||ok)
return false;
return true;
}
void dfs(int x,int y,int l,int r)
{
if(x==n⑴&&y==n⑴)
{
ok=true;
return ;
}
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(limit(xx,yy)&&map[xx][yy]>=l&&map[xx][yy]<=r)
{
vis[xx][yy]=true;
dfs(xx,yy,l,r);
}
}
}
bool find(int k)
{
for(int i=min;i<=max;i++)
{
if(i+k>max)
break;
if(map[0][0]<i||map[0][0]>i+k) continue;
if(map[n⑴][n⑴]<i||map[n⑴][n⑴]>i+k) continue;
memset(vis,false,sizeof(vis));
ok=false;
dfs(0,i,i+k);
if(ok)
return true;
}
return false;
}
int bin_search()
{
int l=0,r=max-min,mid;
while(l<=r)
{
mid=(l+r)/2;
if(find(mid))
r=mid⑴;
else
l=mid+1;
}
return l;
}
int main()
{
while(~scanf("%d",&n))
{
max=-0x3fffffff;
min=0x3fffffff;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&map[i][j]);
max=map[i][j]>max?map[i][j]:max;
min=map[i][j]<min?map[i][j]:min;
}
}
printf("%dn",bin_search());
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |