题解 P6705 【[COCI2010-2011#7] POŠTAR】

_•́へ•́╬_ · 2020-09-23 00:31:59 · 题解

思路

套路题，枚举最小值，求出最大值，时间复杂度 O(n^4)。

正确性：最小值确定，从起点到各个终点的最大值也就确定了，没有更小的最大值，所以正确。

路径：（这个要知道，不然下次变成构造题就不行了）从起点到终点，再从终点返回起点，像这样依次遍历每个终点。本题不管走回头路，这样不影响最大值/最小值。

code

#include<algorithm>
#include<stdio.h>
#include<deque>
#define N 50
#define pr pair<int,int> 
using namespace std;
inline char nc()
{
    static char tp[9999],*p1,*p2;
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,9999,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int&x)
{
    register char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int a[N][N],ans[N][N],lsh[N*N],sz;char b[N][N];deque<pr>q;bool inq[N][N];
main()
{
    register int n,dx[8]={1,-1,0,0,1,1,-1,-1},dy[8]={0,0,1,-1,1,-1,1,-1},sx,sy,minn=1<<30,tmp;
    read(n);
    for(register int i=0;i<n;++i)for(register int j=0;j<n;++j)
    {
        for(;b[i][j]=nc(),b[i][j]!='K'&&b[i][j]!='P'&&b[i][j]!='.';);
        if(b[i][j]=='P'){sx=i;sy=j;b[i][j]='.';}
    }//输入
    for(register int i=0;i<n;++i)for(register int j=0;j<n;++j)read(a[i][j]),lsh[sz++]=a[i][j];
    sort(lsh,lsh+sz);sz=unique(lsh,lsh+sz)-lsh;//离散化
    for(register int i=0;i<sz&&lsh[i]<=a[sx][sy];++i)//枚举最小值
    {
        for(register int j=0;j<n;++j)for(register int k=0;k<n;++k)ans[j][k]=1<<30;
        q.push_back((pr){sx,sy});ans[sx][sy]=a[sx][sy];
        for(register int nx,ny;q.size();)//bfs求最大值
        {
            nx=q.front().first;ny=q.front().second;q.pop_front();inq[nx][ny]=0;
            for(register int j=0;j<8;++j)
            {
                if(nx+dx[j]<0||nx+dx[j]>=n||ny+dy[j]<0||ny+dy[j]>=n)continue;
                if(a[nx+dx[j]][ny+dy[j]]<lsh[i])continue;//小于枚举的最小值就不行
                if(ans[nx][ny]<a[nx+dx[j]][ny+dy[j]])//这里把两种情况分开写
                {//即将到达的点是最大值，更新最大值
                    if(a[nx+dx[j]][ny+dy[j]]<ans[nx+dx[j]][ny+dy[j]])
                    {
                        ans[nx+dx[j]][ny+dy[j]]=a[nx+dx[j]][ny+dy[j]];
                        if(!inq[nx+dx[j]][ny+dy[j]])
                        {
                            inq[nx+dx[j]][ny+dy[j]]=0;
                            q.push_back((pr){nx+dx[j],ny+dy[j]});
                        }
                    }
                }
                else//原来的那个是最大值，不更新最大值
                    if(ans[nx][ny]<ans[nx+dx[j]][ny+dy[j]])
                    {
                        ans[nx+dx[j]][ny+dy[j]]=ans[nx][ny];
                        if(!inq[nx+dx[j]][ny+dy[j]])
                        {
                            inq[nx+dx[j]][ny+dy[j]]=0;
                            q.push_front((pr){nx+dx[j],ny+dy[j]});
                        }
                    }
            }
        }
        tmp=0;
        for(register int j=0;j<n;++j)for(register int k=0;k<n;++k)if(b[j][k]=='K')
            if(tmp<ans[j][k])tmp=ans[j][k];//统计最大值
        if(minn>tmp-lsh[i])minn=tmp-lsh[i];//更新答案
    }
    printf("%d",minn);//输出
}