学步园

这个题是比较难的宽搜题，之所以难是因为他比以前的这个类似题目多了一个炸弹，增加了题目难度。不过杭电的数据好像不强，也就让很多人可以过了。

刚开始的时候我也只有考虑到时间和炸弹数这两个因素。后来我发现有一个因素我们同样需要考虑就是炸弹炸的地方，好像杭电并没有出这种数据我先出个数据

6 5
S.XX1
X.1X1
XX.X.
XXXXX
XXXXX
XXXDX
这个数据的答案并不是－1，而是17.

我的方法也是比较笨的，个人觉得有点蛮干，我把每条路径的每个位置的炸弹数都保存下来了。所以我的是相对每条路径上的炸弹数，而不是整个的。这样就解决了上面那个问题。

我不知道深搜能不能过，好像时间还挺多的，没试过，如果是深搜的话就简单多了。

这个题还要注意的一点就是已经走过的位置的炸弹和WALL都相当于'.'。

// hdu 2128 mnlm 1.0  
#include<cstdio>  
#include<cstdlib>  
#include<cmath>  
#include<cstring>  
#include<vector>  
#include<algorithm>  
using namespace std;  
#include<queue>  
  
struct NODE  
{  
    int x;  
    int y;  
    int b;  
    int t;  
    int mb[8][8]; //保存每个位置的最小炸弹数  
};  
queue <NODE> q;  
int xy[4][2] =   
{  
    {0, 1},  
    {0, -1},  
    {1, 0},   
    {-1, 0}  
};  
int N;  
int M;  
int startx, starty;  //S的位置  
char map[10][10];  
int ans;             //最小的时间，初始值为-1  
void BFS()  
{  
    ans = -1;  
    while (!q.empty())  
    {  
        q.pop();  
    }  
    NODE m;  
    NODE tt;  
    m.x = startx;  
    m.y = starty;  
    m.b = 0;  
    m.t = 0;  
    memset(m.mb, -1, sizeof(m.mb));  
    m.mb[m.x][m.y] = 0;  
    q.push(m);  
    while (!q.empty())  
    {  
        m = q.front();  
        q.pop();  
        if (ans != -1 &&  
        m.t + 1 >= ans)  
        {  
            continue;  
        }  
        int i;   
        for (i = 0; i < 4; i++)  
        {  
            tt.x = m.x + xy[i][0];  
            tt.y = m.y + xy[i][1];  
            tt.b = -1;  
            if (tt.x >= 0 && tt.x < N &&   
            tt.y >= 0 && tt.y < M)  
            {  
                if (map[tt.x][tt.y] == 'D')  
                {  
                    if (ans == -1 ||  
                    m.t + 1 < ans)  
                    {  
                        ans = m.t + 1;  
                    }  
                    continue;  
                }  
                if (m.mb[tt.x][tt.y] > -1 ||  
                map[tt.x][tt.y] == '.') //已经走过的炸弹和WALL都没有了，相当于'.'  
                {  
                    tt.t = m.t + 1;  
                    tt.b = m.b;  
                }  
                else if (map[tt.x][tt.y] == 'X' &&  
                m.b > 0)  
                {  
                    tt.t = m.t + 2;  
                    tt.b = m.b - 1;  
                }  
                else if (isdigit(map[tt.x][tt.y]))  
                {  
                    tt.t = m.t + 1;  
                    tt.b = m.b + map[tt.x][tt.y] - '0';  
                }/* 这个剪枝有问题
                if (tt.b > m.mb[tt.x][tt.y])  
                {  
                    memcpy(tt.mb, m.mb, 64 * sizeof(int));  
                    tt.mb[tt.x][tt.y] = tt.b;  
                    q.push(tt);  
                }*/
            }  
        }  
    }  
    return;  
}  
int main()  
{  
    while (1)  
    {  
        scanf("%d%d", &N, &M);  
        if (!N && !M)  
        {  
            break;  
        }  
        int i;  
        int j;  
        for (i = 0; i < N; i++)  
        {  
            scanf("%s", map[i]);  
            for (j = 0; j < M; j++)  
            {  
                if (map[i][j] == 'S')  
                {  
                    startx = i;  
                    starty = j;  
                }  
            }  
        }  
        BFS();  
        printf("%d\n", ans);  
    }  
}  

再给一些数据吧：

6 6
S1XX3X
XXXXXX
2XXXXX
XXXXXX
XXXXXX
X1XDXX
29

5 3
S..
1X.
XX.
...
XXD

6

5 6
S.XXXX
21..XX
XXXXXX
XXXXXX
3XXXDX

11