样例输入:
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
样例输出:
0
1
2
2
AC Code:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char s[101][101];//存入地图的数组 int sum,n,m; int vis[101][101];//标记数组 int dx[]={-1,0,1,-1,1,-1,0,1};//题中说的是横、竖、对角线,所以有8个方向 int dy[]={-1,-1,-1,0,0,1,1,1}; bool judge(int x,int y) { if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==0&&s[x][y]=='@')//越界判断 return true; return false; } void dfs(int x,int y) { vis[x][y]=1;//标记访问过的每个点 for(int k=0;k<8;k++) {//8个方向搜索 int tx=x+dx[k]; int ty=y+dy[k]; if(judge(tx,ty)) { dfs(tx,ty); } } } int main() { while(~scanf("%d %d",&n,&m)) {//多实例输入 if(!n&&!m)//n和m均为0,输入结束 break; for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf(" %c",&s[i][j]);//%前面的空格确保地图可以完整输入 memset(vis,0,sizeof(vis));//标记数组清零 sum=0;//油田数量 for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(vis[i][j]==0&&s[i][j]=='@') {//此点未被访问,从找到的某个油田处开始搜索 sum++;//数量加1,并且搜索出与这个油田相连的所有油田,算1个石油区域 dfs(i,j); } } } printf("%d\n",sum); } return 0; }