首页 > 其他 > 详细

Leetcode 200 Number of Islands DFS

时间:2016-01-15 12:48:14      阅读:176      评论:0      收藏:0      [点我收藏+]

统计联通区域块的个数,简单dfs

class Solution {
public:
    int m, n;
    bool is_in(int x, int y)
    {
        return (x < m ) && (x >= 0) && (y < n ) && (y >= 0);
    }

    void dfs(std::vector<std::vector<char>> &board, int x, int y)
    {
        board[x][y] = 0;
        int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int i = 0; i < 4; ++i){
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (is_in(tx, ty) && board[tx][ty] == 1)
            {
                dfs(board, tx, ty);
            }
        }
    }

    int numIslands(std::vector<std::vector<char>>& grid)
    {
        m = grid.size();
        if (m == 0) return 0;
        n = grid[0].size();
        if (n == 0) return 0;
        int ans = 0;
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (grid[i][j] == 1){
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
};

 

Leetcode 200 Number of Islands DFS

原文:http://www.cnblogs.com/onlyac/p/5132757.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!