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

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

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;
}``````