首页 > 代码库 > DFS——hdu1241Oil Deposits
DFS——hdu1241Oil Deposits
一、题目回顾
题目链接:Oil Deposits
二、解题思路
- DFS经典
- 注意的就是要向八个方向搜索,搜索完一处,将该处变成石头。
三、代码
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int maxn = 1e4+10; 7 #define INF 0x3f3f3f3f 8 char a[105][105]; 9 int m,n,k,ans; 10 11 void dfs(int x,int y) //当前坐标 12 { 13 if(x<1 || x>m || y<1 || y>n || a[x][y]!=‘@‘){ 14 return; 15 } 16 a[x][y] = ‘*‘; //若(x,y)为石油,则标记已访问 17 18 //向当前坐标点的八个方向搜索 19 dfs(x-1,y-1); 20 dfs(x,y-1); 21 dfs(x+1,y-1); 22 dfs(x-1,y); 23 dfs(x+1,y); 24 dfs(x-1,y+1); 25 dfs(x,y+1); 26 dfs(x+1,y+1); 27 } 28 int main() 29 { 30 while(cin>>m>>n && !(m==0 && n==0)){ 31 for(int i=1;i<=m;i++){ 32 getchar(); 33 for(int j=1;j<=n;j++){ 34 scanf("%c",&a[i][j]); 35 } 36 } 37 getchar(); 38 ans = 0; 39 for(int i=1;i<=m;i++){ 40 for(int j=1;j<=n;j++){ 41 if(a[i][j] == ‘@‘){ 42 dfs(i,j); 43 ans++; 44 } 45 } 46 } 47 printf("%d\n",ans); 48 } 49 return 0; 50 }
DFS——hdu1241Oil Deposits
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。