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;
}