判断矩阵的块数

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

}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 8,789评论 0 2
  • 贪心算法 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上...
    fredal阅读 13,046评论 3 52
  • SwiftDay011.MySwiftimport UIKitprintln("Hello Swift!")var...
    smile丽语阅读 9,251评论 0 6
  • 计算机二级C语言上机题库(南开版) 1.m个人的成绩存放在score数组中,请编写函数fun,它的功能是:将低于平...
    MrSunbeam阅读 11,532评论 1 42
  • 鼻涕兔 我一直喜欢看别人写字,硬笔,软笔,篆书隶书,行书……尤其是书写整洁漂亮的。希望有一天也和他们一样,把文章写...
    鼻涕兔阅读 2,087评论 2 6