POJ2922 Honeymoon Hike(DFS/BFS+二分+枚举区间)
http://poj.org/problem?id=2922
题意:给你一个N*N的网格,并给出网格中每个点的海拔高度,现在要你找出从左上角到右下角那个点的一条路,且这条路所有点中,最高海拔-最低海拔之差最小。输出该最小值。
分析:(本题还可以用BFS实现,不过在下一道题目POJ2110用BFS实现本题,这两道题目基本一样)
二分海拔之差值。看看当海拔差为x时,是否能存在从左下角到右上角的路。
此题如果用常规DFS实现,会超时。对于下面矩阵:
a b c
d e f
g h i
我们初始在a,假设我们往下走到d,然后到e发现走不通了。我们此时标记了a,d,e。现在我们换初始方向为a到b到e走,因为就算我们之前因为走a d e不通(走过e点),不代表我们现在走a
b e也不通。(可能a b e可行呢,自己可以举例判断下比如矩阵:
5 5 100
0 5 200
100 5 5)
所以常规DFS方法需要对vis加锁,且当退出该点的dfs时需要解锁。类似于拓扑排序。
常规DFS超时代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
int n;
int map[maxn][maxn];
int vis[maxn][maxn];//判断当前节点时候被走过
int max_v,min_v;
int dr[]={-1,1,0,0};//上下左右
int dc[]={0,0,-1,1};
bool dfs(int r,int c,int d)
{
if(r==n&&c==n) return true; //到达终点
vis[r][c]=1;//加锁,表示正在搜索中
for(int dir=0;dir<4;dir++)
{
int nr=r+dr[dir],nc=c+dc[dir];
if(nr>=1&&nr<=n&&nc>=1&&nc<=n&&!vis[nr][nc])//我们只保证当前不走回头路
{
if(abs(map[nr][nc]-min_v)<=d && abs(map[nr][nc]-max_v)<=d )
{
min_v=min(min_v,map[nr][nc]);
max_v=min(max_v,map[nr][nc]);
if(dfs(nr,nc,d)) return true;
}
}
}
vis[r][c]=0;//解锁,表示搜索已结束,注意只要是vis==0的点就可以进入的。
return false;
}
bool check(int d)
{
max_v=min_v=map[1][1];
memset(vis,0,sizeof(vis));
return dfs(1,1,d);
}
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&map[i][j]);
int L=0,R=200;
while(R>L)
{
int mid=(R+L)>>1;
if(check(mid)) R=mid;
else L=mid+1;
}
printf("Scenario #%d:\n%d",kase,R);
}
return 0;
}
现在我们用枚举区间的DFS方法,我们现在不枚举高度差d了,我们枚举路径上可能的最大高度up和最小高度low。(他们之差就是d)。
同样对于下面矩阵:
a b c
d e f
g h i
假设此轮枚举是up=5,low=0,如果我们之前走a d e不通,那么我们之后走a b e也是不行的。e肯定越界了。所以这里我们vis数组只要走过一个点就标记,不用加锁解锁了。只要之前该点不可行,以后不论从哪里走过来该点都不可行。
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
int n;
int map[maxn][maxn];
int vis[maxn][maxn];//判断当前节点时候被走过
int max_v,min_v;
int dr[]={-1,1,0,0};//上下左右
int dc[]={0,0,-1,1};
bool dfs(int r,int c,int low,int up)
{
vis[r][c]=1; //错误,这里之前vis放到了if下面
if(map[r][c]>up || map[r][c]<low) return false;
if(r==n&&c==n) return true; //到达终点
for(int dir=0;dir<4;dir++)
{
int nr=r+dr[dir],nc=c+dc[dir];
if(nr>=1&&nr<=n&&nc>=1&&nc<=n&&!vis[nr][nc])
if(dfs(nr,nc,low,up)) return true; //错误,这里忘了返回true了
}
return false;
}
bool check(int d)
{
for(int low=0;low+d<=200;low++)
{
memset(vis,0,sizeof(vis)); //错误,这里memset放到了for上面
if(dfs(1,1,low,low+d)) return true;
}
return false;
}
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&map[i][j]);
int L=0,R=200;
while(R>L)
{
int mid=(R+L)>>1;
if(check(mid)) R=mid;
else L=mid+1;
}
printf("Scenario #%d:\n%d\n\n",kase,R);
}
return 0;
}
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
注意,目前POJ还不支持<bits/stdc++.h>(G++、C++都不支持)。HDU部分支持(G++支持,C++不支持)。 其他国外的oj,还有台湾的oj都支持,CF,Topcoder也都支持。 当然,其实这是一个偷懒的写法,但是会降低编译...
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
Hangover Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 44187 Accepted: 20574 Description How far can you make a stack of cards overhang a table? If you have one card, you can create a...
北大POJ1020-Anniversary Cake 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2676-Sudoku 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
注意,目前POJ还不支持<bits/stdc++.h>(G++、C++都不支持)。HDU部分支持(G++支持,C++不支持)。 其他国外的oj,还有台湾的oj都支持,CF,Topcoder也都支持。 当然,其实这是一个偷懒的写法,但是会降低编译...
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
用DFS深搜,你会发现时间复杂非常高,必然会超时(最大是300*300的图)。本题可以使用改进过的广搜或优先队列+bfs 或 记忆化广搜三种方法来解决。第一种方法:改进过的BFS:有些节点需要耗费2个单位时间,要