HDU 5025 Saving Tang Monk.

【题意】求悟空到师傅的最短距离，这中途会有一些门，悟空必须依次拿到钥匙，打开所有的门，中途遇到妖怪就会多停留1s，求悟空救出师傅的最短时间！

【解题思路】我的第一道dfs+状压！其中dp[x][y][k][s]中,x,y代表位置，k代表拿到了k把钥匙，s代表状态。

【AC代码】

#include <stdio.h>
#include <queue>
#include <string.h>
#include <assert.h>
#include <iostream>
using namespace std;
const int maxn = 102;
const int inf = 0x3f3f3f3f;
struct node{
   int x,y,k,s,d;
   node(){}
   node(int x,int y,int k,int s,int d):x(x),y(y),k(k),s(s),d(d){}
};
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
int dp[maxn][maxn][10][32];
char maze[maxn][maxn];
int n,m,sx,sy,cnt;
int bfs(int sx,int sy)
{
    queue<node>que;
    int ans = inf;
    que.push(node(sx,sy,0,0,0));
    while(!que.empty())
    {
        node cur = que.front();
        que.pop();
        int x=cur.x,y=cur.y,k=cur.k,s=cur.s;
        if(k==m&&maze[x][y]=='T')
        {
            ans = min(ans,cur.d);
        }
        if(dp[x][y][k][s]!=-1)continue;
        dp[x][y][k][s]=cur.d;
        for(int i=0;i<4;i++)
        {
            int dx=x+dir[i][0];
            int dy=y+dir[i][1];
            int st = maze[dx][dy]-'A';
            if(st>=0&&st<cnt)//杀蛇
            {
                if(s&(1<<st)) que.push(node(dx,dy,k,s,cur.d+1));
                else          que.push(node(dx,dy,k,s^(1<<st),cur.d+2));
            }
            else//拿钥匙
            {
                if(maze[dx][dy]=='1'+k)
                {
                    que.push(node(dx,dy,k+1,s,cur.d+1));
                }
                else if((maze[dx][dy]>='1'&&maze[dx][dy]<'1'+m)||(maze[dx][dy]=='.'||maze[dx][dy]=='K'||maze[dx][dy]=='T'))
                {
                    que.push(node(dx,dy,k,s,cur.d+1));
                }
            }
        }
    }
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        cnt = 0;
        if(n==0&&m==0)return 0;
        memset(dp,-1,sizeof(dp));
        memset(maze,0,sizeof(maze));
        for(int i=1; i<=n; i++)
        {
            scanf("%s",maze[i]+1);
            for(int j=1; j<=n; j++)
            {
                if(maze[i][j]=='S')
                {
                    maze[i][j] = 'A'+cnt;
                    cnt++;
                }
                if(maze[i][j]=='K')
                {
                    sx=i,sy=j;
                }
            }
        }
//        for(int i=1; i<=n; i++)
//        {
//            for(int j=1; j<=n; j++)
//            {
//                printf("%c",maze[i][j]);
//            }
//            printf("\n");
//        }
        int ans = bfs(sx,sy);
        if(ans==inf)
        {
            puts("impossible");
        }
        else
        {
            printf("%d\n",ans);
        }
    }
    return 0;
}