hdu 1241 Oil Deposits 【DFS】

2019-11-08 03:21:15

字体：大中小

来源：转载

供稿：网友

题目链接：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;}

上一篇：127. Word Ladder

下一篇：Matlab常见错误及解决办法归纳