LeetCode200. Number of Islands（搜索）

Medium
Accepted：329,727
Submissions：805,856

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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

链接

https://leetcode.com/problems/number-of-islands

题意

给定一个二维平面地图，其中0代表水域，1代表陆地，计算岛的数量，岛就是连（水平/竖直）在一起的陆地。

题解

一道比较简单的搜索题，从值为1的位置搜起，把它和周围四个方向的位置值为1的都标记为false，直到连在一起的整块都被标记为false，然后从值为1的位置继续搜。记录两层循环中搜索的次数就是答案。

代码

Runtime: 16 ms, faster than 98.76% of C++ online submissions for Number of Islands.
Memory Usage: 10.7 MB, less than 100.00% of C++ online submissions for Number of Islands.

class Solution {
private:
    int n, m;
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    vector <vector<bool> > vis;
    bool check(int x, int y)
    {
        return x < n && x >= 0 && y >= 0 && y < m;
    }
    void solve(const vector<vector<char>>& grid, int startx, int starty)
    {
        vis[startx][starty] = true;
        for (int i = 0; i < 4; ++i)
        {
            int newx = startx + dir[i][0];
            int newy = starty + dir[i][1];
            if (check(newx, newy) && !vis[newx][newy] && grid[newx][newy] == '1')
                solve(grid, newx, newy);
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty())
            return 0;
        n = grid.size(), m = grid[0].size();
        vis = vector <vector<bool> >(n + 1, vector<bool>(m + 1, false));
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (grid[i][j] == '1' && !vis[i][j]) 
                {
                    ans++;
                    solve(grid, i, j);
                }
        return ans;
    }
};

The end.
2019年4月13日星期六