安徽索凯特建设工程有限公司网站,wordpress小论坛,视频号视频怎么下载,线下推广怎么做【题目来源】http://oj.ecustacm.cn/problem.php?id1753http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 游泳池可以等分为n行n列的小区域#xff0c;每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n)#xff0c;小明只能向上下左右四个方…【题目来源】http://oj.ecustacm.cn/problem.php?id1753http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 游泳池可以等分为n行n列的小区域每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n)小明只能向上下左右四个方向游不能游出泳池。 而小明对温度十分敏感他希望你帮他找一条最舒适的路径使路径上的最高的水温和最低的水温差值最小。【输入格式】 第一行输入一个正整数n。 接下来n行每行n个正整数表示方阵每个区域的温度a[i][j]。 所有数据保证随机。 (1≤n≤100,1≤a[i][j]≤1000)【输入格式】 一行一个数表示最小差值。【输入样例】 4 1 3 10 8 1 4 10 8 1 1 1 1 1 5 8 8【输出样例】 7【算法分析】 由于本题规定小明可以往上下左右四个方向游也就是说可以走回头路所以不能用动态规划。故依据本题题意若要找一条最舒适的路径的话就需要用搜索算法了。 但是如果简单地遍历出所有路径再比较得到温差最小路径肯定超时必须剪枝才能减少路径的搜索数量。 如何剪枝这是本题难点。因为如果已知最小温差只需一边游一边检查当前路径上的最大温差如果已经超过了允许的最小温差就不用走下去了。但是最小温差不能预知只能猜。最好的方法是使用二分法来猜这个最小温差。本题的解法是“DFS二分法”。 用“BFS二分法”也行请大家思考。【算法代码】
#includebits/stdc.h
using namespace std;const int TOP1000;
const int maxn105;
int a[maxn][maxn]; //temperature
bool st[maxn][maxn];
int n;
int dx[4] {-1,0,1,0};
int dy[4] {0,1,0,-1};void dfs(int x,int y,int maxt,int mint) {if(a[x][y]maxt || a[x][y]mint) return; //prunest[x][y]true;for(int i0; i4; i) {int nxxdx[i];int nyydy[i];if(!st[nx][ny] nx1 nxn ny1 nyn)dfs(nx,ny,maxt,mint);}
}bool check(int x) {for(int i1; ixTOP; i) {memset(st,0,sizeof(st));dfs(1,1,ix,i);if(st[n][n]) return 1;}return 0;
}int main() {scanf(%d,n);for(int i1; in; i) {for(int j1; jn; j) {scanf(%d,a[i][j]);}}int le1,riTOP;while(leri) {int mid(leri)/2;if(check(mid)) rimid-1;else lemid1;}printf(%d,ri1);return 0;
}/*
in:
4
1 3 10 8
1 4 10 8
1 1 1 1
1 5 8 8out:
7
*/
【参考文献】https://blog.csdn.net/weixin_43914593/article/details/131912564
