密室逃脱

题目描述

即使czhou没有派出最强篮球阵容,机房篮球队还是暴虐了校篮球队。为了不打击校篮球队信心,czhou决定改变训练后的活动。近来,江大掌门的徒弟徒孙们纷纷事业有成,回到母校为机房捐钱捐物。财大气粗的机房组收回了五层六层的所有教室。Czhou决定将六层的教室改造为智能密室逃脱活动室。

每天傍晚,神牛们可以依次逐个进入游玩。我们简单的将教室分割为n*n个房间,K是你初始所在房间,T是你最终逃脱的房间。如果你想要逃脱房间,你必须依次找到m把钥匙。我们假定你从一个房间进入另一个房间需要花费1的时间。当然某些房间有些特殊的问题(地图上S表示)需要回答才能通过,对于机智的众牛们来说,这些问题根本不是问题。我们假定众牛们花费1的时间解决问题。(主要是出题的人表述不清,导致众牛理解困难;当然问题只需要回答一次,下次再次进入房间不需要回答了)

输入格式

第一行两个数字n,m

接下来n*n描述地图

输出格式

需要最少时间逃脱密室。若无解输出impossible

数据范围:

0 < N <= 100, 0<=M<=9&#xFF0C;0<=s<=6

思路

解法一

s很小,可以枚举s的情况,枚举那个回答了,那个不回答,把答题用时加上,然后答过的是.,没答的是’#’,然后做一个bfs

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int s,sx,sy,tx,ty,ans=673720360;
int n,m;
char map[101][101];
int dis[101][101][10];
int atx[10],aty[10];
int turnx[4]={-1,0,1,0};
int turny[4]={0,1,0,-1};
void turn(int sta)
{
	int it=0;
	for(int i=1;i<=s;++i)
	{
		if(sta&(1<<(i-1)))
		{
			it+=1;
			map[atx[i]][aty[i]]='.';
		}
		else map[atx[i]][aty[i]]='#';
	}
	dis[sx][sy][0]=it;
}
struct node
{
	int x,y,key;
}num[10];
queue<node> q;
bool can(int x,int y,int key)
{
	if(dis[x][y][key]<673720360) return false;
	return true;
}
bool out(int x,int y)
{
	if(x>n||x<1) return true;
	if(y>n||y<1) return true;
	if(map[x][y]=='#') return true;
	return false;
}
int look(int i,int j,int key)
{
	if(map[i][j]>='0'&&map[i][j]<='9')
	{
		int it=map[i][j]-'0';
		if(it==key+1)
		{
			return it;
		}
	}
	return key;
}
void bfs()
{
	q.push((node){sx,sy,0});
	while(!q.empty())
	{
		node now=q.front();q.pop();
		for(int i=0;i<=3;++i)
		{
    		if(out(now.x+turnx[i],now.y+turny[i])) continue;
			int that=look(now.x+turnx[i],now.y+turny[i],now.key);
			if(can(now.x+turnx[i],now.y+turny[i],that))
			{
				dis[now.x+turnx[i]][now.y+turny[i]][that]=dis[now.x][now.y][now.key]+1;
				q.push((node){now.x+turnx[i],now.y+turny[i],that});
			}
		}
	}
}
int main()
{
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			cin>>map[i][j];
			if(map[i][j]=='S')
			{
				atx[++s]=i;aty[s]=j;
			}
			if(map[i][j]=='K') sx=i,sy=j;
			if(map[i][j]=='T') tx=i,ty=j;
		}
	}
	int to=(1<<s)-1;
	for(int i=0;i<=to;++i)
	{
		memset(dis,40,sizeof(dis));
		turn(i);
		bfs();
		ans=min(ans,dis[tx][ty][m]);
	}
	if(ans==673720360) printf("impossible");
	else printf("%d",ans);
	return 0;
}

解法二

状压spfa,一维表示收集到了第几个钥匙,然后对回答过的问题二进制压位,最后枚举各个答题状态下的重点(然而某台机子就是不给过,所以代码如此的…)

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
int N,M;
char MAP[110][110];
int INF=673720360,SN;
int WHAT[110][110],DIS[110][110][10][150],INIT[110][110][10][150],SX,SY,TX,TY;
int ANS=INF;
struct NODE
{
	int X,Y;
	int K;
	int VIS;
};
queue<NODE> Q;
bool CAN(int X,int Y,int XO,int YO)
{
	if(XO>N||XO<1) return false;
	if(YO>N||YO<1) return false;
	if(MAP[XO][YO]=='#') return false;
}
void SPFA()
{
	memset(DIS,40,sizeof(DIS));
	DIS[SX][SY][0][0]=0;
	Q.push((NODE){SX,SY,0,0});
	INIT[SX][SY][0][0]=1;
	while(!Q.empty())
	{
		NODE NOW=Q.front();
		Q.pop();
		int I=NOW.X,J=NOW.Y;
		INIT[I][J][NOW.K][NOW.VIS]=0;
		if(CAN(NOW.X,NOW.Y,NOW.X+1,NOW.Y))
		{
			int CSOT=1;
			NODE TO=NOW;
			TO.X++;
			if(MAP[I][J]>='0'&&MAP[I][J]<='9')
			{
				int THI=MAP[I][J]-'0';
				if(NOW.K==THI-1) TO.K++;
			}
			if(MAP[I][J]=='S'&&!(TO.VIS&(1<<WHAT[I][J]))) TO.VIS=TO.VIS|(1<<WHAT[I][J]),CSOT++;
			if(DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT<DIS[TO.X][TO.Y][TO.K][TO.VIS])
			{
				DIS[TO.X][TO.Y][TO.K][TO.VIS]=DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT;
				if(!INIT[TO.X][TO.Y][TO.K][TO.VIS])
				{
					INIT[TO.X][TO.Y][TO.K][TO.VIS]=1;
					Q.push(TO);
				}
			}
		}
		if(CAN(NOW.X,NOW.Y,NOW.X-1,NOW.Y))
		{
			int CSOT=1;
			NODE TO=NOW;
			TO.X--;
			if(MAP[I][J]>='0'&&MAP[I][J]<='9')
			{
				int THI=MAP[I][J]-'0';
				if(NOW.K==THI-1) TO.K++;
			}
			if(MAP[I][J]=='S'&&!(TO.VIS&(1<<WHAT[I][J]))) TO.VIS=TO.VIS|(1<<WHAT[I][J]),CSOT++;
			if(DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT<DIS[TO.X][TO.Y][TO.K][TO.VIS])
			{
				DIS[TO.X][TO.Y][TO.K][TO.VIS]=DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT;
				if(!INIT[TO.X][TO.Y][TO.K][TO.VIS])
				{
					INIT[TO.X][TO.Y][TO.K][TO.VIS]=1;
					Q.push(TO);
				}
			}
		}
		if(CAN(NOW.X,NOW.Y,NOW.X,NOW.Y+1))
		{
			int CSOT=1;
			NODE TO=NOW;
			TO.Y++;
			if(MAP[I][J]>='0'&&MAP[I][J]<='9')
			{
				int THI=MAP[I][J]-'0';
				if(NOW.K==THI-1) TO.K++;
			}
			if(MAP[I][J]=='S'&&!(TO.VIS&(1<<WHAT[I][J]))) TO.VIS=TO.VIS|(1<<WHAT[I][J]),CSOT++;
			if(DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT<DIS[TO.X][TO.Y][TO.K][TO.VIS])
			{
				DIS[TO.X][TO.Y][TO.K][TO.VIS]=DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT;
				if(!INIT[TO.X][TO.Y][TO.K][TO.VIS])
				{
					INIT[TO.X][TO.Y][TO.K][TO.VIS]=1;
					Q.push(TO);
				}
			}
		
		}
		if(CAN(NOW.X,NOW.Y,NOW.X,NOW.Y-1))
		{
			int CSOT=1;
			NODE TO=NOW;
			TO.Y--;
			if(MAP[I][J]>='0'&&MAP[I][J]<='9')
			{
				int THI=MAP[I][J]-'0';
				if(NOW.K==THI-1) TO.K++;
			}
			if(MAP[I][J]=='S'&&!(TO.VIS&(1<<WHAT[I][J]))) TO.VIS=TO.VIS|(1<<WHAT[I][J]),CSOT++;
			if(DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT<DIS[TO.X][TO.Y][TO.K][TO.VIS])
			{
				DIS[TO.X][TO.Y][TO.K][TO.VIS]=DIS[NOW.X][NOW.Y][NOW.K][NOW.VIS]+CSOT;
				if(!INIT[TO.X][TO.Y][TO.K][TO.VIS])
				{
					INIT[TO.X][TO.Y][TO.K][TO.VIS]=1;
					Q.push(TO);
				}
			}
		}
	}
}
int main()
{
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int I=1;I<=N;++I)
	{
		for(int J=1;J<=N;++J)
		{
			cin>>MAP[I][J];
		    if(MAP[I][J]=='K') SX=I,SY=J;
			if(MAP[I][J]=='T') TX=I,TY=J;
			if(MAP[I][J]=='S') WHAT[I][J]=++SN;
		}
	}
	SPFA();
	int ZZZ=(1<<(SN+1))-1;
	for(int I=0;I<=ZZZ;++I) ANS=min(ANS,DIS[TX][TY][M][I]);
	if(ANS==INF)
	{
		printf("impossible");
		return 0;
	}
	printf("%d",ANS);
	return 0;
}
(update the code to your comment plugin in comment-full.html)