Tempter of the Bone II

4 4
SX..
XX..
....
1..D
4 4
S.X1
....
..XX
..XD
0 0

-1
9

题意：要求从 S 点走到 D 点的最短时间，‘1’~‘9’：表示当前位置有炸药数量，X：表示墙。" . "：表示可走的路。墙可以用一包炸药炸通，需花一个单位时间。

分析：从S到D，所经过的每个位置得到的炸药数量可能不等，就算得到的炸药数量相等，但每个到达当前位置时的地图的状态不同。所以我们不仅必须判断在每个位置得到的炸药数是否存在过，而且还要判断得到的这些炸药数在相同情况下不同地图的状态。

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;

struct State
{
    short state[8];//地图每行压缩的状态，
};
struct node
{
    int x,y; //当前走到的位置
    int time,explosiveNumb; //走过的时间，得到的炸药数量
    State s;  //走过后的地图状态
    friend bool operator<(const node &a,const node &b) //优先队列以时间最小的顺序取
    {
        return a.time>b.time;
    }
};

int n,m;
char map[10][10];
vector<State>vist[8][8][560]; //走到地图每个位置得到不同炸药数量的地图状态有没有存在过

void init()
{
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        for(int k=0; k<559; k++)
        vist[i][j][k].clear();
}
bool judge(int x,int y,int numb,short state[])
{
    int length=vist[x][y][numb].size();
    for(int i = 0; i < length ;i++)
    {
        int j;
        for(j = 0; j<n ; j++)
            if(vist[x][y][numb][i].state[j]!=state[j])
            break;
        if(j==n) //当前将要走的state[]地图状态，不必再加入队列（即己经存在过）
            return false;
    }
    //当前将要走的地图状态没存在过，需加入队列
    return true;
}
int bfs(int sx,int sy)
{
    int dir[4][2]={0,1,0,-1,1,0,-1,0};
    priority_queue<node>q;
    node p,tp;

    init();
    p.x=sx;
    p.y=sy;
    p.time=0;
    p.explosiveNumb=0;
    for(int i=0;i<n;i++)
    {
        p.s.state[i]=0;
        //压缩每行地图的状态，位置是 1 表示不存在任何东西
        for(int j=0;j<m;j++)
            if(map[i][j]=='.')
        p.s.state[i]|=(1<<j);
    }
    
    vist[sx][sy][0].push_back(p.s);
    q.push(p);
    while(!q.empty())
    {
        p=q.top();
        q.pop();
        for(int e=0;e<4;e++)
        {
            tp=p;
            tp.x+=dir[e][0];
            tp.y+=dir[e][1];
            tp.time++;
            if(tp.x>=0&&tp.x<n&&tp.y>=0&&tp.y<m)
            {
                if(!(tp.s.state[tp.x]&(1<<tp.y))&&map[tp.x][tp.y]=='X'&&!tp.explosiveNumb) //表示将要走的位置是现在还没炸的墙，并且身上没有炸药
                    continue ;
                if(!(tp.s.state[tp.x]&(1<<tp.y))&&map[tp.x][tp.y]>'0'&&map[tp.x][tp.y]<='9') //表示将要走的位置是没有取走的炸药
                {
                    tp.explosiveNumb+=map[tp.x][tp.y]-'0';
                    tp.s.state[tp.x]|=1<<tp.y; //取走后变成 "."
                }
                else if(!(tp.s.state[tp.x]&(1<<tp.y))&&map[tp.x][tp.y]=='X'&&tp.explosiveNumb)  //表示将要走的位置是现在还没炸的墙，身上有炸药
                {
                    tp.explosiveNumb--;
                    tp.s.state[tp.x]|=1<<tp.y; //炸完后变成 "."
                    tp.time++;
                }
                else if(map[tp.x][tp.y]=='D')
                    return tp.time;
                if(judge(tp.x,tp.y,tp.explosiveNumb,tp.s.state)) //判断走到当前位置的炸药数量与地图状态是否没有存在过？为真没存在过，否则为存在过
                vist[tp.x][tp.y][tp.explosiveNumb].push_back(tp.s),q.push(tp);
            }
        }
    }
    return -1;
}
int main()
{
    int sx,sy;
    while(scanf("%d%d",&n,&m)>0)
    {
        if(n==0&&m==0)
            break;
        for(int i=0;i<n;i++)
            scanf("%s",map[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            if(map[i][j]=='S')
            sx=i,sy=j;
        printf("%d\n",bfs(sx,sy));
    }
}

HDU2128Tempter of the Bone II(bfs+状态压缩)

原文：http://blog.csdn.net/u010372095/article/details/41595083