首页 > 代码库 > UVa 572 油田
UVa 572 油田
题目:相当于有一个m行n列的格子矩阵,每个格子要么@要么*,两个格子是连通的当且仅当这两个格子都是@、且一个格子和另一个是水平、垂直或对角线相邻,即一个格子在另一个格子的周围八个格子范围内。最后求连通块的个数。
思路:和书上例题黑白格子一样,只是一个01,一个*@,稍微改一下就可以了。即通过dfs(x,y)递归地深度优先遍历。
Code:
#include<stdio.h> #include<string.h> #define MAX 110 void dfs(int x,int y); char mat[MAX][MAX]; int vis[MAX][MAX]; int m,n; int main() { while(scanf("%d%d",&m,&n)==2 && m) { memset(mat,'*',sizeof(mat)); memset(vis,0,sizeof(vis)); char s[MAX]; for(int i=0;i<m;++i) { scanf("%s",s); for(int j=0;j<n;++j) mat[i+1][j+1]=s[j]; } int cnt=0; for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) if(mat[i][j]=='@' && !vis[i][j]) { dfs(i,j); cnt++; } printf("%d\n",cnt); } return 0; } void dfs(int x,int y) { if(mat[x][y]=='*' || vis[x][y]) return ; vis[x][y]=1; dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1); dfs(x,y-1); dfs(x,y+1); dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); }
UVa 572 油田
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。