P1506 拯救oibh总部

题目链接

P1506 拯救oibh总部

思路

本题需要用到搜索的知识，对于搜索一个地图，可以使用深度优先搜索，也可以使用广度优先搜索，我在本题解中采用广度优先搜索。

广搜思想

广度优先搜索的思想是每次搜索都在向四面八方扩大搜索范围，可以使用洪水填充模型来理解本题使用的广度优先搜索：如果洪水能淹没总部，则说明从边界到这个总部有路可走。故该程序的目的就是找到从边界到总部的路，这道题很适合使用深度优先搜索，但用广度优先搜索也可以做出来。
广搜时经常使用方向数组，用四个变量存储上下左右四个方向，本题的方向数组是二维的，即有 $dir[4][2]$ ，具体的方向请看代码。

前置知识

队列 $queue$ 容器

广度优先搜索经常使用队列 $queue$ 这个容器，这个容器的特点是先进先出，就像排队一样——先来的人先走。使用这个容器是因为在使用完第一个数据后要删除第一个数据，相比链表 $list$ (进出顺序不限制)和栈 $stack$ (先进后出)，还是队列容器方便一点。

$pair$ 对组

由于地图上的点都有两个坐标，故需要使用一个结构体来保存这两个变量。当然，可以自己写一个结构体来存放行数和列数，但有已实现的 $pair$ 对组，为何不使用它呢？
$pair$ 对组由两个成员构成，$first,second$ 可以使用第一个元素存放某个坐标的行数，使用第二个元素存放该坐标的列数。
此外，可以通过 make_pair() 函数快速构造一个匿名的对组。

泛型

泛型是 $C++$ 的一个重要的编程思想，在本文中一言两语是讲不清楚的，故只介绍在本题目中如何使用泛型。
$queue$ 容器后面有一对尖括号 $<>$，尖括号里面表示本容器要存储的数据类型，比如 $queue<int>q$ 表示容器 $q$ 用于存放 $int$ 类型的变量。
$pair$ 对组后面也有一对尖括号 $<>$，尖括号里面表示本对组要存储的数据类型，比如 $pair<int,int>p$ 表示对组 $p$ 用于存放一对 $int,int$ 类型的变量。
最后，将两者组合一下，就能得到 $queue<pair<int,int>>q$ ，这个表示容器 $q$ 存储的数据类型为 $pair<int,int>$ ，并且 $q$ 中的每个元素都由两个 $int$ 类型的变量组成。如果还有疑惑，请看代码理解该语句。

实现

使用一个 $queue$ 容器存放待搜索总部的坐标，先看地图最外围，如果地图最外围都是墙，则接下来洪水就不能淹没总部；否则洪水就从没墙的地方(换言之，没墙的地方就是总部)往内部流，将沿途的总部都淹没，直到遇到阻挡洪水向内部扩散的墙。可见，如果最外围有总部，则该总部必定被淹没。
此外，还需要一个 $bool$ 类型的数组 $isDrown$ 记录该坐标的总部是否被淹没，同时防止洪水往回流的可能：只有当该坐标是总部，并且该坐标的总部没有被淹没时，才将该坐标放入容器中等待搜索；否则就跳过该坐标。

代码

#include <iostream>
#include <queue>		// 队列容器的头文件
using namespace std;	// 使用std的命名空间
const int N = 505;		// 数组大小
int row, col, ans;		// row, col分别是地图的行数和列数，ans存储答案
char map[N][N];			// map[][]二维数组存储地图
bool isDrown[N][N];		// isDrown[][]二维数组存放位于该坐标的总部是否被淹没
// 广搜常用的方向数组，分别为向上、向下、向右、向左
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int main() {
    cin >> row >> col;
    for (int r = 1; r <= row; ++r) {
        for (int c = 1; c <= col; ++c) {
            cin >> map[r][c];
        }
    }
    queue<pair<int, int>> q;			// 用于存放待搜索的坐标
    // 搜索第一行和最后一行的所有总部
    for (int c = 1; c <= col; ++c) {
        if (map[1][c] == '0') {			// 如果该位置是总部
            q.push(make_pair(1, c));	// 则该位置待搜索
            isDrown[1][c] = true;		// 并且该位置的总部被淹没
        }
        if (map[row][c] == '0') {		// 如果该位置是总部
            q.push(make_pair(row, c));	// 则该位置待搜索
            isDrown[row][c] = true;		// 并且该位置的总部被淹没
        }
    }
    // 搜索第一列和最后一列的所有总部
    for (int r = 2; r < row; ++r) {
        if (map[r][1] == '0') {			// 如果该位置是总部
            q.push(make_pair(r, 1));	// 则该位置待搜索
            isDrown[r][1] = true;		// 并且该位置的总部被淹没
        }
        if (map[r][col] == '0') {		// 如果该位置是总部
            q.push(make_pair(r, col));	// 则该位置待搜索
            isDrown[r][col] = true;		// 并且该位置的总部被淹没
        }
    }
    while (q.size() > 0) {
    	// r是该坐标的行数，c时该坐标的列数
        int r = q.front().first, c = q.front().second;
        q.pop();					// 本轮循环搜索该位置，该位置移出待搜索队列
        for (int i = 0; i < 4; ++i) {			// 分别向该位置的四个方向搜索
        	// ir和ic分别是该坐标周围的坐标的行数和列数
            int ir = r + dir[i][0], ic = c + dir[i][1];
            // 如果新坐标是总部 并且 该总部没有被淹没(该总部没有遍历过)
            if (map[ir][ic] == '0' && !isDrown[ir][ic]) {
                q.push(make_pair(ir, ic));		// 则新位置待搜索
                isDrown[ir][ic] = true;			// 并且新位置的总部被淹没
            }
        }
    }
    // 遍历整个地图，找到没有被淹没的总部
    for (int r = 1; r <= row; ++r) {
        for (int c = 1; c <= col; ++c) {
        	// 如果该坐标是总部	并且	该总部没有被淹没
            if (map[r][c] == '0' && !isDrown[r][c]) {
                ans++;							// 则结果加一
            }
        }
    }
    cout << ans;
    return 0;
}