本文主要是介绍964: 数细胞，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
样例：
解法：
1.遍历矩阵
2.判断矩阵[i][j]，若是未标记细胞则遍历相邻所有未标记细胞并标记，且计数
实现：遍历相邻所有未标记细胞
以DFS实现：
function dfs(当前状态) {if (终止条件) {}vis[标记当前状态]for (寻找新状态) {if (状态合法) {dfs(新状态)//看情况是否需要重置vis[]}}
}代码
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = { 0,1,1,0,-1,0,0,-1 };
void dfs(vector<vector<int>>& a, int x, int y) {if (a[x][y] == 0) return;a[x][y] = 0;for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= a.size() || nexty < 0 || nexty >= a[0].size()) {continue;}if (a[nextx][nexty] != 0) {dfs(a, nextx, nexty);}}
}
int main() {int m, n;cin >> m >> n;vector<vector<int>> a(m, vector<int>(n , 0));for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)cin >> a[i][j];int result = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (a[i][j] != 0) {result++;dfs(a, i, j);}}}cout << result;return 0;
}以BFS实现：
function bfs(当前节点) {当前节点入列标记当前节点while (队列不为空) {当前节点出列寻找合法相邻节点合法相邻节点入列标记相邻节点}
}代码：
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
int dir[4][2] = { 0,1,1,0,-1,0,0,-1 };
void bfs(vector<vector<int>>& a, int x, int y) {queue<pair<int, int>> que;que.push({ x,y });a[x][y] = 0;while (!que.empty()) {pair<int, int> cur = que.front();que.pop();int curx = cur.first;int cury = cur.second;for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= a.size() || nexty < 0 || nexty >= a[0].size()) {continue;}if (a[nextx][nexty] != 0) {que.push({ nextx,nexty });a[nextx][nexty] = 0;}}}
}
int main() {int m, n;cin >> m >> n;vector<vector<int>> a(m, vector<int>(n, 0));for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)cin >> a[i][j];int result = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (a[i][j] != 0) {result++;bfs(a, i, j);}}}cout << result;return 0;
}这篇关于964: 数细胞的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
