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

判断矩阵的块数

作者: 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