文章

21

粉丝

0

获赞

19

访问

4.8k

头像
极大连通图个数 题解:C++
P1975 四川大学2024年机试题
发布于2026年3月27日 16:20
阅读数 203

#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++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发