美文网首页
判断矩阵的块数

判断矩阵的块数

作者: km15 | 来源:发表于2020-03-04 11:57 被阅读0次

/*
题意:
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;

}

相关文章

网友评论

      本文标题:判断矩阵的块数

      本文链接:https://www.haomeiwen.com/subject/fnsmlhtx.html