本文主要是介绍hdu 1241 Oil Deposits(经典dfs),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1241
大意:寻找一块区域中有多少的‘@’域,左右上下还有四个斜45度的相邻点都算作连起来的。
Sample Input
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0
Sample Output
0 1 2 2
#include <iostream>
#include<cstdio>
using namespace std;
char s[105][105];
int n,m;
int dir[8][2]={{0,1},{0,-1},{-1,0},{1,0},{1,1},{-1,1},{1,-1},{-1,-1}};
void show(){cout<<"show:"<<endl;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<s[i][j];}cout<<endl;}
}
void dfs(int x,int y){s[x][y]='*';for(int i=0;i<8;i++){int xx=x+dir[i][0],yy=y+dir[i][1];if(xx<n&&xx>=0&&yy<m&&yy>=0&&s[xx][yy]=='@'){dfs(xx,yy);//show();}}
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>n>>m){if(n==0&&m==0)break;for(int i=0;i<n;i++){scanf("%s",s[i]);}int ans=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='@'){dfs(i,j);ans++;}}}printf("%d\n",ans);}return 0;
}
这篇关于hdu 1241 Oil Deposits(经典dfs)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!