首页 > 代码库 > 统计八连块
统计八连块
输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻(横竖或者对角线方向),就说它们属于同一个八连块。例如,下图中有两个八连块。
|
输入
|
第一行包括两个正整数m和n,由空格隔开,接下来的m行,每行n个字符,字符只包括“*”和“@”。
|
输出
|
一个自然数,表示八连块的个数。
|
输入示例
|
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
|
输出示例
|
2
|
其他说明
|
数据范围:0<m,n<101。
|
#include<iostream> using namespace std; const int MAXN=101; char a[MAXN][MAXN]; int m,n,flag[MAXN][MAXN]; void dfs(int i,int j,int id) { if(i<0 || i>=m || j<0 || j>=n) return; //判断是否出界 if(flag[i][j]>0 || a[i][j]!=‘@‘) return; //如果已经访问过或者非‘@’字 flag[i][j]=id; //标记第i行第j列的字符被访问过 dfs(i-1,j-1,id); dfs(i-1,j,id); dfs(i-1,j+1,id); dfs(i,j-1,id); dfs(i,j+1,id); dfs(i+1,j-1,id); dfs(i+1,j,id); dfs(i+1,j+1,id);//八个方向 } int main() { int i,j,cnt=0; cin>>m>>n; for(i=0;i<m;i++) cin>>a[i]; for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(flag[i][j]==0 && a[i][j]==‘@‘) dfs(i,j,++cnt); } } cout<<cnt; return 0; }
统计八连块
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。