「省选模拟赛」[BZOJ1556] 小奇走迷宫
原题：「bzoj1556」墓地秘密
「题目背景」
小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫，一旁的木牌上写着：“你可以回头，但你永远无法离去。”
「问题描述」
木牌下方有一行小字：“撞击所有机关墙”。
G-1500机器人每次可以朝着前方光速移动，质量、动能无穷大，可以选择自己在行进中停下来或者撞墙后停下来，移动时只有转向需要花费时间。
真是个诡异的迷宫，不过，小奇的眼前已经出现了迷宫的地图，它想尽早离开这里，请你帮助小奇制定一个行动方案，使得转向的次数最小，且在行动时撞击过所有的机关墙。
「输入格式」
第一行包含三个正整数n,m,K，表示迷宫的大小为n*m，迷宫中有K个机关墙。
接下来给出一个n*m的矩阵，.表示空地，#表示墙。
接下来K行，每行包含两个正整数a，b，表示第a行第b列的墙是机关墙。
最后一行包含两个正整数x，y，表示小奇的起始位置在第x行第y列，为了方便，认为起始时机器人方向奇怪，需要转向一次。
「输出格式」
输出一个正整数，表示小奇撞击完机关墙的最少转向次数，保证问题有解。
「样例输入」
4 6 3
……
.#..#.
.#…#
….#.
2 2
3 6
4 5
1 5
「样例输出」
6
「数据范围」
对于10%的数据，n，m <= 10，1 <= K <= 2。
对于40%的数据，n，m <= 50，1 <= K <= 10。
对于100%的数据，n，m <= 100，1 <= K <= 15。
「提示」
迷宫的最外层是墙，所有墙都是基岩，无法破坏。
移动方向只能是四个基本方向之一。
「题解」
对于40%的数据
状压墙的撞击情况，然后广搜
d[x][y][st][dir]表示到x行y列，撞击情况为st，朝向为dir的最小转向数
对于100%的数据
只有机关四周的四个石头是有意义的
只会在这些格子间之间走最短路（可以广搜来求），那么只剩下4T个格子，预处理每个格子到另一个格子撞机关的最少转向次数
最后状压dp即可
复杂度4T*4NM+2^T*4T*4T
由于我预处理写的是spfa，会多花些时间
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define p(x,y) (x-1)*4+y+1 #define inf 100000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char ch[105]; int bin[20]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int n,m,T,ed,bx,by; int x[25],y[25]; int f[65536][65],dis[65][65],d[105][105][5]; int qx[200005],qy[200005]; bool inq[105][105],rock[105][105]; void bfs(int bx,int by,int id) { if(rock[bx][by]||bx<1||by<1||bx>n||by>m)return; memset(d,127/3,sizeof(d)); qx[0]=bx;qy[0]=by;inq[bx][by]=1; for(int k=0;k<4;k++)d[bx][by][k]=0; int head=0,tail=1; while(head!=tail) { int x=qx[head],y=qy[head];head++; for(int k=0;k<4;k++) { int nowx=x+xx[k],nowy=y+yy[k]; if(rock[nowx][nowy]||nowx<1||nowy<1||nowx>n||nowy>m)continue; for(int b=0;b<4;b++) if(d[x][y][k]+(k!=b)<d[nowx][nowy][b]) { d[nowx][nowy][b]=d[x][y][k]+(k!=b); if(!inq[nowx][nowy]) { inq[nowx][nowy]=1; qx[tail]=nowx;qy[tail]=nowy; tail++; } } } inq[x][y]=0; } for(int i=1;i<=T;i++) for(int k=0;k<4;k++) { int t=inf,tx=x[i]+xx[k],ty=y[i]+yy[k]; for(int l=0;l<4;l++) t=min(t,d[tx][ty][l]+(tx+xx[l]!=x[i]||ty+yy[l]!=y[i])); dis[id][p(i,k)]=t; } } void dp() { for(int i=0;i<=ed;i++) for(int x=1;x<=4*T+1;x++) f[i][x]=inf; f[0][4*T+1]=0; for(int i=0;i<=ed;i++) for(int x=1;x<=4*T+1;x++) if(f[i][x]!=inf) for(int y=1;y<=4*T;y++) { int t=i|bin[(y-1)/4]; f[t][y]=min(f[t][y],f[i][x]+dis[x][y]+1); } int ans=inf; for(int x=1;x<=4*T;x++) ans=min(ans,f[ed][x]); printf("%d\n",ans); } int main() { freopen("maze.in","r",stdin); freopen("maze.out","w",stdout); bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; memset(dis,127/3,sizeof(dis)); n=read();m=read();T=read(); ed=bin[T]-1; for(int i=1;i<=n;i++) { scanf("%s",ch+1); for(int j=1;j<=m;j++) if(ch[j]=='#')rock[i][j]=-1; } for(int i=1;i<=T;i++) x[i]=read(),y[i]=read(); for(int i=1;i<=T;i++) for(int k=0;k<4;k++) bfs(x[i]+xx[k],y[i]+yy[k],p(i,k)); bx=read();by=read(); bfs(bx,by,4*T+1); dp(); return 0; } |
OI 课件=>
memset(dis,127/3,sizeof(dis));是什么意思啊？
将dis数组初始化为约7*10^8