`
阿尔萨斯
  • 浏览: 4110459 次
社区版块
存档分类
最新评论

POJ 1562 Oil Deposits(DFS:求八连通分量个数)

 
阅读更多

POJ 1562 Oil Deposits(DFS:求八连通分量个数)

http://poj.org/problem?id=1562

题意:输入是一个R行C列的字符网格,表示油田,问你这个网格中有多少个由油田构成的连通分量.其中上下左右对角线相邻的网格油都算一个连通分量.

分析:典型的DFS,我们只需要对于网格中的每个油格,做一次DFS即可.(且还需要该油格之前没有被走过).

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100+5;
int R,C;
int cnt;//连通分量数目
char grid[maxn][maxn];
void dfs(int x,int y)
{
    if(x<0 || x>=R || y<0 || y>=C || grid[x][y]!='@')
        return ;
    grid[x][y]='*';//这样做我就少用一个vis数组标记该点被走过
    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",&R,&C)==2&&R)
    {
        cnt=0;
        for(int i=0;i<R;i++)
            scanf("%s",grid[i]);
        for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
        if(grid[i][j]=='@')
        {
            cnt++;
            dfs(i,j);
        }
        printf("%d\n",cnt);
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics