游客 注册 | 登录
中文 | En

2687 - 烦人的病灶

通过次数

0

提交次数

0

时间限制 : 3 秒 内存限制 : 128 MB

生物医学图像处理实验室拥有许多包含病灶的眼底图片，老师让苏八八把图片中的病灶区域标出来，这可难坏了苏八八。聪明的你能够帮助苏八八解决这个难题吗？

题目输入

第一行输入一个整数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;
}
请先登陆