「NOIP模拟赛」密室逃脱
即使czhou没有派出最强篮球阵容，机房篮球队还是暴虐了校篮球队。为了不打击校篮球队信心，czhou决定改变训练后的活动。近来，江大掌门的徒弟徒孙们纷纷事业有成，回到母校为机房捐钱捐物。财大气粗的机房组收回了五层六层的所有教室。Czhou决定将六层的教室改造为智能密室逃脱活动室。
每天傍晚，神牛们可以依次逐个进入游玩。我们简单的将教室分割为n*n个房间，K是你初始所在房间，T是你最终逃脱的房间。如果你想要逃脱房间，你必须依次找到m把钥匙。我们假定你从一个房间进入另一个房间需要花费1的时间。当然某些房间有些特殊的问题(地图上S表示)需要回答才能通过，对于机智的众牛们来说，这些问题根本不是问题。我们假定众牛们花费1的时间解决问题。（主要是出题的人表述不清，导致众牛理解困难；当然问题只需要回答一次，下次再次进入房间不需要y回答了）
Input：maze.in
第一行两个数字n，m
接下来n*n描述地图
Output: maze.out
需要最少步数逃脱密室。若无解输出impossible
Sample1.in:
3 1
K.S
##1
1#T
Sample1.outvb
5
Sample2.in
3 1
K#T
.S#
1#.
Sample2.out
Impossible
Sample3.in
3 2
K#T
.S.
21.
Sample3.out
8
样例3说明：
要先取钥匙1，再取钥匙2。地图上可能有多个同一种钥匙，#为墙壁即不可走.
数据范围：
0 < N <= 100, 0<=M<=9，S的个数<=5
题解
这题由于S较小，2^5枚举S的方案。。。然后直接bfs即可 即当枚举走那些S之后，原图的所有节点权都变成了1，至于按顺序取钥匙可以做分层图，f[i][j]为第i个点取到钥匙j的路径长
|
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 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #define inf 1000000000 using namespace std; 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; } int ans=inf; int n,m,cnt,x1,x2,y1,y2; char a[105][105]; int f[105][105][10]; int qx[100005],qy[100005],qm[100005]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int x[15],y[15]; void bfs() { memset(f,-1,sizeof(f)); qx[0]=x1;qy[0]=y1; int head=0,tail=1; f[x1][y1][0]=0; while(head!=tail) { int x=qx[head],y=qy[head],t=qm[head];head++; for(int i=0;i<4;i++) { int nowx=x+xx[i],nowy=y+yy[i],nowm=t; if(nowx<1||nowy<1||nowx>n||nowy>n)continue; if(a[nowx][nowy]=='#'||f[nowx][nowy][nowm]!=-1)continue; if(nowm+1==a[nowx][nowy]-'0')nowm++; f[nowx][nowy][nowm]=f[x][y][t]+1; qx[tail]=nowx;qy[tail]=nowy;qm[tail]=nowm;tail++; } } } void dfs(int now,int k) { if(now==cnt+1) { bfs(); if(f[x2][y2][m]!=-1) ans=min(ans,k+f[x2][y2][m]); return; } a[x[now]][y[now]]='.'; dfs(now+1,k+1); a[x[now]][y[now]]='#'; dfs(now+1,k); } int main() { //freopen("maze.in","r",stdin); //freopen("maze.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++) { scanf("%s",a[i]+1); for(int j=1;j<=n;j++) if(a[i][j]=='K') { x1=i;y1=j; } else if(a[i][j]=='T') { x2=i;y2=j; } else if(a[i][j]=='S') { cnt++; x[cnt]=i;y[cnt]=j; } } dfs(1,0); if(ans==inf)puts("impossible"); else printf("%d\n",ans); return 0; } |
Subscribe
计数器 9774555
OI 课件=>
OI 课件=>