2021-02-24

2020 icpc asia tehran regional contest E题

Social Distancing

题解

切比雪夫距离和曼哈顿距离相互转变

根据上述性质，可以将求切比雪夫不等式最小值转化为求曼哈顿距离的最小值。

二维矩阵求曼哈顿距离可以根据前缀和来减少时间复杂度，如果该点非病人，标记为1，代表该点权值为1；反之则标记为-1，后期求前缀和时该点权值定为0；然后分别沿四个方向求前缀和，取最小值即为每个点的最小曼哈顿距离。

最后根据最小曼哈顿距离dfs进行搜索即可得出答案。

代码

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
char a[505][505]={0};
int ans1[505][505]={0};
int dis[505][505]={0};
int sx,sy,ex,ey;
struct node
{
    int x,y,val;
};
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
int n,m;
int ans=-1;
int dfs(int x,int y,int val)
{
    if(ans>=val)
        return 0;
    if(x==ex&&y==ey)
    {
        ans=max(ans,val);
        return 0;
    }
    for(int i=1;i<=4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>m)
            continue;
        if(a[xx][yy]=='#')
            continue;
        int val1=min(val,dis[xx][yy]);
        if(ans1[xx][yy]>=val1)
            continue;
        ans1[xx][yy]=val1;
        dfs(xx,yy,val1);
    }
    return 0;
}
int mp[1050][1050]={0};
int mp_sum1[1050][1050]={0};
int mp_sum2[1050][1050]={0};
int mp_sum3[1050][1050]={0};
int mp_sum4[1050][1050]={0};
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",a[i]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dis[i][j]=inf;
        }
    }
    for(int i=0;i<1050;i++)
        for(int j=0;j<1050;j++)
            mp_sum1[i][j]=mp_sum2[i][j]=mp_sum3[i][j]=mp_sum4[i][j]=inf;
    int sum=0;
    for(int i=0;i<=n+1;i++)
    {
        int j=0;
        mp[i+j][i-j+500]=inf;
        j=m+1;
        mp[i+j][i-j+500]=inf;
    }
    for(int j=0;j<=m+1;j++)
    {
        int i=0;
        mp[i+j][i-j+500]=inf;
        i=n+1;
        mp[i+j][i-j+500]=inf;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='*')
            {
                sum++;
                mp[i+j][i-j+500]=-1;
            }
            else
            {
                mp[i+j][i-j+500]=1;
            }
            if(a[i][j]=='S')
                sx=i,sy=j;
            if(a[i][j]=='E')
                ex=i,ey=j;
        }
    }
    for(int i=1;i<1050;i++)
    {
        for(int j=1;j<1050;j++)
        {
            if(mp[i][j]==-1)
                mp_sum1[i][j]=0;
            else
                mp_sum1[i][j]=min(mp_sum1[i][j],min(mp_sum1[i-1][j],mp_sum1[i][j-1])+mp[i][j]);
        }
    }

    for(int i=1;i<1050;i++)
    {
        for(int j=1049;j>=1;j--)
        {
            if(mp[i][j]==-1)
                mp_sum2[i][j]=0;
            else
                mp_sum2[i][j]=min(mp_sum2[i][j],min(mp_sum2[i-1][j],mp_sum2[i][j+1])+mp[i][j]);
        }
    }


    for(int i=1049;i>=1;i--)
    {
        for(int j=1;j<1050;j++)
        {
            if(mp[i][j]==-1)
                mp_sum3[i][j]=0;
            else
                mp_sum3[i][j]=min(mp_sum3[i][j],min(mp_sum3[i+1][j],mp_sum3[i][j-1])+mp[i][j]);
        }
    }    


    for(int i=1049;i>=1;i--)
    {
        for(int j=1049;j>=1;j--)
        {
            if(mp[i][j]==-1)
                mp_sum4[i][j]=0;
            else
                mp_sum4[i][j]=min(mp_sum4[i][j],min(mp_sum4[i+1][j],mp_sum4[i][j+1])+mp[i][j]);
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int xx=i+j,yy=i-j+500;
            dis[i][j]=min(min(mp_sum1[xx][yy],mp_sum2[xx][yy]),min(mp_sum3[xx][yy],mp_sum4[xx][yy]));
        }
    }

    dfs(sx,sy,dis[sx][sy]);
    if(ans!=-1&&sum==0)
    {
        printf("safe\n");
        return 0;
    }
    printf("%d\n",ans);
    return 0;
}