[已解决]淘金者

柿子饼同学

题解是深搜 + 二分梯子长度 , 但是深搜的代码不理解 , 求解释
输入输出:

1. 5 8
   
2. XXXX....
   
3. ...X.XXX
   
4. XXX..X..
   
5. ......X.
   
6. XXXXXXXX
   
7. 1 3

复制代码

1. 2

复制代码

题解 :

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n, m, x, y, mid, vis[205][205], i, j, k, l, r, ans, o, p;
   
4. char S[205][205];
   
5. void dfs(int x, int y) { // 深搜代码不理解 , 跟梯子长度有什么关系
   
6.     if (vis[x][y] || S[x][y] == '.')
   
7.         return;
   
8.     vis[x][y] = 1;
   
9.     if (y > 1)
   
10.         dfs(x, y - 1);
    
11.     if (y < m)
    
12.         dfs(x, y + 1);
    
13.     for (int i = 1; i <= mid; i++) {
    
14.         if (x > i)
    
15.             dfs(x - i, y);
    
16.         if (x + i <= n)
    
17.             dfs(x + i, y);
    
18.     }
    
19. }
    
20. int main() {
    
21.     cin >> n >> m;
    
22.     for (i = 1; i <= n; i++) cin >> S[i] + 1;
    
23.     cin >> x >> y;
    
24.     r = 205;
    
25.     while (l <= r) {
    
26.         mid = (l + r) >> 1;
    
27.         memset(vis, 0, sizeof(vis));
    
28.         dfs(n, m);
    
29.         if (vis[x + 1][y + 1])
    
30.             ans = mid, r = mid - 1;
    
31.         else
    
32.             l = mid + 1;
    
33.     }
    
34.     cout << ans;
    
35.     return 0;
    
36. }

复制代码

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2022-7-19 17:52:21

首先要搞明白“二分查找答案”是一个什么样的模式：当问题要求满足某个条件的最大/最小值时，如果任何一个给定的值是否满足条件是非常容易判定的，同时值大小到是否满足条件的映射是单调的，也就是说任何一个值如果满足条件，那么任何比该值更大/更小的值一定也满足条件，这时就通常可以尝试考虑二分答案。二分答案就是利用单调性，二分查找答案的值，每次判定当前范围的中点是否满足条件，根据结果和单调性调整下一次迭代中的搜索范围。
那显然，为了判定当前的 mid 是否足够大，需要在 dfs 也就是判定过程中使用当前 mid 的值，这一值决定了此次 dfs 中一次最多能向上/下移动的距离。
（说实话这个代码已经看懂二分梯子长度还没看懂我是没看懂的……感觉最难看懂的实际上是 cin >> S[i] + 1 这句话）

跳转到最佳答案楼层

dolly_yos2

首先要搞明白“二分查找答案”是一个什么样的模式：当问题要求满足某个条件的最大/最小值时，如果任何一个给定的值是否满足条件是非常容易判定的，同时值大小到是否满足条件的映射是单调的，也就是说任何一个值如果满足条件，那么任何比该值更大/更小的值一定也满足条件，这时就通常可以尝试考虑二分答案。二分答案就是利用单调性，二分查找答案的值，每次判定当前范围的中点是否满足条件，根据结果和单调性调整下一次迭代中的搜索范围。
那显然，为了判定当前的 mid 是否足够大，需要在 dfs 也就是判定过程中使用当前 mid 的值，这一值决定了此次 dfs 中一次最多能向上/下移动的距离。
（说实话这个代码已经看懂二分梯子长度还没看懂我是没看懂的……感觉最难看懂的实际上是 cin >> S[i] + 1 这句话）

柿子饼同学

dolly_yos2 发表于 2022-7-19 17:52
首先要搞明白“二分查找答案”是一个什么样的模式：当问题要求满足某个条件的最大/最小值时，如果任何一个 ...

写出来了
谢谢

hornwong