[LUOGU]P1451 求细胞数量

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1<=m,n<=100）?

输入输出格式

输入格式： 输入：整数m,n(m行，n列)

矩阵

输出格式： 输出：细胞的个数

输入输出样例

输入样例#1：4 10
0234500067
1034560500
2045600671
0000000089
输出样例#1： 4

dfs每个非0且未访问的数字。

#include<iostream> #include<string> #define MAXN 200 using namespace std; int a[MAXN][MAXN]; int m,n; bool vis[MAXN][MAXN]; int ans; inline bool pd(int x,int y) { if(x<=m&&x>0&&y<=n&&y>0) return true; return false; } void dfs(int x,int y) { if(vis[x][y]||a[x][y]==0) return; a[x][y]=-1; vis[x][y]=1; if(pd(x+1,y)) dfs(x+1,y); if(pd(x-1,y)) dfs(x-1,y); if(pd(x,y+1)) dfs(x,y+1); if(pd(x,y-1)) dfs(x,y-1); return; } int calc() { int i,j; int cnt=0; for(i=1; i<=m; i++) { for(j=1; j<=n; j++) { if(a[i][j]==-1) { a[i][j]=0; cnt++; } } } return cnt; } void show(){ for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { cout<<a[i][j]<<" "; } cout<<endl; } cout<<endl; } int main() { int i,j; cin>>m>>n; string s; for(i=1; i<=m; i++) { cin>>s; for(j=0; j<n ; j++) { a[i][j+1]=s[j]-'0'; } } for(i=1; i<=m; i++) { for(j=1; j<=n; j++) { if(!vis[i][j]&&a[i][j]!=0) { dfs(i,j); // show(); int re=calc(); if(re>0) ans++; } } } cout<<ans; return 0; }

和swim很像。。恩

宽搜版:

#include<iostream>
#include<queue>
#include<string>
#define MAXN 200
using namespace std;

int n,m;
int a[MAXN][MAXN];
int cnt;
bool vis[MAXN][MAXN];
int mx[4]= {1,0,-1,0};
int my[4]= {0,1,0,-1};

struct point {
    int x,y;
} node,r;

void bfs(int x,int y) {
    a[x][y]=0;
    vis[x][y]=1;
    queue<point> Q;
    node.x = x;
    node.y = y;
    Q.push(node);
    while(!Q.empty() ) {
        r=Q.front() ;
        Q.pop();
        for(int i=0; i<=3; i++) {
            int nx=r.x + mx[i],ny=r.y + my[i];
            if(nx>0&&nx<=m&&ny>0&&ny<=n&&a[nx][ny]!=0&&!vis[nx][ny]) {
                a[nx][ny]=0;
                vis[nx][ny]=1;
                node.x = nx;
                node.y = ny;
                Q.push(node); 
            }
        }
    }
}

void show(){
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
int main() {
    string s;
    cin>>m>>n;
    int i,j;
    for(i=1; i<=m; i++) {
        cin>>s;
        for(j=0; j<n; j++) {
            a[i][j+1]=s[j]-'0';
        }
    }

    for(i=1; i<=m; i++) {
        for(j=1; j<=n; j++) {
            if(a[i][j]!=0) {
                bfs(i,j);
                cnt++;
            }
        }
    }
    cout<<cnt;

}