jsp做网站都可以做什么,wordpress自己写界面,免费下载应用软件,建站官网模板题目
农夫约翰和贝西牛已经开始了其中一个“积极”的假期。他们整天都在山里散步#xff0c;然后在一天结束时#xff0c;他们厌倦了回到度假小屋。
由于攀爬需要大量能量并且已经疲惫#xff0c;他们希望使用其最高和最低高度之间的差异最小的路径返回到机舱#xff0c;…题目
农夫约翰和贝西牛已经开始了其中一个“积极”的假期。他们整天都在山里散步然后在一天结束时他们厌倦了回到度假小屋。
由于攀爬需要大量能量并且已经疲惫他们希望使用其最高和最低高度之间的差异最小的路径返回到机舱无论路径有多长。帮助FJ找到这条易于移动的路径。
山的地图由N×N2 N 100整数高程矩阵给出0 任意高程 110FJ和Bessie当前位于左上角位置第1行列 1并且舱室位于右下方第N行第N列。它们可以向右向左向顶部或向网格底部移动。他们不能在对角线上旅行。 输入 *第1行单个整数N
*行2…N 1每行包含N个整数每个整数指定一个正方形的高度。第2行包含网格的第一行顶部; 第3行包含第二行依此类推。该行上的第一个数字对应于网格的第一个左列依此类推。 产量 *第1行一个整数它是最佳路径上的最小高度差。 样本输入 5 1 1 3 6 8 1 2 2 5 5 4 4 0 3 3 8 0 2 3 4 4 3 0 2 1 样本输出 2
分析与解答
这题根滑雪那到一样用普通的搜索根本没法写因为广搜每个节点只访问一次而这个并不是只找一条路。深搜的话找路径需要记录当前DFS路径上所遇到所有点的高度有些路径中的某个点高度过高一看就知道不需要走但是深搜还是要走所以时间上浪费
这题利用二分我们二分的是个高度差就是说当前高度差处于[low,up]这个区间的范围之中对于这个区间[low,up]我们用BFS找,看看能不能找到一条从左上角到右下角的路,
我们bfs参数是数的高度他们的高度差我们二分出来了现在就不断枚举所有可能的起止高度进行遍历比如高度差位mid那么区间就是lowlowmidlow从一递增到一百一.。只要有一个路径的数都在区间里面我们就return bfs从11开始搜先判断起点是不是在区间范围内不是的话返回是的话入队然后只要队不空取队首然后上下左右移动一般的bfs只要是第一次出现在这个区域内就入队了这个区间的bfs 是有选择的入队只有属于我们规定的的区间的我们才让他入队就这么一直如下去如果碰到这个坐标是nn就说明已经找到了属于这个区间的路径返回true 注意两个if的顺序四个方向能走的不一定在这个区间里
参考代码
#includeiostream
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int maxn105;
int map[maxn][maxn];
int vis[maxn][maxn];
int n;
int to[4][2]{{-1,0},{1,0},{0,-1},{0,1}};
struct node{int x,y;
};int bfs(int l,int r)
{if(map[1][1]l||map[1][1]r) return 0;queuenode q;node k;k.x1;k.y1;q.push(k);vis[1][1]1;while(!q.empty()){node a,b;bq.front();q.pop();int xb.x;int yb.y;for(int j0;j4;j){int axxto[j][0];int ayyto[j][1];if(ax1axnay1ayn!vis[ax][ay]){vis[ax][ay]1;if(map[ax][ay]lmap[ax][ay]r){if(axnayn) return true; a.xax;a.yay;q.push(a);}}}}return false;}int check(int d){for(int i0;id110;i){memset(vis,0,sizeof(vis));if(bfs(i,id)) return 1; }return false;}
int main()
{scanf(%d,n);for(int i1;in;i)for(int j1;jn;j)scanf(%d,map[i][j]);int l0,r110;while(rl){int mid (rl)/2;if(check(mid)) rmid;else lmid1;}printf(%d\n,r);return 0;
}
}
欣赏一下dfs
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int maxn1005;
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(rncn) return true; //到达终点for(int dir0;dir4;dir){int nrrdr[dir],nccdc[dir];if(nr1nrnnc1ncn!vis[nr][nc])if(dfs(nr,nc,low,up)) return true; //错误,这里忘了返回true了}return false;
}
bool check(int d)
{for(int low0;lowd200;low){memset(vis,0,sizeof(vis)); //错误,这里memset放到了for上面if(dfs(1,1,low,lowd)) return true;}return false;
}
int main()
{int T; scanf(%d,T);for(int kase1;kaseT;kase){scanf(%d,n);for(int i1;in;i)for(int j1;jn;j)scanf(%d,map[i][j]);int L0,R200;while(RL){int mid(RL)1;if(check(mid)) Rmid;else Lmid1;}//printf(Scenario #%d:\n%d\n\n,kase,R);printf(%d\n,R);}return 0;
}
