2021-09-22 22:16:56 星期三
#296. 最强大脑 题解
这是一道非常简单的bfs水题。。。。但是为什么没有人做呢？ 难道是因为网上搜不到？
理解题意：
输入为 2 个 n * m 大小矩阵。
第一个矩阵表示每个点的分数值， 第二个矩阵则表示这个点是否是特殊点 (1 & 0)
这里规定了一种移动方式， 你可以上左下右四个方向都走，但是重点是从你原来的点走过来，分数值的差不能大于 d, 求出最小的d使我们可以到达所有特殊点的位置。
分析样例
我们可以借助样例进行分析
3 5 // n, m
20 21 18 99 5 // 分数值
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1 // 特殊点
0 0 0 0 0
0 0 0 0 1
可以看出， 这个样例的 n = 3, m = 5
特殊点有
\[(1, 1), (1, 5), (3, 5) \]我们会发现 d 如果小于21， 无论怎么走都是走不完这三个点的。
思考
确定算法
本题的关键是如何找到一个最小的 d ，这个 d 要满足一定条件。
首先这个答案一定是具有单调性的，同时如果 d 的值小于答案就一定无法通过，大于答案就一定可以通过， 简而言之就是局部取舍性。
你想到了什么算法？
对 ！ 本题的另一个关键算法 二分答案
如何二分
我们首先要找到二分的几个要素， 首先:
二分什么？ - > d
二分区间 [l, r] 是？ - > [1, 1000000000] （题目中有所要求，分数值最大为1000000000，且为整数）
二分函数怎么写？ - > 通过bfs 确定是否可以到达所有的关键点.
如何写出这个代码
bfs 就是普通的bfs在入队列的时候判断一下是否可走， 在可走的地方做出标记，最后比较标记就可以了。
如果满足条件就往下找，不满足条件就往上找就可以了！
// 如果这么水的题你都 Copy，那你就真的颓废了
queue<node> q;
inline bool C(int X) {
while(q.size()) q.pop();
q.push(start);
memset(vis, 0, sizeof vis);
memset(vis2, 0, sizeof vis2);
vis[q.front().x][q.front().y] = 1;
vis2[q.front().x][q.front().y] = 1;
while (q.size()) {
node u = q.front(); q.pop();
for (int i = 1; i <= 4; i++) {
int x = dx[i] + u.x, y = dy[i] + u.y;
if (x >= 1 && x <= n && y >= 1 && y <= m) {
if (vis[x][y]) continue;
if (abs(a[u.x][u.y] - a[x][y]) < X) {
q.push((node){x, y});
vis[x][y] = 1;
if (b[x][y] == 1) vis2[x][y] = 1;
}
}
}
}
//思考：如何判断？
return 1;
}