题目：
给出一个m x n的矩阵，矩阵中的元素为0或1。称位置(x, y)与其上下左右四个位置(x, y+1)、(x, y-1)、(x+1, y)、(x-1, y)是相邻的。 如果矩阵中有若干个1是相邻的(不必两两相邻)，那么称这些1构成了一个“块”。求给定矩阵中“块”的个数。
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
例如上面的6x7的矩阵中，“块”的个数为4。
题解：
#include <cstdio> #include <queue> using namespace std; const int maxn = 100; struct Node{ int x, y; //位置(x, y) } node; int n, m; //矩阵大小为n*m int matrix[maxn][maxn]; //01矩阵 bool inq[maxn][maxn] = {false}; //记录位置(x, y)是否已入过队 int X[4] = {0, 0, 1, -1}; //增量数组 int Y[4] = {1, -1, 0, 0}; /***判断位置(x, y)是否需要访问****/ bool judge(int x, int y){ //越界返回false if(x >= n || x < 0 || y >= m || y < 0){ return false; } if(matrix[x][y] == 0 || inq[x][y] == true){ return false; } return true; } /***BFS函数访问位置(x, y)所在的块，将该块中所有的1的inq都设置为true****/ void BFS(int x, int y){ queue<Node> Q; node.x = x; node.y = y; Q.push(node); inq[x][y] = true; while(!Q.empty()){ Node top = Q.front(); Q.pop(); for(int i = 0; i < 4; i++){ int newX = top.x + X[i]; int newY = top.y + Y[i]; if(judge(newX, newY)){ node.x = newX; node.y = newY; Q.push(node); inq[newX][newY] = true; } } } } int main(){ scanf("%d%d", &n, &m); for(int x = 0; x < n; x++){ for(int y = 0; y < m; y++){ scanf("%d", &matrix[x][y]); } } int ans = 0; for(int x = 0; x < n; x++){ for(int y = 0; y < m; y++){ if(matrix[x][y] == 1 && inq[x][y] == false){ ans++; BFS(x, y); } } } printf("%d\n", ans); return 0; }
