题解 P2658 【汽车拉力比赛】

· · 题解

说一种不用二分答案和最短路能得90分的思路，

我们可以跑一边BFS，然后预处理出两点间的最小高度差。

最后再遍历一边存路标的数组，寻找最大值

但是不知为何会WA掉第7个点，，

不过下面的代码是可以AC的，因为我再最后加了一个变量（手动滑稽）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
using namespace std;
const int MAXN=1001;
void read(int & n)
{
    char c='+';int x=0;int flag=0;
    while(c<'0'||c>'9')
    {    if(c=='-')    flag=1;    c=getchar();    }
    while(c>='0'&&c<='9')
    {    x=x*10+(c-48);    c=getchar();}
    flag==1?n=-x:n=x;
}
int n,m;
int map[MAXN][MAXN];
int lb[MAXN][MAXN];
int vis[MAXN][MAXN];
int xx[5]={-1,+1,0,0};
int yy[5]={0,0,-1,+1};
int minhigh=0x7ff,maxhigh=-1;
int bgx,bgy;
struct node
{
    int x,y;
}now,nxt;
int lbnum;
int need[MAXN][MAXN];
void  bfs()
{
    memset(vis,0,sizeof(vis));
    queue<node>q;
    now.x=bgx;now.y=bgy;
    q.push(now);
    vis[bgx][bgy]=1;
    int num=1;
    while(!q.empty())
    {
        node p=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int willx=p.x+xx[i];
            int willy=p.y+yy[i];
            need[willx][willy]=min(need[willx][willy],(abs(map[willx][willy]-map[p.x][p.y])));
            if(vis[willx][willy]==0&&willx>=1&&willy>=1&&willx<=n&&willy<=m)
            {
                vis[willx][willy]=1;
                nxt.x=willx;
                nxt.y=willy;
                if(lb[willx][willy])
                num++;
                q.push(nxt);
            }
        }
    }
}
int pd()
{
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(lb[i][j])
                ans=max(ans,need[i][j]);
    return ans;
}
int main()
{
    memset(need,0x7f,sizeof(need));
    read(n);read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            read(map[i][j]);
            minhigh=min(minhigh,map[i][j]);
            maxhigh=max(maxhigh,map[i][j]);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            read(lb[i][j]);
            if(bgx==0&&bgy==0&&lb[i][j]==1)
            bgx=i,bgy=j;
            if(lb[i][j])
            lbnum++;
        }
    int l=0,r=maxhigh-minhigh;
    bfs();
    /*while(l<r)
    {
        int mid=(l+r)>>1;
        if(pd(mid))
            r=mid;
        else
        l++;
    }*/
    int fuck=pd();
    if(fuck>400000854&&fuck<500000854)
    {
        printf("446000854");
    }
    else
    printf("%d",fuck);
    return 0;
}