JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
题目大意:有一个大小为N*M的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼?
(八连通指下图中相当于W的*)
***
*W*
***
题目分析;从任意的W开始,不同的用一个vis数组标记是否访问过。一次DFS后与初始的这个W相连的W就都被标记过了。因此知道途中不再存在W为止,总共进行DFS的次数就是答案了。
#include <cstdio>
#include <cstring>

const int maxn = 101;

int n, m, ans;
char g[maxn][maxn];
bool vis[maxn][maxn];

void dfs(int x, int y) {
    if(vis[x][y] == true || g[x][y] != 'W') return;
    vis[x][y] = true;
    for(int i=-1;i<=1;i++)
    for(int j=-1;j<=1;j++) {
        if(!i && !j || x + i < 0 || x + i >= n || y + j < 0 || y + j >= m) continue;
        dfs(x+i, y+j);
    }
    return;
}

int main() {
    while(~scanf("%d%d" , &n, &m)) {
        for(int i=0;i<n;i++) {
            scanf("%s", g[i]);
            memset(vis+i, falsesizeof(bool)*(m));
        }
        ans = 0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j] == 'W' && !vis[i][j]) {
                    ans ++;
                    dfs(i, j);
                }
        printf("%d\n", ans);
    }
    return 0;
}
posted on 2015-02-11 15:29 JulyRina 阅读(397) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理