OJ刷题记录：问题 F: 地质调查

英雄爱吃土豆片

发布于 2020-10-29 11:05:03

3380

发布于 2020-10-29 11:05:03

问题 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，并且赋予这个位置一个特殊值，防止重复搜索，直至队列为空，搜索完成。

通关代码：

#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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/08/28 ，如有侵权请联系 cloudcommunity@tencent.com 删除

地图