现在的位置: 首页 > 算法 > 正文

poj1562

2017年11月23日 算法 ⁄ 共 634字 ⁄ 字号 评论关闭

为了做好apple tree。。我先水个dfs的题吧。。。这个题确实挺水的T_T,就是一裸裸的dfs啊。。。。结果一开始还卡在了输入上。。。。

题意就是给你一个char的数组,求有多少个连通分量。

典型的dfs。。【递归的比较水的说。。。。ps后来知道可以用bfs做。。。。哪天做到bfs再重新把题做一遍好了。。。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=105;
int ans=0,m,n;
char deposit[maxn][maxn];
void dfs(int x,int y)
{
    if(x<0||x>=m||y<0||y>=n||deposit[x][y]!='@')
        return;
    deposit[x][y]='*';
    dfs(x-1,y);
    dfs(x,y-1);
    dfs(x+1,y);
    dfs(x,y+1);
    dfs(x+1,y+1);
    dfs(x+1,y-1);
    dfs(x-1,y-1);
    dfs(x-1,y+1);
}
int main()
{
    while(scanf("%d%d",&m,&n),m)
    {
        ans=0;
        for(int i=0;i<m;i++)
        {
           scanf("%s",&deposit[i]);
        }


        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                if(deposit[i][j]=='@')
                {
                    ans++;
                    dfs(i,j);
                }
            }
        printf("%d\n",ans);
    }
}
【上篇】
【下篇】

抱歉!评论已关闭.