【LeetCode】 200. Number of Islands

Description

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.

給予一個用'1'(陸地)和'0'(水)組成的2d的網格地圖，計算有多少島嶼。一個島嶼被水所圍繞並由垂直或水平鄰近的陸地所組成。你可以假設網格中的四個邊界都被水給包圍。

Example:

Example 1:

Input:
11110
11010
11000
00000

Output: 1


Example 2:

Input:
11000
11000
00100
00011

Output: 3

Solution

• 寫一個DFS或BFS的演算法，去將相鄰的陸地都變成水。
  • 注意邊界處理。
• 只有第一次變成水的時候需要將計數器加一，最後回傳計數器即可。

Code

class Solution {
public:
    
    void toWater(int x, int y, vector<vector<char>>& grid)
    {
        grid[y][x] = '0';
        if(x != 0 && grid[y][x - 1] == '1') toWater(x - 1, y, grid);
        if(x != grid[0].size() - 1 && grid[y][x + 1] == '1') toWater(x + 1, y, grid);
        if(y != 0 && grid[y - 1][x] == '1') toWater(x, y - 1, grid);
        if(y != grid.size() - 1 && grid[y + 1][x] == '1') toWater(x, y + 1, grid);
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[0].size(); j++)
                if(grid[i][j] == '1')
                {
                    count++;
                    toWater(j, i, grid);
                }
        
        return count;
    }
};

tags: LeetCode C++