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

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，但你没有更新这两个端点的值。因此，无论如何循环，都只能得到右端点的值。

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

int left = 1; // 左端点的初始值
int right = n; // 右端点的初始值

while (left <= right) {
    int middle = (left + right) / 2; // 计算中间位置的值

    // 根据中间位置的值进行判断，并更新左端点或右端点的值
    if (middle > m) {
        // 更新右端点
        right = middle - 1;
    } else if (middle < m) {
        // 更新左端点
        left = middle + 1;
    } else {
        // 中间位置的值等于要查找的值
        // 进行相应的操作，然后退出循环
        break;
    }
}

cout << middle << endl; // 输出结果

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

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