满江红
查看原帖
满江红
1213524
C_plus_plus_12345楼主2024/12/20 21:52

怒发冲冠,凭栏处、潇潇雨歇。抬望眼,仰天长啸,壮怀激烈。三十功名尘与土,八千里路云和月。莫等闲,白了少年头,空悲切!

靖康耻,犹未雪。臣子恨,何时灭!驾长车,踏破贺兰山缺。壮志饥餐胡虏肉,笑谈渴饮匈奴血。待从头,收拾旧山河,朝天阙!

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

// 定义方向数组,用于DFS遍历上下左右四个方向
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 深度优先搜索函数
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x,
         int y, int n, int m)
{
	// 标记当前位置为已访问
	visited[x][y] = true;

	// 遍历四个方向
	for (int i = 0; i < 4; ++i)
	{
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];

		// 检查新坐标是否在矩阵范围内,并且新位置是细胞且未访问过
		if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '0'
		        && !visited[nx][ny])
		{
			dfs(grid, visited, nx, ny, n, m);
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<char>> grid(n, vector<char>(m));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j <= m; ++j)
		{
			cin >> grid[i][j];
		}
	}

	vector<vector<bool>> visited(n, vector<bool>(m, false));
	int cellCount = 0;

	// 遍历整个矩阵
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			// 如果当前位置是细胞且未访问过,则启动一次DFS
			if (grid[i][j] != '0' && !visited[i][j])
			{
				dfs(grid, visited, i, j, n, m);
				++cellCount; // 找到一个完整的细胞,细胞计数加一
			}
		}
	}

	cout << cellCount << endl;

	return 0;
}

就俩测试点是绿的

2024/12/20 21:52
加载中...