为什么二分出来的结果不对，一直是右端点

lsmCC

// 考察dfs跟二分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int n,m,p[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0-1};
bool vis[N][N];
bool dfs(int x,int y,int P)
{
    if(x==n)return true;
    vis[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&!vis[a][b]&&p[a][b]<=P)
        {
            if(dfs(a,b,P))return true;
        }
        //p大，易true

    }
    return false;
}
int find()
{
    int l=-1,r=1001;
    while(l+1<r)
    {
        int mid=l+r>>1;
        memset(vis,0,sizeof(vis));  // 每次二分都要清空
        if(dfs(1,1,mid)) r=mid;
        else l=mid;
    }
    return r;
}



int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>p[i][j];
        }
    }
    cout<<find()<<endl;
}

FishC

你的问题出在二分查找的逻辑上。在二分查找中，我们需要确定左端点和右端点，并计算出中间位置的值。然后根据中间位置的值来更新左端点或右端点，在下一次循环中继续进行二分查找。

在你的代码中，你只是简单地将左端点设为1，右端点设为n，但你没有更新这两个端点的值。因此，无论如何循环，都只能得到右端点的值。

正确的二分查找应该如下所示：

1. int left = 1; // 左端点的初始值
   
2. int right = n; // 右端点的初始值
   
3. 
   
4. while (left <= right) {
   
5.     int middle = (left + right) / 2; // 计算中间位置的值
   
6. 
   
7.     // 根据中间位置的值进行判断，并更新左端点或右端点的值
   
8.     if (middle > m) {
   
9.         // 更新右端点
   
10.         right = middle - 1;
    
11.     } else if (middle < m) {
    
12.         // 更新左端点
    
13.         left = middle + 1;
    
14.     } else {
    
15.         // 中间位置的值等于要查找的值
    
16.         // 进行相应的操作，然后退出循环
    
17.         break;
    
18.     }
    
19. }
    
20. 
    
21. cout << middle << endl; // 输出结果

复制代码

希望我的回答能够帮到你。如果还有其他问题，请随时提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。