2343 - 统计林地(bfs模板)

其他 C++ 公开

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char mp[107][107];
int n, m;
int vis[107][107]; // 标记数组
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0,-1}; // 方向数组 

struct node{
	int x, y;  // 用来存储每一个点的坐标 
};

int main() {

	cin >> n >> m;
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			cin >> mp[i][j];
		}
	}
	int ans = 0;  // 用来统计结果的变量
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			// 这个地方不能是字符0，并且还不能被搜索过 
			if (mp[i][j] != '0' && vis[i][j] == 0){
				ans++; 
				queue<node> q;
				q.push({i, j}); vis[i][j] = 1;// 标记这个节点已经走过了 
				while (!q.empty()) {
					node f = q.front();
					q.pop();
					for (int k=0; k<4; k++){
						int nx = f.x + dx[k]; int ny = f.y + dy[k];
						if (nx>=0&&nx<n &&ny>=0 &&ny<m && mp[nx][ny]!='0' && vis[nx][ny] == 0){
							q.push({nx, ny});
							vis[nx][ny] = 1;
						}
					} 
				}
			} 
		}
	}	 
	cout << ans;
	return 0;
}