题解 P1902 刺杀大使

首先注意到，只需要到达一个开关，就可以开启所有开关（打开所有门）

所以我们就可以想到，我们要寻找一条从任意 \(1-m\) 开关（因为访问一个开关就可以开启所有开关，详情见看ps）到达 \(1-m\) 门的所有路径中伤害数最大值最小路径

很容易就想到了，最大值最小，明显是二分答案（伤害数），二分每条路径中的伤害数最大值

• 如果路径中的伤害数大于二分的答案，说明此答案不满足，就将二分的答案调大，以此找到满足条件的路径
• 如果满足条件，就试着找到更小的答案，将二分答案调小，寻找满足条件的路径

ps：看起来可能要遍历所有的开关来找到到达门的路径，实际上，因为开关的伤害数为 \(0\) ，所以可以直接从第一个开关开始 \(bfs\) ，借此访问到每个开关的同时，寻找路径的可能性，累计的最大伤害数都是 \(0\)

// #Tyrue#
#include<map>
#include<queue>
#include<cstdio>
#include<string>
#include<string.h>
#include<iostream>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int N=1e3+10;
int T,n,m,l=1e9,r=-1e9;
int a[N][N],vis[N][N];
int dx[5]{0,0,0,1,-1},dy[5]{0,1,-1,0,0};
struct Node{
    int x,y;
};
queue<Node> q;
bool bfs(int xz){
    memset(vis,0,sizeof vis);
    while(!q.empty()){
        q.pop();
    }
    q.push((Node){1,1});
    vis[0][0]=1;
    while(!q.empty()){
        Node f=q.front();
        q.pop();
        if(f.x==n){
            return 1;
        }
        for(int i=1;i<=4;i++){
            int xx=f.x+dx[i],yy=f.y+dy[i];
            if(xx<=n && xx>=1 && yy<=m && yy>=1 && !vis[xx][yy] && a[xx][yy]<=xz){
                q.push((Node){xx,yy});
                vis[xx][yy]=1;
            }
        }
    }
    return 0;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            l=min(l,a[i][j]);
            r=max(r,a[i][j]);
        }
    }
    int ans;
    // printf("%d %d\n",l,r);
    while(l<r){
        int mid=(l+r)>>1;
        // printf("%d %d %d\n",l,r,mid);
        if(bfs(mid)){
            r=mid;
            // ans=mid;
        }else{
            // printf("%d\n",l);
            l=mid+1;
        }
    }
    printf("%d",l); 
    return 0;
}