本文主要是介绍hdu 1241 Oil Deposits 【DFS】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1241
题意:油田问题,很经典的搜索题
解析:每遇到@就对他进行dfs,把和他相连的@全都打上标记,顺便ans++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int dx[] = {0,1,-1,0,1,-1,1,-1};
int dy[] = {1,0,0,-1,-1,1,1,-1};
char a[105][105];
int n,m;
int vis[105][105];
void dfs(int x,int y)
{for(int i=0;i<8;i++){int tx = x+dx[i];int ty = y+dy[i];if(vis[tx][ty] || a[tx][ty]=='*')continue;if(tx<0 || tx>=n || ty<0 || ty>=m)continue;vis[tx][ty] = 1;dfs(tx,ty);}return ;
}
int main()
{while(~scanf("%d %d",&n,&m)){if(n==0 && m==0)break;for(int i=0;i<n;i++)scanf("%s",a[i]);memset(vis,0,sizeof(vis));int ans = 0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]=='@' && !vis[i][j]){vis[i][j] = 1;dfs(i,j);ans++;}}}printf("%d\n",ans);}return 0;
}
这篇关于hdu 1241 Oil Deposits 【DFS】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!