问题 F: 地质调查
题目要求： 小明是一个地质调查员，在他调查的地方突然出现个泉眼。由于当地的地势不均匀，有高有低，他觉得这意味着这里在不久的将来将会一个小湖。水往低处流，凡是比泉眼地势低或者等于的地方都会被水淹没，地势高的地方水不会越过。而且又因为泉水比较弱，当所有地势低的地方被淹没后，水位将不会上涨，一直定在跟泉眼一样的水位上。现在给出小明掌握的地图，所有的地图都是一个矩形，并按照坐标系分成了一个个小方格，小明测量除了每个方格的具体高度。我们假定当水留到地图边界时，不会留出地图外，现在他想通过这些数据分析出，将来这里将会出现一个多大面积的湖。
输入 有若干组数据，每组数据的第一行有四个整数n,m,p1,p2(0<n,m,p1,p2<=100)，n和m表示当前地图的长和宽，p1和p2表示当前地图的泉眼位置，即第p1行第p2列，随后的n行中，每行有m个数据。表示这每一个对应坐标的高度。 输出 输出对应地图中会有多少个格子被水充满。 样例输入 Copy 3 5 2 3 3 4 1 5 1 2 3 3 4 7 4 1 4 1 1 样例输出 Copy 6
解题思路： 典型的搜索题。不外乎两种方法：深度优先搜索，广度优先搜索。广度优先搜索思路如下：从指定的矩阵起点开始，将符合条件的点的位置放入队列中，依次从队列中取出一个位置，并搜索这个位置的上下左右，搜到符合条件的位置，则计数器 1，并且赋予这个位置一个特殊值，防止重复搜索，直至队列为空，搜索完成。
通关代码：
代码语言：javascript复制#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int getWaterNum(vector<vector<int>> matrix, int originX, int originY) {
const int bx[] = {0, 0, -1, 1};
const int by[] = {1, -1, 0, 0};
int sum = 1;
int height = matrix[originX][originY];
int ROW = matrix.size();
int COLUMN = matrix[0].size();
queue<pair<int, int>> q;
q.emplace(originX, originY);
matrix[originX][originY] = -1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i ) {
int nx = x bx[i];
int ny = y by[i];
if (nx >= 0 && nx < ROW && ny >= 0 && ny < COLUMN) {
if (matrix[nx][ny] <= height && matrix[nx][ny] != -1) {
sum ;
q.emplace(pair<int, int>(nx, ny));
matrix[nx][ny] = -1;
}
}
}
}
return sum;
}
int main() {
vector<vector<int>> matrix;
int ROW, COLUMN, originX, originY;
cin >> ROW >> COLUMN >> originX >> originY;
vector<int> arr(COLUMN);
for (int i = 0; i < ROW; i ) {
for (int j = 0; j < COLUMN; j ) {
cin >> arr[j];
}
matrix.emplace_back(arr);
}
cout << getWaterNum(matrix, originX - 1, originY - 1);
return 0;
} 
