P4442

iiiiiiiiiiiiiiiiiii · 2023-03-04 16:12:21 · 题解

一道最短路的变形题。

首先，把传送的过程拆开，就是先射两枪，再走到一个传送门，传送到另一个传送门，共花费 1 单位时间。

所以一共有两种走法：一种是走到相邻的格子（spfa 即可），一种是传送。

对于传送，在搜索时枚举起点传送门和终点传送门。在 spfa 之前 O(n^2) 递推预处理出每个点向四个方向直线走最近的墙的距离，走到起点传送门即可。当然，传送到每个位置有 3 种方案（起点传送门和终点传送门方向不同），但是起到的效果是一样的，需要取最小值。

注意：不一定是要挨着墙才能传送，会 78 分。

const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,sx,sy,tx,ty,vis[N][N],dis[N][N],b[N][N][4];
char ch[N][N];
struct node
{
    int x,y;
};
void bfs()
{
    memset(dis,0x3f,sizeof dis),dis[sx][sy]=0;
    queue<node> q;q.push({sx,sy}),vis[sx][sy]=1;
    while(!q.empty())
    {
        node f=q.front();q.pop(),vis[f.x][f.y]=0;
        for(int i=0;i<4;i++)//走到相邻格子
        {
            int nx=f.x+dx[i],ny=f.y+dy[i];
            if(ch[nx][ny]!='#'&&dis[f.x][f.y]+1<dis[nx][ny])
            {
                dis[nx][ny]=dis[f.x][f.y]+1;
                if(!vis[nx][ny])
                    q.push({nx,ny}),vis[nx][ny]=1;
            }
        }
        for(int i=0;i<4;i++)//传送，枚举终点
        {
            int d=b[f.x][f.y][i],minn=INF,nx=f.x+dx[i]*d,ny=f.y+dy[i]*d;
            for(int j=0;j<4;j++)//枚举起点
                if(i!=j)
                    minn=min(minn,b[f.x][f.y][j]);//取最小值转移
            minn+=dis[f.x][f.y]+1;
            if(dis[nx][ny]>minn)
            {
                dis[nx][ny]=minn;
                if(!vis[nx][ny])
                    vis[nx][ny]=1,q.push({nx,ny});
            }
        }
    }
}
void solve()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>ch[i][j];
            if(ch[i][j]=='C')
                sx=i,sy=j;
            if(ch[i][j]=='F')
                tx=i,ty=j;
        }
    for(int i=1;i<=n;i++)//预处理墙壁距离
        for(int j=m;j;j--)
            if(ch[i][j]=='#')
                b[i][j][0]=-1;
            else
                b[i][j][0]=b[i][j+1][0]+1;
    for(int j=1;j<=m;j++)
        for(int i=n;i;i--)
            if(ch[i][j]=='#')
                b[i][j][1]=-1;
            else
                b[i][j][1]=b[i+1][j][1]+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ch[i][j]=='#')
                b[i][j][2]=-1;
            else
                b[i][j][2]=b[i][j-1][2]+1;
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            if(ch[i][j]=='#')
                b[i][j][3]=-1;
            else
                b[i][j][3]=b[i-1][j][3]+1;
    bfs();
    if(dis[tx][ty]==INF)
        puts("nemoguce");
    else
        write(dis[tx][ty],"");
}