刺杀大使

DFS+二分

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],st[N][N];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int n,m;
bool dfs(int x,int y,int max_damage){
    st[x][y]=1;
    if(x==n)return true;
    for(int i=0;i<4;i++){
        int x1=x+dx[i],y1=y+dy[i];
        if(st[x1][y1])continue;
        if((x1>=1 and x1<=n and y1>=1 and y1<=m and g[x1][y1]<=max_damage)){
        if(dfs(x1,y1,max_damage))return true;
    }
    }
    return false;
}
int find(){
    int l=-1,r=1001;
    while(l+1<r){
        int mid=l+r>>1;
        memset(st,0,sizeof st);
        if(dfs(1,1,mid))r=mid;
        else l=mid;

    }
    return r;
}

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

BFS+二分

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],st[N][N];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int n,m;
typedef pair<int,int>PII;
bool bfs(int max_damage){
    memset(st,0,sizeof st); 
    queue<PII>q;
    q.push({1,1});
    st[1][1]=1;
    while(not q.empty()){
        PII fr=q.front();
        q.pop();
        int x=fr.first,y=fr.second;
        //st[x][y]=1;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(!(a>=1 and a<=n and b>=1 and b<=m))continue;
            if(st[a][b])continue;
            if(g[a][b]>max_damage)continue;
            q.push({a,b});
            //忘记加 st[ 
            st[a][b]=1;
        }
    }
    for(int i=1;i<=m;i++){
        if(!st[n][i])return false;
    }
    return true;

}
int find(){
    int l=-1,r=1001;
    while(l+1<r){
        int mid=l+r>>1;
        memset(st,0,sizeof st);
        if(bfs(mid))r=mid;
        else l=mid;

    }
    return r;
}

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

这里在我的 BFS 爆 MLE 了，原因是

在您的原始代码中，出现了内存超限（MLE）的错误，原因与 BFS（广度优先搜索）中访问标记 st 的更新位置有关。具体来说，您在 BFS 中将 st[x][y]=1; 放在了错误的位置，导致队列中存在大量重复的节点，从而使内存占用过大，最终导致 MLE。

1. 访问标记的位置问题：

在原始代码中，您在从队列中取出节点后，才对该节点进行访问标记：

cppCopy codewhile(not q.empty()){ PII fr=q.front(); q.pop(); int x=fr.first,y=fr.second; st[x][y]=1; // 在这里进行访问标记 // ... }

这样做的问题是，在节点被实际处理（即从队列中弹出）之前，没有标记它已经被访问过。这意味着在此节点被处理之前，可能会有其他路径再次将相同的节点加入队列，导致相同的节点被多次加入队列。

1. 重复节点导致队列膨胀：

由于没有在节点入队时就标记已访问，多个路径可能会将同一节点多次加入队列，导致队列中存在大量的重复节点。对于一个大的网格，这种重复会导致队列占用的内存急剧增加，从而导致 MLE。

1. 解决方法：

正确的做法是在将节点加入队列时，就立即标记为已访问，以防止重复入队：

cppCopy codefor(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(!(a>=1 and a<=n and b>=1 and b<=m)) continue; if(st[a][b]) continue; if(g[a][b]>max_damage) continue; q.push({a,b}); st[a][b]=1; // 在这里标记已访问 }

这样，当其他路径尝试将相同的节点加入队列时，由于 st[a][b] 已经为 1，就会跳过，从而避免了重复入队。

为什么会导致 MLE：

• 队列占用内存过大： 队列是一个动态数据结构，其大小随着加入的元素增多而增大。在 BFS 中，如果不及时标记已访问节点，队列中可能会包含大量重复的节点。对于一个大小为 n×mn \times mn×m 的网格，理论上队列的大小可能达到 O(n×m)O(n \times m)O(n×m) 的数量级，但由于重复入队，实际占用的内存会远超这个规模。
• 内存消耗超限： 在题目中，nnn 和 mmm 最大可达 1000，整个网格有 1,000,000 个节点。如果每个节点因为重复而多次加入队列，内存占用将远超程序的内存限制（通常为 64MB 或 128MB），从而导致 MLE。