题意

一块m*n的油田里 @ 表明油袋 * 表明空地，相连（八个方向上下左右对角）的油袋为同一个油块，问油田中有几个油块，输入以m=0结束web

1. 范围：1 <= m <= 100 and 1 <= n <= 100
2. 连接：Oil Deposits
3. 输入

1 1
*
3 5
@@*
@
@@*
1 8
@@***@
5 5
****@
@@@
@**@
@@@@
@@**@
0 0svg

4. 输出

0
1
2
2spa

解题思路

深搜求连通块数.net

易错点

• 没有将已搜过的油袋改成空地
• 读入数据是没有作换行处理

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int map[110][110],n,m;
char s[110];
int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//八个方向 
void dfs(int x,int y)//深搜 
{
	if(map[x][y]==1)map[x][y]=0;//修改搜过的油袋 
	for(int i=0;i<8;i++)//八个方向搜索 
	{
		int a=x+dir[i][0];
		int b=y+dir[i][1];
		if(map[a][b]&&a>=1&&b>=1&&a<=m&&b<=n)
		dfs(a,b);
	}
}
int main()
{
	scanf("%d%d",&m,&n);
	while(m!=0)
	{
		gets(s);//换行处理 
		int cnt=0;//油块数 
		memset(map,0,sizeof(map));
		for(int i=1;i<=m;i++)
		{
			gets(s);//换行处理 
			for(int j=0;j<n;j++)
			if(s[j]=='*')map[i][j+1]=0;
			else if(s[j]=='@')map[i][j+1]=1;
			//将字符油田转为数字油田，1为油袋，0为空地 
		}
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				if(map[i][j])
				{
					dfs(i,j);
					cnt++;
				}
		printf("%d\n",cnt);
		scanf("%d%d",&m,&n);
	}
	return 0;
}