【NOIP2017提高A组模拟9.21】传送蛋糕

题解

这题虽然看起来很毒瘤，暴力分超级少还超级难打，但是如果静心想还是可以想到很多结论的，可是我在比赛的时候spfa的数组开小了。。。
首先我们来看两个结论
结论1：任何一个传送门只会进/出一次（这个是十分显然的）
结论2：对于在两个不同的地方射出两个传送门的情况，我不可能回到第一个射出的传送门走到第二个传送门（因为这相当与你先走到射第二个传送门的位置，然后在走回第一个传送门）

有了这两个结论，我们就可以发现这题其实就相当于
1：上下左右走1步
2：往一个方向射出一个传送门，并且在若干步后通过另外一个后面射出的传送门走到那里
我们可以先预处理出每一个点想要构造出一个传送门并且走进去所需的时间，那么2中的四种走法所耗的时间其实是一样的
一共有n*n *8条边，可以打一发spfa

贴代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fo1(i,b,a) for(i=b;i>=a;i--)
using namespace std;

const int maxn=1305;

int map[maxn][maxn],cc[maxn][maxn],f[maxn][maxn],g[maxn][maxn][5][3];
int go[5][3];
int h[maxn*maxn*2][3];
bool bz[maxn][maxn];
int i,j,k,l,m,n,x,y,z,be1,be2,now,ed1,ed2;
char ch;

void make_cc(){
    go[1][1]=1; go[2][1]=-1; go[3][2]=1; go[4][2]=-1;
    i=now; j=0;
    while (i>j){
        j++;
        fo(k,1,4){
            x=go[k][1]+h[j][1];
            y=go[k][2]+h[j][2];
            if (bz[x][y]==false && map[x][y]!=1){
                bz[x][y]=true;
                cc[x][y]=cc[h[j][1]][h[j][2]]+1;
                h[++i][1]=x; h[i][2]=y;
            }
        }
    }
}
void make_g(){
    fo(i,1,n)
        fo(j,1,m) if (map[i][j]==1) z=j+1; else{
                g[i][j][1][1]=i;
                g[i][j][1][2]=z;
            }
    fo(i,1,n)
        fo1(j,m,1) if (map[i][j]==1) z=j-1; else{
            g[i][j][2][1]=i;
            g[i][j][2][2]=z;
        }
    fo(j,1,m)
        fo(i,1,n) if (map[i][j]==1) z=i+1; else{
            g[i][j][3][1]=z;
            g[i][j][3][2]=j;
        }
    fo(j,1,m)
        fo1(i,n,1) if (map[i][j]==1) z=i-1; else{
            g[i][j][4][1]=z;
            g[i][j][4][2]=j;
        }
}
void geans(){
    i=1;
    j=0;
    memset(bz,false,sizeof(bz));
    while (i>j){
        j++;
        fo(k,1,4){
            x=go[k][1]+h[j][1];
            y=go[k][2]+h[j][2];
            if (map[x][y]!=1){
                if (f[x][y]>f[h[j][1]][h[j][2]]+1){
                    f[x][y]=f[h[j][1]][h[j][2]]+1;
                    if (bz[x][y]==false){
                        bz[x][y]=true;
                        h[++i][1]=x;
                        h[i][2]=y;
                    }
                }
            }
        }
        fo(k,1,4){
            x=g[h[j][1]][h[j][2]][k][1];
            y=g[h[j][1]][h[j][2]][k][2];
            if (f[x][y]>f[h[j][1]][h[j][2]]+cc[h[j][1]][h[j][2]]){
                    f[x][y]=f[h[j][1]][h[j][2]]+cc[h[j][1]][h[j][2]];
                    if (bz[x][y]==false){
                        bz[x][y]=true;
                        h[++i][1]=x;
                        h[i][2]=y;
                    }
                }
        }
        bz[h[j][1]][h[j][2]]=false;
    }
}
int main(){
    freopen("portals.in","r",stdin);
    freopen("portals.out","w",stdout);
//  freopen("t1.in","r",stdin);
    scanf("%d%d",&n,&m);
    fo(i,1,m+2) map[1][i]=map[n+2][i]=1;
    fo(i,1,n+2) map[i][1]=map[i][m+2]=1;
    fo(i,1,n)
        fo(j,1,m){
            ch=getchar();
            while (ch!='.' && ch!='#' && ch!='C' && ch!='S') ch=getchar();
            if (ch=='#') map[i+1][j+1]=1; else
            if (ch=='S'){
                be1=i+1; be2=j+1;
            } else if (ch=='C'){
                ed1=i+1; ed2=j+1;
            } else map[i+1][j+1]=2;
        }
    n=n+2; m=m+2;
    fo(i,1,n) 
        fo(j,1,m)if (map[i][j]!=1){
        if (map[i][j-1]==1 || map[i][j+1]==1 || map[i+1][j]==1 || map[i-1][j]==1){
            h[++now][1]=i; h[now][2]=j; bz[i][j]=true; cc[i][j]=1;
        }
    }
    make_cc();
    make_g();
    h[1][1]=be1; h[1][2]=be2;
    memset(f,61,sizeof(f));
    f[be1][be2]=0;
    geans();
    printf("%d\n",f[ed1][ed2]);
    return 0;
}