首页 > 代码库 > hdu1241 dfs

hdu1241 dfs

2024-08-11 21:40:43   218人阅读

链接改天再补 杭电又崩了。。。

题意：求“@”组成了多少个联通区域，每个点的8个方向都认为是相连的

思路：对每一个点进行搜索 当Map == @ && vis == 0 时 可进入搜索 每次进入搜索时 ans++ 搜索时将该联通区域所有的点标记 8个方向搜

AC代码：

 1 #include "iostream" 2 #include "string.h" 3 #include "stack" 4 #include "queue" 5 #include "map" 6 #include "algorithm" 7 #include "stdio.h" 8 #include "math.h" 9 #define ll long long10 #define mem(a) memset(a,0,sizeof(a))11 #define max(a,b) a > b ? a : b12 #define min(a,b) a < b ? a : b13 14 using namespace std;15 16 int d[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}};17 bool vis[1005][1005];18 bool Map[1005][1005];19 20 struct Node21 {22     int xx,yy;23 };24 25 void Dfs(int x,int y)26 {27     stack<Node>S;28     Node now,next;29     now.xx = x;30     now.yy = y;31     vis[x][y] = 1;32     S.push(now);33 34     while(!S.empty())35     {36         now = S.top();37         S.pop();38 39         for(int i=0; i<8; i++)40         {41             next.xx = now.xx + d[i][0];42             next.yy = now.yy + d[i][1];43 44             if(Map[next.xx][next.yy] && !vis[next.xx][next.yy])45             {46                 vis[next.xx][next.yy] = 1;47                 S.push(next);48             }49         }50     }51 }52 53 int main()54 {55     int n,m,i,j,ans;56     char c;57     while(scanf("%d%d",&m,&n)&&(m||n))58     {59         mem(vis);60         mem(Map);61         ans = 0;62         for(i=1; i<=m; i++)63             for(j=1; j<=n; j++)64             {65                 cin>>c;66                 if(c==‘@‘)67                     Map[i][j] = 1;68                 if(c==‘*‘)69                     Map[i][j] = 0;70             }71         for(i=1; i<=m; i++)72             for(j=1; j<=n; j++)73             {74                 if(Map[i][j] && !vis[i][j])75                 {76                     ans++;77                     Dfs(i,j);78                 }79             }80         printf("%d\n",ans);81     }82     return 0;83 }

 

hdu1241 dfs


联系
我们