Description
有一副n*m的地图,有n*m块地,每块是下列四种中的一种: 墙:用#表示,墙有4个面,分别是前面,后面,左面,右面。 起点:用C表示,为主角的起点,是一片空地。 终点:用F表示,为主角的目的地,是一片空地。 空地:用 . 表示。 其中除了墙不能穿过,其他地方都能走。 主角有以下3种操作: 1.移动到相邻的前后左右的地方,花费一个单位时间。 2.向前后左右其中一个方向发射子弹,子弹沿直线穿过,打在最近的一堵墙的一面,然后墙的这面就会形成一个开口通往秘密通道。同一时间最多只能有两个开口,若出现有3个开口,出现时间最早的开口会立即消失。该操作不用时间。 3.可以从一个与开口相邻的空地跳进去,进入秘密通道,从另外一个开口正对的空地跳出来。这个过程花费一个单位时间。 地图四周都是墙,问主角最少用多少时间从C走到F。C和F 只会出现一次。
Input
第一行输入两个正整数n,m。 接下来n行,每行m个字符描述地图。
Output
输出1个整数,表示最短时间完成路途。如果无解输出nemoguce
Sample Input
Input 14 4#####.F##C.#####Input 26 8#########.##..F##C.##..##..#...##.....##########Input 34 5######C#.####F######
Sample Output
Output 12Output 24Output 3nemoguce
Data Constraint
对于50%的数据,4≤ n,m≤ 15。 对于100%的数据,4≤ n,m≤ 500。
Hint
总共用到8次操作,时间之和为4。如下图所示 1.向左射一枪,在(3,1)的右面出现开口。 2.向下射一枪,在(6,2)的上面出现开口。 3.向左从(3,1)进入秘密通道,从(6,2)中出来,到达(5,2)。用1单位时间。 4.向右射一枪,在(5,7)的左面出现开口,(3,1)右面的开口消失。 5.走进(6,2)的开口,出来到(5,6)。用1单位时间。 6.向上射一枪,在(1,6)的下面出现开口。 7.经过秘密通道,走到(2,6)。用1单位时间。 8.走到终点。用1单位时间。
题解
- 首先,可以预处理出每个格子到上下左右第一堵墙在哪里
- 然后考虑点连边跑最短路
- ①向它的四周连一条权值为1的边
- ②向上下左右第一堵墙连一条与它距离的墙为权值的边
- 最后跑一边spfa最短路就好了
代码
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int mo=500000,dx[4]={ 0,1,0,-1},dy[4]={ 1,0,-1,0}; 7 struct edge { int x,y; }st,en; 8 int d[mo+1][2],dis[501][501],bz[501][501],a[501][501],f[501][501][4],n,m; 9 char map[501][501];10 void bfs()11 {12 int tail=0,head=1;13 memset(a,127,sizeof(a));14 for (int i=1;i<=n;i++)15 for (int j=1;j<=m;j++)16 if (map[i][j]=='#')17 d[++tail][0]=i,d[tail][1]=j,a[i][j]=0; 18 while (head n||y>m||x<1||y<1||a[u][v]+1>=a[x][y]) continue;26 d[++tail][0]=x,d[tail][1]=y;27 a[x][y]=a[u][v]+1;28 }29 }30 }31 void spfa()32 {33 int head=0,tail=1;34 while (head =dis[x][y])) continue;43 dis[x][y]=dis[u][v]+1;44 if (bz[x][y]) continue;45 bz[x][y]=1;46 tail=tail%mo+1;47 d[tail][0]=x,d[tail][1]=y;48 } 49 for (int i=0;i<4;i++)50 {51 int x=u,y=v;52 if (i>1) x=f[u][v][i]; else y=f[u][v][i];53 if (dis[u][v]+a[u][v]>=dis[x][y]) continue;54 dis[x][y]=dis[u][v]+a[u][v];55 if (bz[x][y]) continue;56 bz[x][y]=1;57 tail=tail%mo+1;58 d[tail][0]=x,d[tail][1]=y; 59 }60 }61 }62 int main()63 {64 // freopen("portal.in","r",stdin);65 // freopen("portal.out","w",stdout);66 scanf("%d%d",&n,&m);67 memset(dis,127,sizeof(dis));68 for (int i=1;i<=n;i++)69 {70 scanf("%s",map[i]+1);71 for (int j=1;j<=m;j++)72 if (map[i][j]=='C') st.x=i,st.y=j,dis[i][j]=0;73 else if (map[i][j]=='F') en.x=i,en.y=j;74 }75 for (int i=1;i<=n;i++)76 {77 f[i][1][0]=1;78 for (int j=2;j<=m;j++) if (map[i][j-1]=='#') f[i][j][0]=j; else f[i][j][0]=f[i][j-1][0];79 f[i][m][1]=m;80 for (int j=m-1;j;j--) if (map[i][j+1]=='#') f[i][j][1]=j; else f[i][j][1]=f[i][j+1][1];81 }82 83 for (int j=1;j<=m;j++)84 {85 f[1][j][2]=1;86 for (int i=2;i<=n;i++) if (map[i-1][j]=='#') f[i][j][2]=i; else f[i][j][2]=f[i-1][j][2];87 f[n][j][3]=n;88 for (int i=n-1;i;i--) if (map[i+1][j]=='#') f[i][j][3]=i; else f[i][j][3]=f[i+1][j][3];89 }90 bfs();91 memset(bz,0,sizeof(bz));92 d[1][0]=st.x,d[1][1]=st.y;93 spfa();94 if (dis[en.x][en.y]>1e9) printf("nemoguce\n");95 else printf("%d\n",dis[en.x][en.y]);96 }