题解
【入门】有多少细胞
1 条题解
-
0
#include <iostream> #include <vector> #include <string> using namespace std; // 四个方向:上下左右 const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) { int m = grid.size(); int n = grid[0].size(); // 边界检查:超出范围、已访问、是0则返回 if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) { return; } visited[x][y] = true; // 标记为已访问 // 遍历四个方向 for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; dfs(grid, visited, nx, ny); } } int main() { int m, n; cin >> m >> n; cin.ignore(); // 忽略换行符,避免影响后续getline vector<vector<int>> grid(m, vector<int>(n)); for (int i = 0; i < m; ++i) { string line; getline(cin, line); for (int j = 0; j < n; ++j) { grid[i][j] = line[j] - '0'; // 字符转整数 } } vector<vector<bool>> visited(m, vector<bool>(n, false)); int count = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { // 找到未访问的非0数字,启动DFS if (!visited[i][j] && grid[i][j] != 0) { count++; dfs(grid, visited, i, j); } } } cout << count << endl; return 0; }
- 1