題目描述

一矩形陣列由數字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;}

轉載于:https://www.cnblogs.com/ghostcai/p/9247551.html

總結

以上是生活随笔為你收集整理的[LUOGU]P1451 求细胞数量的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。