Saving Tang Monk

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 941    Accepted Submission(s): 352

3 1
K.S
##1
1#T
3 1
K#T
.S#
1#.
3 2
K#T
.S.
21.
0 0

5
impossible
8

解题思路：

题意为一个地图，‘K‘代表孙悟空的位置，也就是起点，‘T‘代表唐僧的位置，数字‘1’‘2’等代表第几种钥匙，‘S‘代表蛇，‘#‘不能走，题意的目的就是孙悟空去救唐僧，要求前提必须是拿到给定的m种钥匙，才能去救唐僧，除了‘#‘的位置，其他位置都可以走（如果到达了唐僧的位置，但没拿到给定的m种钥匙，任务也没法完成，必须得拿到m钟钥匙)，到达‘S‘位置，要多花一分钟杀死蛇，其他位置走一步花一分钟，问最少花多少分钟才能解救唐僧，如果不能，输出impossible.

 题意真的不好理解：要想解救唐僧，只有唯一的方法，就是取得所有种类的钥匙，然后到达唐僧的位置，去解救。孙悟空位置和唐僧位置可以走多次。

还有蛇的状态也需要特别注意，第一次杀死蛇，第二次再到达该位置时，就不用再杀蛇了，给蛇编号，杀了为1，不杀为0，状态压缩。

定义 f[i][j][k][state] ,为坐标位置走到坐标 i, j ，时已经取得了第k种钥匙，当前蛇的状态为state。 进行广度优先搜索。

参考：http://www.cnblogs.com/whatbeg/p/3983522.html

代码：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#include <queue>
using namespace std;

const int inf=0x3f3f3f3f;
int n,m;
char mp[102][102];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int f[102][102][12][35];//f[i][j][k][state]为坐标i,j位置处已经拿到第k种钥匙且杀死蛇的状态为state时的最小步数
int sx,sy;//开始位置
int scnt;//蛇的数量
int ans;
map<pair<int,int>,int>snake;//给某一位置上的蛇编号,从1开始

struct Node
{
    int x,y,k,s,step;
};
queue<Node>q;


void init()
{
    memset(f,inf,sizeof(f));
    snake.clear();
    scnt=0;
    ans=inf;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        cin>>mp[i][j];
        if(mp[i][j]=='K')
            sx=i,sy=j,mp[i][j]='.';//别忘了mp[i][j]='.'这一句，起始位置也可以重复多次走
        else if(mp[i][j]=='S')
            snake[make_pair(i,j)]=++scnt;//编号
    }
    f[sx][sy][0][0]=0;
}


bool ok(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=n&&mp[x][y]!='#')
        return true;
    return false;
}


void bfs(Node st)
{
    if(!q.empty())
        q.pop();
    q.push(st);
    while(!q.empty())
    {
        Node cur=q.front();
        q.pop();
        Node next;//下一步的状态节点
        for(int i=0;i<4;i++)
        {
            int newx=cur.x+dx[i];
            int newy=cur.y+dy[i];
            if(!ok(newx,newy))
                continue;
            next.x=newx,next.y=newy;
            if(mp[newx][newy]=='S')
            {
                int th=snake[make_pair(newx,newy)];
                if(cur.s&(1<<(th-1)))//已经杀过该条蛇
                {
                    next.s=cur.s;
                    next.k=cur.k;
                    next.step=cur.step+1;
                }
                else
                {
                    next.s=(cur.s|(1<<(th-1)));
                    next.k=cur.k;
                    next.step=cur.step+2;
                }
                if(next.step<f[newx][newy][next.k][next.s])
                {
                    f[newx][newy][next.k][next.s]=next.step;
                    q.push(next);
                }
            }
            else if(mp[newx][newy]>='1'&&mp[newx][newy]<='9')
            {
                int th=mp[newx][newy]-'0';
                if(th==cur.k+1)//当前这个钥匙正好是想要的，已有钥匙加1
                    next.k=cur.k+1;
                else
                    next.k=cur.k;
                next.s=cur.s;
                next.step=cur.step+1;
                if(next.step<f[newx][newy][next.k][next.s])
                {
                    f[newx][newy][next.k][next.s]=next.step;
                    q.push(next);
                }
            }
            else if(mp[newx][newy]=='.')
            {
                next.k=cur.k;
                next.s=cur.s;
                next.step=cur.step+1;
                if(next.step<f[newx][newy][next.k][next.s])
                {
                    f[newx][newy][next.k][next.s]=next.step;
                    q.push(next);
                }
            }
            else if(mp[newx][newy]=='T')
            {
                next.k=cur.k;
                next.s=cur.s;
                next.step=cur.step+1;
                if(next.step<f[newx][newy][next.k][next.s])
                    f[newx][newy][next.k][next.s]=next.step;
                if(next.k==m)//该状态下不再向下扩展
                    ans=min(f[newx][newy][next.k][next.s],ans);
                else
                    q.push(next);
            }
        }
    }
}

int main()
{
    while(cin>>n>>m&&(n||m))
    {
        init();
        Node temp;
        temp.x=sx,temp.y=sy,temp.k=0,temp.s=0,temp.step=0;
        bfs(temp);
        if(ans==inf)
            cout<<"impossible"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

[ACM] HDU 5025 Saving Tang Monk （状态压缩，BFS）

原文：http://blog.csdn.net/sr_19930829/article/details/40352719