題目： LeetCode - 200. Number of Islands

題目說明

給一個二維的陣列當作 2d 地圖，1 代表土地，0 代表海水，求出地圖中島嶼的數量。( 上下左右相鄰的 1 代表同一座島 )

解題思路

將整個地圖訪問一次，若碰到 1 就使用遞迴的概念將相鄰的 1 都設成 0，做完一次代表找到一個島。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    void mark(vector<vector<char>>& grid, int i, int j, int height, int width)
    {
        if(i < 0 || j < 0 || i >= height || j >= width || grid[i][j] != '1')
            return;
        grid[i][j] = '0';
        mark(grid, i, j + 1, height, width);
        mark(grid, i, j - 1, height, width);
        mark(grid, i + 1, j, height, width);
        mark(grid, i - 1, j, height, width); 
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int height = grid.size();
        if(!height)    
            return 0;
        int width = grid[0].size(), numberOfRegions = 0;
        for(int i = 0; i < height; ++i)
            for(int j = 0; j < width; ++j)
                if(grid[i][j] == '1')
                    mark(grid, i, j, height, width),    ++numberOfRegions;
        return numberOfRegions;
    }
};