常州Day8

T1
受昨天教学内容影响（什，我比赛时的思路就是往DP上靠的
后来知道显然不行，人也可能往迷阵上一行走，从而更新答案
又可从题目中获取信息“整个部队受到的伤害值为所有士兵的伤害值中的最大值”“怎么安排他们的行进路线可以使得整个团队的伤害值最小”
像这样要让最大值最小的题目 就优先考虑二分答案
每枚举一个答案就进行一次宽搜，看看能否从第一行走到第n行

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
int n,m,p[1005][1005];
bool vis[1005][1005];
int ans;
queue <PII > q; 
bool bfs(int mid){
    while (!q.empty())q.pop();
    q.push({1,1});
    vis[1][1]=1;
    while(!q.empty()){
        PII qq=q.front();
        int lx=qq.first,ly=qq.second;
        q.pop();
        if(lx==n)return true;
        if(p[lx+1][ly]<=mid && lx+1<=n && !vis[lx+1][ly]){
            q.push({lx+1,ly});
            vis[lx+1][ly]=1;
        }
        if(p[lx][ly+1]<=mid && ly+1<=m && !vis[lx][ly+1]){
            q.push({lx,ly+1});
            vis[lx][ly+1]=1;
        }
        if(p[lx][ly-1]<=mid && ly-1>=1 && !vis[lx][ly-1]){
            q.push({lx,ly-1});
            vis[lx][ly-1]=1; 
        }
        if(p[lx-1][ly]<=mid && lx-1>=1 && !vis[lx-1][ly]){
            q.push({lx-1,ly});
            vis[lx-1][ly]=1;
        }
    }
    return false;
}
int main(){
    freopen("escape.in","r",stdin);
    freopen("escape.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>p[i][j];
            ans=max(ans,p[i][j]);
        }
    }
    int l=0,r=ans;
    while(l<=r){
        int mid=(l+r)/2;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                vis[i][j]=0;
            }
        }
        if(bfs(mid)){
            r=mid-1;ans=mid;
        }else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}