英文题目巨烦

紧接着百练4115:鸣人和佐助和百练4116拯救行动的变形

题目连接：http://bailian.openjudge.cn/practice/4130/

#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<cctype>
#include<vector>
#include<limits.h>
#include<queue>using namespace std;#define N 110int INF=(int)1e10;int dir[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};char s[N][N];   //输入的字符串矩阵
int p[N][N];      //有蛇的位置会显示编号
int mark[N][N][10]; //拿过所有钥匙后的最小时间,11表示的可能就是那9把钥匙吧int n,m,ans;struct mmp
{int x,y,t,id,snake;   //坐标、时间、钥匙、和杀死的蛇bool operator<(const mmp &w) const{return t>w.t;}mmp(int xx,int yy,int tt,int ii,int ss):x(xx),y(yy),t(tt),id(ii),snake(ss) {}
};void bfs(int x,int y)
{int i,h;priority_queue<mmp>q;mmp next= {0,0,0,0,0};q.push(mmp(x,y,0,1,0));mark[x][y][1]=0;while(!q.empty()){mmp cur=q.top();q.pop();if(s[cur.x][cur.y]=='T'&&cur.id==m+1){ans=min(ans,cur.t);continue;}for(i=0; i<4; i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];next.t=cur.t+1;next.snake=cur.snake;next.id=cur.id;if(next.x<0||next.x>=n||next.y<0||next.y>=n||s[next.x][next.y]=='#')continue;if(s[next.x][next.y]=='S')  //判断是否杀死过蛇，只杀一次，杀一次时间+1{h=p[next.x][next.y];if((next.snake&(1<<h))==0){next.snake|=(1<<h);next.t++;}}if(next.id==s[next.x][next.y]-'0') //只有前几把钥匙拿到手后才能拿下一把钥匙{next.id++;}if(mark[next.x][next.y][next.id]>next.t) //拿过某一把钥匙后的最小时间{mark[next.x][next.y][next.id]=next.t;q.push(next);}}}
}int main()
{int i,j,k,l,a,b;while(scanf("%d%d",&n,&m)&&!(n==0&&m==0)){memset(p,0,sizeof(p));for(i=0,k=0; i<n; i++){scanf("%s",s[i]);for(j=0; j<n; j++){if(s[i][j]=='K'){a=i;b=j;}if(s[i][j]=='S'){p[i][j]=k++;}for(l=0; l<10; l++){mark[i][j][l]=INF;}}}ans=INF;bfs(a,b);if(ans==INF)printf("impossible\n");elseprintf("%d\n",ans);}return 0;
}