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;
}