今天的題目是計算有幾個小島 200. Number of Islands:題目給定一個二維陣列,1 : 陸地、0 : 海洋,水平垂直有連接的就是一座島嶼,以下面測資為例就是三個小島。

Input:
11000
11000
00100
00011

Output: 3

地圖遍尋的題目看來就是需要 DFS/BFS 出馬解決。我們另外準備一個陣列紀錄是否拜訪過,程式開始一一遍尋每個點,如果曾經拜訪或是海洋就跳過,不然就 DFS/BFS 把相鄰的都跑一遍,最後就可以算出有幾個小島了。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;
        vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size()));
        int res = 0;

        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[i].size(); j++){
                if(grid[i][j] == '0' || visit[i][j] == 1) continue;
                checkIsland(grid, visit, i, j);
                res++;
            }
        }

        return res;
    }

    void checkIsland(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
        visited[x][y] = true;
        checkIsland(grid, visited, x - 1, y);
        checkIsland(grid, visited, x + 1, y);
        checkIsland(grid, visited, x, y - 1);
        checkIsland(grid, visited, x, y + 1);
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料