[2014-11-05 模拟赛] 密室逃脱 (maze.*)

2014-11-05
竞赛题解 / 搜索
BFSNOIP模拟赛

描述 Description

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

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

输入格式 InputFormat

第一行两个数字 n，m
接下来 n*n 描述地图

输出格式 OutputFormat

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

样例输入 SampleInput

5 4
S#K#.
3SS.#
..4T2
S..S.
#1#..

样例输出 SampleOutput

20

NOIP 模拟赛

代码 Code

分层图广搜。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int inf=0x7fffffff/27.11;
const int dx[5]={0,0,0,-1,1};
const int dy[5]={0,1,-1,0,0};
int i,j,t,n,m,l,r,k,z,y,x;
int sx,sy,tx,ty;
char a[105][105];
vector < pair<int,int> > v;
struct point
{
    int x,y,z;
};
deque <point> q;
int f[105][105][10];
int ans;
inline void bfs(int s)
{
    int i,j,t;
    int nx,ny,nz;
    point p;
    for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (k=0;k<=m;k++) f[i][j][k]=inf;
    while (!q.empty()) q.pop_front();
    f[sx][sy][0]=0;q.push_back((point){sx,sy,0});
    while (!q.empty())
    {
        p=q.front();q.pop_front();
        for (i=1;i<=4;i++)
        {
            nx=p.x+dx[i];ny=p.y+dy[i];nz=p.z;
            if (nx<=0 || nx>n || ny<=0 || ny>n || a[nx][ny]=='#') continue;
            if (a[nx][ny]-'0'-nz==1)
            {
                if (f[nx][ny][nz+1]>f[p.x][p.y][p.z]+1)
                {
                    f[nx][ny][nz+1]=f[p.x][p.y][p.z]+1;
                    q.push_back((point){nx,ny,nz+1});
                }
            }
            else
            {
                if (f[nx][ny][nz]>f[p.x][p.y][p.z]+1)
                {
                    f[nx][ny][nz]=f[p.x][p.y][p.z]+1;
                    q.push_back((point){nx,ny,nz});
                }
            }
        }
    }
    ans=min(ans,f[tx][ty][m]+s);
}
void dfs(int s,int x)
{
    if (s==v.size())
    {
        bfs(x);
        return ;
    }
    a[v[s].first][v[s].second]='#';
    dfs(s+1,x);
    a[v[s].first][v[s].second]='.';
    dfs(s+1,x+1);
}
int main()
{
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%s",a[i]+1);
    for (i=1;i<=n;i++) for (j=1;j<=n;j++)
    {
        if (a[i][j]=='S') v.push_back(make_pair(i,j));
        if (a[i][j]=='K')
        {
            sx=i;sy=j;
            a[i][j]='.';
        }
        if (a[i][j]=='T')
        {
            tx=i;ty=j;
            a[i][j]='.';
        }
    }
    ans=inf;
    dfs(0,0);
    if (ans==inf) printf("impossible\n");
    else printf("%d\n",ans);
    return 0;
}