YbtOj练习:广搜1 最小权值

这道题的数据是不是有点水?还是题目描述有问题?

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=1005;
typedef pair<int,int> PII;
int g[N][N],ans=0x3f3f3f3f;
bool vis[N][N];
int n,m;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
PII Q[N*N];
int l,r,maxv;
bool check(int x)
{
    memset(vis,0,sizeof(vis));
    int hh=0,tt=-1;
    for(int i=1;i<=m;i++) Q[++tt]=make_pair(1,i);
    while(hh<=tt)
    {
        PII tmp=Q[hh++];
        for(int i=0;i<4;i++)
        {
            int nx=tmp.x+dx[i],ny=tmp.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(vis[nx][ny]) continue;
            if(g[nx][ny]>x) continue;
            vis[nx][ny]=1;
            if(nx==n) return true;
            Q[++tt]=make_pair(nx,ny);
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
     for(int j=1;j<=m;j++)
      {
          scanf("%d",&g[i][j]);
          r=max(r,g[i][j]);
      }
    for(int i=1;i<=m;i++) maxv=max(maxv,g[n][i]);
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",l);  //讲道理应该是这种写法printf("%d",max(maxv,l));  但直接输出l就可以过了 
    return 0;
}

 

上一篇:AOJ 0558 Cheese


下一篇:LeetCode 79,这道走迷宫问题为什么不能用宽搜呢?