[LeetCode]200.Number of Islands

题目

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

思路

可以参考：Find the number of islands
有一点不同的是本题目只用考虑四个方向，而参考题目是考虑了8个方向。

代码

/*------------------------------------------------------
*   日期：2014-04-10
*   作者：SJF0115
*   题目: 200.Number of Islands
*   网址：https://leetcode.com/problems/number-of-islands/
*   结果：AC
*   来源：LeetCode
*   博客：
--------------------------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>> &grid) {
        // 行数
        int row = grid.size();
        if(row == 0){
            return 0;
        }//if
        // 列数
        int col = grid[0].size();
        if(col == 0){
            return 0;
        }//if
        int count = 0;
        for(int i = 0;i < row;++i){
            for(int j = 0;j < col;++j){
                // 如果是1且没有被访问过则发现一个新的岛屿
                if(grid[i][j] == '1'){
                    // 以该岛屿做深度遍历
                    DFS(grid,row,col,i,j);
                    ++count;
                }//if
            }//for
        }//for
        return count;
    }
private:
    // grid 地图 row 行数 col 列数 (x,y)当前坐标
    void DFS(vector<vector<char> > &grid,int row,int col,int x,int y){
        if(x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == '0'){
            return;
        }//if
        grid[x][y] = '0';
        // right
        DFS(grid,row,col,x,y+1);
        // left
        DFS(grid,row,col,x,y-1);
        // top
        DFS(grid,row,col,x-1,y);
        // bottom
        DFS(grid,row,col,x+1,y);
    }
};

int main() {
    Solution solution;
    vector<vector<char> > grid =
    {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    cout<<solution.numIslands(grid)<<endl;
    return 0;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>