點(diǎn)擊打開鏈接

題意：從K走到T，S為怪，走的時(shí)候就多花費(fèi)一秒，走到T時(shí)收集m把不同的鑰匙，但是規(guī)定收集n之前，必須1~n-1全部收集完畢，怪最多有5個(gè)

思路：怪最多就有5個(gè)，然后鑰匙是1~9把，我們每個(gè)點(diǎn)的狀態(tài)就不會(huì)很多，在BFS時(shí)每個(gè)點(diǎn)的狀態(tài)進(jìn)行標(biāo)記就行了，5個(gè)怪狀態(tài)壓縮著判斷，因?yàn)檫@個(gè)怪在第二次經(jīng)過(guò)的時(shí)候已經(jīng)死了，不用花費(fèi)時(shí)間去殺死它

////  main.cpp//  dfs-bfs搜索////  Created by liuzhe on 16/8/10.//  Copyright © 2016年 my_code. All rights reserved.//#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <queue>using namespace std;const int maxn=110;const int inf = 0x3f3f3f3f;int sx,sy,ex,ey,n,m,cnt;int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int vis[maxn][maxn][10][40];char str[maxn][maxn];struct edge{    int x,y,step,numkey,ss;};struct snake{    int x,y;}sna[10];int bfs(){    queue<edge>que;    edge c,ne;    memset(vis,0,sizeof(vis));    c.x = sx;    c.y = sy;    c.step = 0;    c.numkey = 0;    c.ss = 0;    vis[c.x][c.y][0][0] = 1;    que.push(c);    int ans = inf;    while(!que.empty())    {        c = que.front();        que.pop();        if(c.x==ex&&c.y==ey&&c.numkey==m)            ans = min(ans,c.step);        for(int i=0;i<4;i++)        {            int xx = c.x + dir[i][0];            int yy = c.y + dir[i][1];            if(xx<0||xx>n-1||yy<0||yy>n-1||str[xx][yy]=='#')                continue;            if(vis[xx][yy][c.numkey][c.ss])                continue;            ne.x = xx;            ne.y = yy;            ne.step = c.step+1;            ne.numkey = c.numkey;            ne.ss = c.ss;            if(str[xx][yy]>='1'&&str[xx][yy]<='9')//如果走到的位置是鑰匙就進(jìn)行判斷            {                int t = str[xx][yy] - '0';                if(ne.numkey==t-1)//鑰匙剛好是當(dāng)前鑰匙數(shù)＋1，就符合條件                {                    ne.numkey++;                    vis[ne.x][ne.y][ne.numkey][ne.ss] = 1;                    que.push(ne);                }                else//不符合條件直接壓進(jìn)隊(duì)列                {                    vis[ne.x][ne.y][ne.numkey][ne.ss]  =1;                    que.push(ne);                }            }            else                if(str[xx][yy]=='S')//meet snake,then judge                {                    for(int i=0;i<cnt;i++)                    {                        if(xx==sna[i].x&&yy==sna[i].y)                        {                            if((ne.ss>>i)&1)//說(shuō)明這個(gè)已經(jīng)死掉了                            {                                vis[ne.x][ne.y][ne.numkey][ne.ss] = 1;                                que.push(ne);                            }                            else//時(shí)間加一，狀態(tài)更新                            {                                ne.step++;                                ne.ss+=(1<<i);                                vis[ne.x][ne.y][ne.numkey][ne.ss] = 1;                                que.push(ne);                            }                            break;                        }                    }                }            else            {                vis[ne.x][ne.y][ne.numkey][ne.ss] = 1;                que.push(ne);            }        }    }    return ans;}int main(){    while(scanf("%d%d",&n,&m)!=-1)    {        if(n==0&&m==0)            break;        cnt = 0;        for(int i=0;i<n;i++)            scanf("%s",str[i]);        for(int i=0;i<n;i++)        {            for(int j=0;j<n;j++)            {                if(str[i][j]=='K')                {                    sx = i;                    sy = j;                }                if(str[i][j]=='T')                {                    ex = i;                    ey = j;                }                if(str[i][j]=='S')                {                    sna[cnt].x = i;                    sna[cnt].y = j;                    cnt++;//記錄怪的位置和數(shù)量                }            }        }        int ans = bfs();        if(ans == inf)            puts("impossible");        else            PRintf("%d/n",ans);    }    return 0;}