即使czhou没有派出最强篮球阵容,机房篮球队还是暴虐了校篮球队。为了不打击校篮球队信心,czhou决定改变训练后的活动。近来,江大掌门的徒弟徒孙们纷纷事业有成,回到母校为机房捐钱捐物。财大气粗的机房组收回了五层六层的所有教室。Czhou决定将六层的教室改造为智能密室逃脱活动室。
每天傍晚,神牛们可以依次逐个进入游玩。我们简单的将教室分割为n*n个房间,K是你初始所在房间,T是你最终逃脱的房间。如果你想要逃脱房间,你必须依次找到m把钥匙。我们假定你从一个房间进入另一个房间需要花费1的时间。当然某些房间有些特殊的问题(地图上S表示)需要回答才能通过,对于机智的众牛们来说,这些问题根本不是问题。我们假定众牛们花费1的时间解决问题。(主要是出题的人表述不清,导致众牛理解困难;当然问题只需要回答一次,下次再次进入房间不需要回答了)
第一行两个数字n,m
接下来n*n描述地图
需要最少时间逃脱密室。若无解输出impossible
0 < N <= 100, 0<=M<=9,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;
}