判断矩阵的块数
/*
题意:
1、给出一个mn矩阵,矩阵中国男的元素为0或1.一个坐标,上下左右是相邻的。
2、如果矩阵中有若干个1是相邻的,则构成一个块,求块数
解题:
1、枚举每一个位置,为0则跳过,为1,则用bfs查询与该位置相邻4个位置,判断他们是否为1(如果为1)则同样去查询与该位置相邻的4个位置,知道整个1块访问完毕
2、为防止走回头路,(技巧)一般可以设置一个bool型数组来记录每个位置是否在bfs中出现
3、小技巧,增量数组,来表示四个方向
leanr && wrong:
1、为防止走回头路,(技巧)一般可以设置一个bool型数组来记录每个位置是否在bfs中出现
2、小技巧,增量数组,来表示四个方向
*/
include <iostream>
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 x1[4] = { 0, 0, -1, -1};
int y1[4] = { 1, -1, 0, 0};
bool judge(int x, int y) { //判断坐标(x,y)是否需要访问
//越界返回false
if (x >= n || x < 0 || y >= m || y < 0) {
return false;
}
//如果当前位置为0,或者(x,y)已经入队,返回false
if (matrix[x][y] == 0 || inq[x][y] == true) return false;
//以上都不满足,返回true
return true;
}
//BFS函数访问位置(x,y)所在的块,将该块中所有的"1"的inq设为true
void bfs(int x, int y) {
queue<node> q; //定义队列
Node.x = x, Node.y = y; //当前节点的坐标为(x,y)
q.push(Node); //将节点Node入队
inq[x][y] = true; //设置(x,y)已经入队
while (!q.empty()) {
node top = q.front(); // 取出队首元素
q.pop(); //队首元素出队
for (int i = 0;i < 4;i++) {//循环四次,得到相龄的4个位置
int newx = top.x + x1[i];
int newy = top.y + y1[i];
if (judge(newx, newy)) { //如果新位置(newx,newy)需要访问
//设置node的作为为newx,newy
Node.x = x, Node.y = y;
q.push(Node); //将节点node入队
inq[newx][newy] = true; //设置位置newx,newy已经入过队
}
}
}
}
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++) {
//如果元素为1,并且未入队
if (matrix[x][y] == 1 && inq[x][y] == false) {
ans++; //块数+1
bfs(x, y); //访问整个块,将该块所有"1"的inq都标记为true
}
}
}
printf("%d", &ans);
return 0;
}