题目链接：GMOJ 6286/GMOJ 5781。

题目

CYJ 想找到他的小伙伴 FPJ，CYJ 和 FPJ 现在位于一个房间里，这个房间的布置可以看成一个 $n$ 行 $m$ 列的矩阵，矩阵的每一个元素会是下列情况中的一种：

1. 障碍区域——这里有一堵墙（用 # 表示）。
2. 这里是CYJ最开始在的区域（用 C 表示）。
3. 这里是FPJ在的区域（用 F 表示）。
4. 空区域（用 . 表示）。

CYJ 携带了一个所谓传送枪的东西，这是

未完待续

题解

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
#include<queue>
using std::queue;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=500+5;
const int MAXM=500+5;
bool inque[MAXN*MAXM];
char ch;
int n,m;
int cnt,head[MAXN*MAXM*2],to[MAXN*MAXM*16],w[MAXN*MAXM*16],Next[MAXN*MAXM*16];
short sx,sy,ex,ey;
bool map[MAXN][MAXM];
short up[MAXN][MAXM],down[MAXN][MAXM];
short left[MAXN][MAXM],right[MAXN][MAXM];
int dis[MAXN*MAXM];
queue<int> Q;
inline void Add_Edge(int,int,int);
inline int GetID(int,int);
inline bool SPFA(int);
int main(void){
    freopen("cell.in","r",stdin);
    freopen("cell.out","w",stdout);
    register short i,j;
    n=read(),m=read();
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j){
            do{
                ch=getchar();
            }while(ch!='#'&&ch!='.'&&ch!='C'&&ch!='F');
            if(ch=='#')
                map[i][j]=false;
            else{
                map[i][j]=true;
                if(ch=='C')
                    sx=i,sy=j;
                if(ch=='F')
                    ex=i,ey=j;
            }
        }
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j){
            if(map[i][j]){
                up[i][j]=up[i-1][j]+1;
                left[i][j]=left[i][j-1]+1;
            }
            else
                up[i][j]=left[i][j]=-1;
        }
    for(i=n;i>=1;--i)
        for(j=m;j>=1;--j){
            if(map[i][j]){
                down[i][j]=down[i+1][j]+1;
                right[i][j]=right[i][j+1]+1;
            }
            else
                down[i][j]=right[i][j]=-1;
        }
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j){
            if(map[i][j]){
                if(map[i-1][j])
                    Add_Edge(GetID(i,j),GetID(i-1,j),1);
                if(map[i][j-1])
                    Add_Edge(GetID(i,j),GetID(i,j-1),1);
                if(map[i+1][j])
                    Add_Edge(GetID(i,j),GetID(i+1,j),1);
                if(map[i][j+1])
                    Add_Edge(GetID(i,j),GetID(i,j+1),1);
                register int d=min(min(up[i][j],down[i][j]),min(left[i][j],right[i][j]));
                Add_Edge(GetID(i,j),GetID(i-up[i][j],j),d+1);
                Add_Edge(GetID(i,j),GetID(i,j-left[i][j]),d+1);
                Add_Edge(GetID(i,j),GetID(i+down[i][j],j),d+1);
                Add_Edge(GetID(i,j),GetID(i,j+right[i][j]),d+1);
            }
        }
    SPFA(GetID(sx,sy));
    if(dis[GetID(ex,ey)]!=INF)
        printf("%d\n",dis[GetID(ex,ey)]);
    else
        puts("-1");
    return 0;
}
inline void Add_Edge(int u,int v,int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}
inline int GetID(int a,int b){
    return (a-1)*m+b;
}
inline bool SPFA(int s){
    register int i,ID;
    //memset(inque,false,sizeof(inque));
    //本来就是空的
    memset(dis,0X3F,sizeof(dis));
    inque[s]=true,dis[s]=0;
    Q.push(s);
    while(!Q.empty()){
        ID=Q.front();
        Q.pop();
        inque[ID]=false;
        for(i=head[ID];i;i=Next[i]){
            if(dis[ID]+w[i]<dis[to[i]]){
                dis[to[i]]=dis[ID]+w[i];
                if(!inque[to[i]]){
                    inque[to[i]]=true;
                    Q.push(to[i]);
                }
            }
        }
    }
    return true;
}