HDU 5025 Saving Tang Monk(状压搜索)

钥匙是必须有序，蛇是不要求有序的。所以一个需要状压一个不用

因为时间计算和步数计算不同。所以要遍历整个空间，或者使用优先队列。优先时间短的。

风格就这样了.

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define inf 0x3f3f3f3f #define maxn 110 using namespace std; int N,M,T; int D[maxn][maxn][10][32]; char G[maxn][maxn]; int dr[]={-1,0,1,0},dc[]={0,1,0,-1}; int sr[5],sc[5],scnt; struct P { int r,c,s,k; }s,e,use,in; int bfs() { queue
       
         q; q.push(s);int res=inf; while(q.size()){ use=q.front();q.pop(); if(use.k==M && use.r==e.r && use.c==e.c) res=min(res,D[use.r][use.c][use.k][use.s]); for(int i=0;i<4;i++){ int t=1; in=use; in.r=use.r+dr[i]; in.c=use.c+dc[i]; if(D[in.r][in.c][in.k][in.s]!=inf || G[in.r][in.c]=='#' || in.r<1 || in.r>N || in.c<1 || in.c>N) continue; if(G[in.r][in.c]=='S'){ for(int j=0;j
        
         ='1' && G[in.r][in.c]-'0'==in.k+1) in.k++; D[in.r][in.c][in.k][in.s]=D[use.r][use.c][use.k][use.s]+t; q.push(in); } } return res==inf?-1:res; } int main() { while(~scanf("%d%d",&N,&M) && (N+M)){ scnt=0; for(int i=1;i<=N;i++){ getchar(); for(int j=1;j<=N;j++){ scanf("%c",G[i]+j); if(G[i][j]=='K') s.r=i,s.c=j,s.k=0,s.s=0; else if(G[i][j]=='T') e.r=i,e.c=j,e.k=0,e.s=0; else if(G[i][j]=='S') sr[scnt]=i,sc[scnt++]=j; } } memset(D,0x3f,sizeof(D)); D[s.r][s.c][0][0]=0; int ans=bfs(); if(ans==-1) cout<<"impossible"<