http://acm.hdu.edu.cn/showproblem.php?pid=5025

N*N矩阵 M个钥匙

K起点，T终点，S点需多花费1点且只需要一次，1-9表示9把钥匙，只有当前有I号钥匙才能拿I+1号钥匙，可以不拿钥匙只从上面走过

BFS+优先队列。蛇最多只有5条，状压即可。

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

typedef pair<int,int> pii;

const int INF = 2000000007;

map <pii,int> hash;

int n,m,sx,sy,tx,ty,cnt_snake;

char s[105][105];

int dx[] = {1,-1,0,0},

    dy[] = {0,0,1,-1};

int _key[105][105][10];

int anss;

bool in(int x,int y)

{

    return 0 <= x && x < n && 0 <= y && y < n;

}

struct node{

    int x,y,key,snak,t;

    bool operator < (const node b )const

    {

        return t > b.t;

    }

};

//class cmp

//{

//public:

//    cmp(){};

//    bool operator ()( const node a, const node b )

//    {

//        if(a.x!=b.x)

//            return a.x<b.x;

//        if(a.y!=b.y)

//            return a.y<b.y;

//        if(a.key != b.key)

//            return a.key < b.key;

//        if(a.snak != b.snak)

//            return a.snak < b.snak;

//        return false;

//    }

//};

void bfs()

{

    //map <node,int,cmp> vis;

    priority_queue<node> q;

    q.push((node){sx,sy,0,0,0});

    while(!q.empty()){

        node now = q.top(),to;

        int x = now.x,y = now.y,key = now.key,snak = now.snak,t = now.t;

        q.pop();

        //vis[now] = 0;

        if(s[x][y] == 'T'  && key == m){//cout<<snak;

            anss = min(anss,now.t);

            return ;

        }

        for(int i = 0;i < 4;++i){

            int mx = x+dx[i],my = y + dy[i];

            if(!in(mx,my) || s[mx][my] == '#')continue;

            if(s[mx][my] == 'S'){

                pii tt = make_pair(mx,my);

                if(snak & (1<<(hash[tt] - 1))){

                    to = (node){mx,my,key,snak,t+1};

                }

                else{

                    int tosnak = snak | (1<<(hash[tt] - 1));

                    to = (node){mx,my,key,tosnak,t+2};

                }

            }

            else if(s[mx][my] - '0' == key + 1){

                to = (node){mx,my,key+1,snak,t+1};

            }

            else{

                to = (node){mx,my,key,snak,t+1};

            }

            if(to.t < _key[mx][my][to.key]){

                q.push(to);

                _key[mx][my][to.key] = to.t;

            }

        }

    }

}

int main(){

    while(~scanf("%d%d",&n,&m),n|m){

        hash.clear();

        cnt_snake = 0;

        for(int i = 0;i < n;++i){

            scanf("%s",s[i]);

            for(int j = 0;j < n;++j){

                if(s[i][j] == 'K')

                    sx = i,sy = j;

                else if(s[i][j] == 'T')

                    tx = i,ty = j;

                else if(s[i][j] == 'S'){

                    pii tt = make_pair(i,j);

                    hash[tt] = ++cnt_snake;

                }

                for(int k = 0;k <= m;++k)

                    _key[i][j][k] = INF;

            }

        }

        //int mm = 1<<cnt_snake;

        //memset(dp,0x3f,sizeof(dp));

        _key[sx][sy][0] = 0;

        anss = INF;

        bfs();

        if(anss >= INF)

            puts("impossible");

        else

            printf("%d\n",anss);

     }

     return 0;

 }