题目链接：https://hpuoj.com/contest/23/problem/B/

B. 恐怖的怪物

单点时限: 5.0 sec

内存限制: 512 MB

一天早上，Dicer一觉醒来，发现自己来到了MineCraft的世界里面，身为MineCraft游戏爱好者的他欣喜不已，于是他在地下挖了一片长方体的空间作为秘密基地，可是他发现光照亮度小于等于7时，会有恐怖的怪物出现，并且他通过查阅资料发现光源方块产生光照每一米（方格）衰减1光照等级。

此规律在坐标轴的3个方向上（东西、南北、上下）均成立。换句话来说，对角线方向的光照衰减依照“曼哈顿距离”（两个点在坐标系上的绝对轴距总和）计算。这意味着，假如地上插着一支火把（光照等级14），则在水平面上与火把相邻的4个方向的方格上光照等级均为13，而在水平面上与火把对角的4个方格上光照等级均为12（譬如，西北方格的光照等级为14-向西1级-向北1级）。

上述这种衰减特性会在光源周围产生菱形的照明。该效果会在光源周围的光源扩散呈钻石状。如果被不透明方块阻挡，光照也可以沿着复杂而弯曲的路径扩散。

如下图所示，红色为光源（亮度等级为14）,黑色为秘密物品，其余各个位置光照强度如图所示。

秘密基地为N∗M的空间，不考虑高度，初始地面光照强度为0。为了不生成恐怖的怪物，Dicer布置了一些光源，但他不知道是否仍会生成怪物，现在请你帮助Dicer判断。

注：光源及秘密物品均为不透明方块，且其上方均不会生成怪物。

输入格式

第一行是一个T。（1≤T≤100）
接下来有T组数据，每一组第一行是N,M,（1≤N,M≤1000）,接下来有N行，每行M个字符，代表秘密基地地面放置的方块，0代表空气，#代表秘密物品，Y代表萤石(光照等级为15)，H代表火把(光照等级为14)，F代表附魔台(光照等级为12)，R代表激活的红石火把(光照等级为7)。

输出格式

输出包含T行，每行如果仍会生成怪物，输出”Yes”,否则输出”No”。

 

标程给的使用BFS解题，时间在两秒左右，我用的DFS时间5秒左右，运气好能过运气不好就过不了。

回头我在补上一个BFS的题解。

也许我的BFS还能再优化优化。

不过解题过程中也遇到很多问题，比如光线不能穿过秘密物品，也不能穿过别的光源，但是可以绕道过去。问题是题目上说，小于等于7就有怪物出现，但是我用DFS的时候不能把7算在内，否则就错。然后样例中也有7的光源，有的有怪物出现有的没怪物出现，按理说其他光源发出的光不能穿过另一个光源，但是可以覆盖？能覆盖的话不就是等于能穿过？总之疑问很多。

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

char G[N][N];
int maps[N][N];
int n, m;

inline int max(int &a, int &b)
{
    if(a > b)
        return a;
    return b;
}

inline void dfs(int num, int i, int j)
{
    if(i < 0 || j < 0 || i ==n || j == m)
        return;
    if(num < 7) 
        return;
    if(num < maps[i][j])
        return;
    maps[i][j] = max(maps[i][j], num);
    if(G[i-1][j] != '#' && G[i-1][j] != 'Y' && G[i-1][j] != 'H' && G[i-1][j] != 'F' && G[i-1][j] != 'R')
        dfs(num-1, i-1, j);
    if(G[i+1][j] != '#' && G[i+1][j] != 'Y' && G[i+1][j] != 'H' && G[i+1][j] != 'F' && G[i+1][j] != 'R')
        dfs(num-1, i+1, j);
    if(G[i][j-1] != '#' && G[i][j-1] != 'Y' && G[i][j-1] != 'H' && G[i][j-1] != 'F' && G[i][j-1] != 'R')
        dfs(num-1, i, j-1);
    if(G[i][j+1] != '#' && G[i][j+1] != 'Y' && G[i][j+1] != 'H' && G[i][j+1] != 'F' && G[i][j+1] != 'R')
        dfs(num-1, i, j+1);
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        
        scanf("%d%d", &n, &m);
        for(int i=0; i<n; i++)
            scanf("%s", G[i]);
        memset(maps, 0, sizeof(maps));
        // for(int i=0; i<n; i++)
        //     for(int j=0; j<m; j++)
        //         maps[i][j] = 0;
        // int num;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(G[i][j] == '0')
                    continue;
                else if(G[i][j] == '#')
                {
                    maps[i][j] = 15;
                    continue;
                }
                else if(G[i][j] == 'Y')
                {
                    maps[i][j] = 15;
                    dfs(15, i, j);
                }
                else if(G[i][j] == 'H')
                {
                    maps[i][j] = max(maps[i][j], 14);
                    dfs(14, i, j);
                }
                else if(G[i][j] == 'F')
                {
                    maps[i][j] = max(maps[i][j], 12);
                    dfs(12, i, j);
                }
                else if(G[i][j] == 'R')
                {
                    maps[i][j] = max(maps[i][j], 7);
                    // maps[i][j] = 7;
                    continue;
                }

            }
        }

        // for(int i=0; i<n; i++)
        // {
        //     for(int j=0; j<m; j++)
        //         printf("%d ", maps[i][j]);
        //     printf("\n");
        // }



        bool flag = true;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(maps[i][j] < 7)
                {
                    flag = false;
                    // break;
                    goto out;
                }
            }
            // if(!flag)
            //     break;
        }
        out:
        if(!flag)
            printf("Yes\n");
        else
            printf("No\n");
    }


    return 0;
}