#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <cmath>
using namespace std;
#define MAXN 110
int vis[MAXN][MAXN][1<<6][15];
char map1[MAXN][MAXN];
struct point{
int x,y,step,stats,statk;
bool operator<(point y)const {
return step>y.step;
}
}st,et;
struct snack{
int x,y;
}S[10];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n,m,scnt,k;
int bfs(){
queue <point> q;
point now,next;
q.push(st);
memset(vis,0,sizeof(vis));
vis[st.x][st.y][st.stats][st.statk]=1;
while(!q.empty()){
now=q.front();
q.pop();
if(now.x==et.x&&now.y==et.y&&now.statk==k){
return now.step;
}
if(map1[now.x][now.y]=='S'){
int flag=0;
for(int i=1;i<=scnt;i++){
if(now.x==S[i].x&&now.y==S[i].y){
flag=i;
break;
}
}
if((now.stats>>(flag-1))&1);
else {
now.stats|=(1<<(flag-1));
now.step++;
q.push(now);
continue;
}
}
for(int i=0;i<4;i++){
next.x=now.x+dx[i];
next.y=now.y+dy[i];
next.step=now.step+1;
next.statk=now.statk;
next.stats=now.stats;
if(next.x<1||next.x>n||next.y<1||next.y>n)continue;
if(map1[next.x][next.y]=='#')continue;
if(map1[next.x][next.y]-'0'==now.statk+1){
next.statk=now.statk+1;
}
if(vis[next.x][next.y][next.stats][next.statk])continue;
vis[next.x][next.y][next.stats][next.statk]=1;
q.push(next);
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m)&&(n||m)){
k=m;
m=n;
scnt=0;
int flag1=0,flag2=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf(" %c",&map1[i][j]);
if(map1[i][j]=='S'){
scnt++;
S[scnt].x=i;
S[scnt].y=j;
}
if(map1[i][j]=='K'){
st.x=i;st.y=j;
st.step=0;st.stats=0;st.statk=0;
flag1=1;
}
if(map1[i][j]=='T'){
et.x=i;et.y=j;
flag2=1;
}
}
if(!flag1||!flag2){
puts("impossible");
continue;
}
int ff=bfs();
if(ff==-1)puts("impossible");
else printf("%d\n",ff);
}
return 0;
}
法二：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <cmath>
using namespace std;
#define MAXN 110
int vis[MAXN][MAXN][1<<6][15];
char map1[MAXN][MAXN];
struct point{
int x,y,step,stats,statk;
bool operator<(point y)const {
return step>y.step;
}
}st,et;
struct snack{
int x,y;
}S[10];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n,m,scnt,k;
int bfs(){
priority_queue <point> q;
point now,next;
q.push(st);
memset(vis,0,sizeof(vis));
vis[st.x][st.y][st.stats][st.statk]=1;
while(!q.empty()){
now=q.top();
q.pop();
if(now.x==et.x&&now.y==et.y&&now.statk==k){
return now.step;
}
for(int i=0;i<4;i++){
next.x=now.x+dx[i];
next.y=now.y+dy[i];
next.step=now.step+1;
next.statk=now.statk;
next.stats=now.stats;
if(next.x<1||next.x>n||next.y<1||next.y>n)continue;
if(map1[next.x][next.y]=='#')continue;
if(map1[next.x][next.y]=='S'){
int flag=0;
for(int i=1;i<=scnt;i++){
if(next.x==S[i].x&&next.y==S[i].y){
flag=i;
break;
}
}
if((next.stats>>(flag-1))&1);
else {
next.stats|=(1<<(flag-1));
next.step++;
}
}
if(map1[next.x][next.y]-'0'==now.statk+1){
next.statk=now.statk+1;
}
if(vis[next.x][next.y][next.stats][next.statk])continue;
vis[next.x][next.y][next.stats][next.statk]=1;
q.push(next);
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m)&&(n||m)){
k=m;
m=n;
scnt=0;
int flag1=0,flag2=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf(" %c",&map1[i][j]);
if(map1[i][j]=='S'){
scnt++;
S[scnt].x=i;
S[scnt].y=j;
}
if(map1[i][j]=='K'){
st.x=i;st.y=j;
st.step=0;st.stats=0;st.statk=0;
flag1=1;
}
if(map1[i][j]=='T'){
et.x=i;et.y=j;
flag2=1;
}
}
if(!flag1||!flag2){
puts("impossible");
continue;
}
int ff=bfs();
if(ff==-1)puts("impossible");
else printf("%d\n",ff);
}
return 0;
}
|
