淘金者
题解是深搜 + 二分梯子长度 , 但是深搜的代码不理解 , 求解释输入输出:5 8
XXXX....
...X.XXX
XXX..X..
......X.
XXXXXXXX
1 3
2
题解 : #include <bits/stdc++.h>
using namespace std;
int n, m, x, y, mid, vis, i, j, k, l, r, ans, o, p;
char S;
void dfs(int x, int y) { // 深搜代码不理解 , 跟梯子长度有什么关系
if (vis || S == '.')
return;
vis = 1;
if (y > 1)
dfs(x, y - 1);
if (y < m)
dfs(x, y + 1);
for (int i = 1; i <= mid; i++) {
if (x > i)
dfs(x - i, y);
if (x + i <= n)
dfs(x + i, y);
}
}
int main() {
cin >> n >> m;
for (i = 1; i <= n; i++) cin >> S + 1;
cin >> x >> y;
r = 205;
while (l <= r) {
mid = (l + r) >> 1;
memset(vis, 0, sizeof(vis));
dfs(n, m);
if (vis)
ans = mid, r = mid - 1;
else
l = mid + 1;
}
cout << ans;
return 0;
} 首先要搞明白“二分查找答案”是一个什么样的模式：当问题要求满足某个条件的最大/最小值时，如果任何一个给定的值是否满足条件是非常容易判定的，同时值大小到是否满足条件的映射是单调的，也就是说任何一个值如果满足条件，那么任何比该值更大/更小的值一定也满足条件，这时就通常可以尝试考虑二分答案。二分答案就是利用单调性，二分查找答案的值，每次判定当前范围的中点是否满足条件，根据结果和单调性调整下一次迭代中的搜索范围。
那显然，为了判定当前的 mid 是否足够大，需要在 dfs 也就是判定过程中使用当前 mid 的值，这一值决定了此次 dfs 中一次最多能向上/下移动的距离。
（说实话这个代码已经看懂二分梯子长度还没看懂我是没看懂的……感觉最难看懂的实际上是 cin >> S + 1 这句话） dolly_yos2 发表于 2022-7-19 17:52
首先要搞明白“二分查找答案”是一个什么样的模式：当问题要求满足某个条件的最大/最小值时，如果任何一个 ...
写出来了
谢谢 {:5_108:}
页:
[1]