题目
CYJ 想找到他的小伙伴 FPJ,CYJ 和 FPJ 现在位于一个房间里,这个房间的布置可以看成一个 $n$ 行 $m$ 列的矩阵,矩阵的每一个元素会是下列情况中的一种:
- 障碍区域——这里有一堵墙(用
#
表示)。 - 这里是CYJ最开始在的区域(用
C
表示)。 - 这里是FPJ在的区域(用
F
表示)。 - 空区域(用
.
表示)。
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;
}
近期评论