2014 网选 广州赛区 hdu 5025 Saving Tang Monk（bfs+四维数组记录状态）

/*
    这是我做过的一道新类型的搜索题！从来没想过用四维数组记录状态！
    以前做过的都是用二维的！自己的四维还是太狭隘了.....
    
    题意：悟空救师傅 ！ 在救师父之前要先把所有的钥匙找到！
    每种钥匙有 k 种， 每一种有多个！ 只要求找到每一种的其中一个就可以！
    找钥匙的顺序按照 第1种， 第2种， 第3种 ....第k种！ 
    找钥匙的时间是一步， 走到相邻空地的时间是一步， 打蛇的时间就是两步！
    求找到师傅的最少步数！ 
    
    这里说一下 state[N][N][10][35]表示的含义： ->state[x][y][i][j] 
    前两维就不用说了，就是地图上的坐标， 第三维表示的是当前找到第几把钥匙
    第四维表示的沿着一条路径走到 （x, y）找到 第 i 把钥匙打掉了哪几条蛇！
    将 j 拆分成 二进制， 从右往左数， 如果第 k 为是1， 表示第 k 条 蛇杀掉了！ 
*/ 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

#define N 105
using namespace std;

char mp[105][105];

bool state[N][N][10][35];

int bx, by;

struct node{
    int x, y;
    int numk, snk;
    int step;
    node(){}
    
    node(int x, int y, int numk, int snk, int step){
        this->x = x;
        this->y = y;
        this->numk = numk;
        this->snk = snk;
        this->step = step;
    }
};

int n, m;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
bool operator < (node a, node b) {
    return a.step > b.step;
}

priority_queue<node>q;

bool bfs(){
    while(!q.empty()) q.pop();
    memset(state, false, sizeof(state));
    q.push( node(bx, by, 0, 0, 0) );
    state[bx][by][0][0] = true;
    while( !q.empty() ) {
        node cur = q.top();
        q.pop();
        for(int i=0; i<4; ++i){
            int x = cur.x + dir[i][0];
            int y = cur.y + dir[i][1];
            if(x<1 || x>n || y<1 || y>n || mp[x][y]=='#') continue;
            int numk = cur.numk, snk = cur.snk, step = cur.step;
            if(mp[x][y] == '.')
                step += 1;
            else if( mp[x][y] >= '1' && mp[x][y] <= '9'){
                if( numk + 1 == mp[x][y] - '0' )
                    numk += 1;
                step += 1;
            }
            else if( mp[x][y] >= 'A' && mp[x][y] <= 'E' ){//这一步是关键 
                int cnt = mp[x][y] - 'A' + 1; 
                if(    (1 << (cnt-1) ) & snk ) step += 1;//如果这一条蛇已经被打过了，也就是一条路又折回到这一个点 
                else{//在这一条路上，这条蛇没有被打过，那就将它打掉，并标记这条蛇打过了！ 
                    step += 2;
                    snk ^= ( 1 << (cnt-1) );
                }
            }
            else if( mp[x][y] == 'T' && numk == m ){
                printf("%d\n", step + 1);
                return true;
            }
            else step += 1;
            
            if( state[x][y][numk][snk] )  continue;
            state[x][y][numk][snk] = true;
            q.push( node(x, y, numk, snk, step) );
        }
    }
    return false;
}

int main(){
    while( scanf("%d%d", &n, &m) && (n ||m) ) {
        int cntS = 0;
        for(int i = 1; i <= n; ++ i){
            scanf("%s", mp[i] + 1);
            for(int j = 1; j <=n; ++ j)
                if(mp[i][j] == 'K'){
                    bx = i;
                    by = j;
                }
                else if(mp[i][j] == 'S')
                    mp[i][j] = 'A' + cntS++;
        }
        if( !bfs() )  printf("impossible\n");
    }
    return 0;
}