2687 - 烦人的病灶
生物医学图像处理实验室拥有许多包含病灶的眼底图片，老师让苏八八把图片中的病灶区域标出来，这可难坏了苏八八。聪明的你能够帮助苏八八解决这个难题吗？
题目输入
第一行输入一个整数N，表示共有N组测试数据
每一组数据都是先输入该图片的行数m(0<m<100)与列数n(0<n<100)，然后，输入接下来的m行每行输入n个数，表示此处有没有病灶（1表示此处是病灶区，0表示此处正常）
题目输出
输出该图片中病灶区域的个数。
要注意，如果每个病灶的旁边（上下左右四个位置）如果还是病灶的话，应该将其看作同一个病灶区域。
输入/输出样例
题目输入
2 3 4 1 0 0 0 0 0 1 1 1 1 1 0 5 5 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1
题目输出
2 3
C语言解答
#include<stdio.h> int m,n; short tab[101][101]; const int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; void check(int a,int b){ tab[a][b] = 0; int i,x,y; for(i = 0;i < 4;i++){ x = a + dir[i][0]; y = b + dir[i][1]; if(x >=0 && x < m && y >= 0 && y < n && tab[x][y]){ check(x,y); } } } int main(){ //freopen("a.txt","r",stdin); int T,count,i,j; scanf("%d",&T); while(T--){ count = 0; scanf("%d%d",&m,&n); for(i = 0;i < m;i++) for(j = 0;j < n;j++){ scanf("%hd",&tab[i][j]); } for(i = 0;i < m;i++) for(j = 0;j < n;j++) if(tab[i][j]){ check(i,j); count++; } printf("%d\n",count); } return 0; }
C++解答
/** dfs深度搜索 **/ #include<iostream> #include<cstring> using namespace std; int a[101][101],vis[101][101]; void dfs(int x,int y){ if(!a[x][y]||vis[x][y]) return;//已访问或不是水池(a[x][y]==0) vis[x][y]=1;//已访问过 /**搜素上下左右四个方向**/ dfs(x-1,y);//搜素上面 dfs(x+1,y);//搜素下面 dfs(x,y-1);//搜素左面 dfs(x,y+1);//搜素右面 } int main() { int m,n,t; cin>>t; while(t--){ cin>>m>>n; memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; int count=0; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(!vis[i][j]&&a[i][j]){//if(有水池)&没有被访问 count++; dfs(i,j); } } } cout<<count<<endl; } return 0; }