2020东北大学NEU校赛热身赛：找猫猫

Problem: 找猫猫
Time limit: 1s Mem limit: 64 MB
Problem Description
猫猫和嘟嘟一起打游戏， 猫猫被困在了M点不能移动，每一秒减少一个单位的HP， 需要队友嘟嘟来救。但是现在嘟嘟不在猫猫旁边，而是在远离猫猫的另一个D点。当猫猫的HP变成负数之后，猫猫的人物就会死亡，而猫猫就会不高兴。为了让猫猫能继续玩下去， 嘟嘟需要马上到M点去救猫猫（嘟嘟到达后可以让猫猫的HP增加并且可以离开M点）。
现在给你这个n*m的游戏地图， D代表嘟嘟的位置，M代表猫猫的位置，*代表可以走的路，#代表不能翻越的墙。已知现在猫猫的HP为t个单位，嘟嘟每1秒只能移动1个格子，只能走上下左右四个方向（不能斜着走，即四联通） 。
现在问你，嘟嘟能不能在猫猫HP变为负数之前到达M点？ 如果能到达，请输出猫猫最小损失的HP。不然，游戏结束，猫猫很生气，嘟嘟会跪机械键盘的，所以就要输出一行字符串：“OMG! DUDU is bound to Kneel keyboard”(没有引号）。

Input
第一行一个整数T，代表有T组数据。
每组数据的第一行有三个整数m, n, t，分别表示地图的行数、地图的列数和猫猫的HP。 (0<=m,n<=10 0<=t<=100)
接下来有m行数据，每行n个字符，代表一个mn的矩阵，矩阵有且仅有’D’ ’M’ ‘’ ‘#’字符组成（没有引号）

Output
如果嘟嘟能在猫猫HP变为负数之前到达M点，则输出猫猫损失的最小HP。
否则输出“OMG! DUDU is bound to Kneel keyboard”（没有引号）

Sample Input
2
3 3 10
D**
#
#M*
3 3 2
D**
#
#M*
Sample Output

5
OMG! DUDU is bound to Kneel keyboard

这是一道广度优先搜索的例题，深度优先搜索虽然可以得出答案但是容易超时，广度优先搜索的思路是从起点开始向可以走的方向辐射出去搜索，搜到终点时停止。广度优先搜索一旦搜索到终点就肯定是最短路径，相比深度优先搜索来说内存占用多一些，但是快得多。

下面是BFS解法代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
typedef long long ll;
const int M = 1005;
const int INF = 0x3f3f3f3f;

struct Node
{
    int x, y, step;// 记录点和当前步数
};
queue <Node> Q;
int maze[15][15], m, n, t, x, y;// maze记录已经去过的点，防止重复遍历，m和n是长和宽，t是最大HP，x和y是终点坐标
// 广度优先搜索
void bfs()
{
    int nx, ny, step;
    while(!Q.empty())
    {
        Node pt = Q.front();// 导出目前搜索的点
        Q.pop();
        nx = pt.x;
        ny = pt.y;
        step = pt.step;
        if (nx == x && ny == y)// 坐标符合则结束搜索
        {
            if (step <= t) printf("%d\n", step);// HP未为负
            else printf("OMG! DUDU is bound to Kneel keyboard\n");// 到达了点但是HP为负
            return;
        }
        // 四方向搜索
        if (nx >= 1 && !maze[nx-1][ny])
        {
            Node ptt = {nx-1, ny, step+1};
            maze[nx-1][ny] = 1;
            Q.push(ptt);
        }
        if (nx <= m && !maze[nx+1][ny])
        {
            Node ptt = {nx+1, ny, step+1};
            maze[nx+1][ny] = 1;
            Q.push(ptt);
        }
        if (ny >= 1 && !maze[nx][ny-1])
        {
            Node ptt = {nx, ny-1, step+1};
            maze[nx][ny-1] = 1;
            Q.push(ptt);
        }
        if (ny <= n && !maze[nx][ny+1])
        {
            Node ptt = {nx, ny+1, step+1};
            maze[nx][ny+1] = 1;
            Q.push(ptt);
        }
    }
    // 终点属于不能到达的类型，可去的点全部搜索完毕也无法到达，输出失败结果
    printf("OMG! DUDU is bound to Kneel keyboard\n");
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        // 初始化
        while(!Q.empty())
            Q.pop();
        memset(maze, 0, sizeof(maze));
        char line[15];
        scanf("%d%d%d", &m, &n, &t);
        for(int i = 1; i <= m; i++)
        {
            scanf("%s", line);
            for(int j = 1; j <= n; j++)
            {
                // 记录起点和终点，以及不能去的点
                if (line[j-1] == 'D')
                {
                    maze[i][j] = 1;
                    Node pt = {i, j, 0};
                    Q.push(pt);
                }
                else if (line[j-1] == 'M')
                {
                    x = i;
                    y = j;
                }
                else if (line[j-1] == '#')
                    maze[i][j] = 1;
            }
        }
        // 开始BFS计算
        bfs();
    }
    return 0;
}

在做类似这种题目时，建议使用广搜节省时间。