文章

21

粉丝

0

获赞

19

访问

3.6k

头像
雨后圆子 题解:C++
P5364 四川大学2024年机试题
发布于2026年3月27日 16:21
阅读数 82

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int n, m; 
vector<string> map;
// 方向矩阵
int dir[2][8] = {{0,  0, 1, 1,  1, -1, -1, -1},
		   		 {1, -1, 0, 1, -1,  0,  1, -1}};

// 每次找到一点后向周围蔓延
void dfs(int i, int j){
    // 越界和非水坑就返回
	if(i < 0 || i >= n || j < 0 || j >= m || map[i][j] != 'W')
		return;
	
	map[i][j] = '.'; // 把水坑填上防止二次遍历
	for(int k = 0; k < 8; k++)
		dfs(i + dir[0][k], j + dir[1][k]);
}

int main(){
	cin >> n >> m;
	map.resize(n, string(m, '.')); 
	for(int i = 0; i < n; i++)
		cin >> map[i];
	
	//------------------------------------
	int ans = 0;
    // 遍历找水坑
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(map[i][j] == 'W'){
				dfs(i, j);
				ans++; // 每次进入dfs必定将一个相连通的水坑填上,因此进入次数就是答案数
			}
		}
	}
	cout << ans << endl;
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发