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