题目描述

2XXX年，人类通过对火星的大气进行宜居改造分析，使得火星已在理论上具备人类宜居的条件，由于技术原因，无法一次性将火星大气全部改造，只能通过局部处理形式。假设将火星待改造的区域为row * column的网格，每个网格有三个值，宜居区、可改造区、死亡区，使用YES、NO、NA代替，YES表示该网格已经完成大气改造，NO表示该网格未进行改造，后期可进行改造，NA表示死亡区，不作为判断是否改造完成的宜居，无法穿过。初始化下，该区域可能存在多个宜居区，并且每个宜居区能同时在每个太阳日单位向上下左右四个方向的相邻格子进行扩散，自动将四个方向相邻的真空区改造成宜居区：请计算这个待改造区域的网格中，可改造区是否能全部变成宜居区，如果可以，则返回改造的太阳日天数，不可以则返回-1。

样例

输入 row * column 个网格数据，每个网格值枚举值如下：YES，NO，NA

示例1
输入：
YES YES NO  
NO NO NO
YES NO NO

输出：
2

经过2个太阳日，完成宜居改造。

示例2
输入：
YES NO NO NO
NO NO NO NO
NO NO NO NO
NO NO NO NO

输出：
6

示例3
输入：
NO NA

输出：
-1

C++ 代码

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1010, M = N * N, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];
PII q[M];

void bfs(vector<vector<string>>& g)
{   
    int hh = 0, tt = -1;
    memset(d, 0x3f, sizeof d);

    for (int i = 0; i < n; i++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == "YES")
            {
                q[++ tt] = {i, j};
                d[i][j] = 0;
            }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

    while (hh <= tt)
    {
        auto t = q[hh ++ ];
        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[a][b] == "NA") continue;
            if (d[a][b] > d[t.x][t.y] + 1)
            {
                d[a][b] = d[t.x][t.y] + 1;
                q[++ tt] = {a, b};
            }
        }
    }
}

int main()
{   
    string s;
    vector<vector<string>> g;
    while(getline(cin, s))
    {   
        vector<string> tmp;
        string t;
        stringstream ssin(s);
        while (ssin >> t)
        {
            tmp.push_back(t);
        }
        g.push_back(tmp);
    }

    n = g.size(), m = g[0].size();

    bfs(g);

    int res = -1;

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == "NO")
                res = max(res, d[i][j]);
    if (res == INF) res = -1;

    cout << res << endl;

    return 0;
}