一本通-1191：流感传染（两个队列模拟BFS）¶

一本通-1191：流感传染（两个队列模拟BFS）¶

【题目描述】有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。

【输入】第一行一个数字n，n不超过100，表示有n*n的宿舍房间。接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。接下来的一行是一个整数m，m不超过100。

【输出】输出第m天，得流感的人数。

【输入样例】

5
....#
.#.@.
.#@..
#....
.....
4

【输出样例】 16

这道题目初看可以用DFS求解，但是会存在很多重复遍历造成超时的情况。比如下面程序：

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

struct Node {
    int x, y;
    Node(int xEle, int yEle): x(xEle), y(yEle) {}
};

int n;
vector<vector<char> > grid(100, vector<char>(100));
int m;
int direction[4][2] = {{1,0}, {-1,0}, {0,1}, {0, -1}};

void DFS(int row, int col, int step)
{
    ++step; grid[row][col] = '@';
    if (step >= m) return;

    for (int i = 0; i < 4; ++i) {
        int nextRow = row + direction[i][0];
        int nextCol = col + direction[i][1];
        if (0 <= nextRow && nextRow < n && 0 <= nextCol && nextCol < n 
            && (grid[nextRow][nextCol] == '.' || grid[nextRow][nextCol] == '@')) {
            DFS(nextRow, nextCol, step);
        }
    }
}

ostream & operator<<(ostream & os, vector<vector<char> > &v)
{
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            os << v[i][j] << " ";
        }
        os << endl;
    }
    return os;
}

int solve()
{
    vector<Node> store;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '@') {
                store.push_back(Node(i, j));
            }
        }
    }

    int len = store.size();
    for (int i = 0; i < len; ++i) {
        DFS(store[i].x, store[i].y, 0);
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '@') ++cnt;
        }
    }

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
        }
    }
    cin >> m;
    cout << solve() << endl;
    // cout << grid;

    return 0;
}

结果可以保证正确，但是性能很差。

另外的一种方法就是给每个点加上一个时间戳，用两个队列来维护可以被传染的点，其实就是模拟的BFS，每个队列维护第i层，然后分奇偶天去处理每一层，总有一个队列是空的，于是交替进行就模拟了BFS。

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

struct Node {
    int x, y;
    Node(int xEle, int yEle): x(xEle), y(yEle) {}
};

int n;
vector<vector<char> > grid(100, vector<char>(100));
int m;
int direction[4][2] = {{1,0}, {-1,0}, {0,1}, {0, -1}};

ostream & operator<<(ostream & os, vector<vector<char> > &v)
{
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            os << v[i][j] << " ";
        }
        os << endl;
    }
    return os;
}

int solve()
{
    queue<Node> q1, q2;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '@') {
                ++cnt;
                q1.push(Node(i, j));
            }
        }
    }

    for (int i = 2; i <= m; ++i) {
        if (i & 1) { //奇数天
            while (!q2.empty()) {
                Node tmp = q2.front(); q2.pop();
                for (int j = 0; j < 4; ++j) {
                    int nextRow = tmp.x + direction[j][0];
                    int nextCol = tmp.y + direction[j][1];
                    if (0 <= nextRow && nextRow < n && 0 <= nextCol && nextCol < n 
                        && grid[nextRow][nextCol] == '.') {
                        grid[nextRow][nextCol] = '@';
                        ++cnt;
                        q1.push(Node(nextRow, nextCol));
                    }
                }
            }
        }
        else { //偶数天
            while (!q1.empty()) {
                Node tmp = q1.front(); q1.pop();
                for (int j = 0; j < 4; ++j) {
                    int nextRow = tmp.x + direction[j][0];
                    int nextCol = tmp.y + direction[j][1];
                    if (0 <= nextRow && nextRow < n && 0 <= nextCol && nextCol < n 
                        && grid[nextRow][nextCol] == '.') {
                        grid[nextRow][nextCol] = '@';
                        ++cnt;
                        q2.push(Node(nextRow, nextCol));
                    }
                }
            }
        }
    }

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
        }
    }
    cin >> m;
    cout << solve() << endl;
    // cout << grid;

    return 0;
}