題目

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

解題之法

class Solution {
public:
    int numIslands(vector<vector<char> > &grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool> > visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    numIslandsDFS(grid, visited, i, j);
                    ++res;
                }
            }
        }
        return res;
    }
    void numIslandsDFS(vector<vector<char> > &grid, vector<vector<bool> > &visited, int x, int y) {
        if (x < 0 || x >= grid.size()) return;
        if (y < 0 || y >= grid[0].size()) return;
        if (grid[x][y] != '1' || visited[x][y]) return;
        visited[x][y] = true;
        numIslandsDFS(grid, visited, x - 1, y);
        numIslandsDFS(grid, visited, x + 1, y);
        numIslandsDFS(grid, visited, x, y - 1);
        numIslandsDFS(grid, visited, x, y + 1);
    }
};

分析

這道求島嶼數(shù)量的題的本質(zhì)是求矩陣中連續(xù)區(qū)域的個數(shù)，很容易想到需要用深度優(yōu)先搜索DFS來解。
我們需要建立一個visited數(shù)組用來記錄某個位置是否被訪問過，對于一個為‘1’且未被訪問過的位置，我們遞歸進(jìn)入其上下左右位置上為‘1’的數(shù)，將其visited對應(yīng)值賦為true，繼續(xù)進(jìn)入其所有相連的鄰位置，這樣可以將這個連通區(qū)域所有的數(shù)找出來，并將其對應(yīng)的visited中的值賦true，找完次區(qū)域后，我們將結(jié)果res自增1，然后我們在繼續(xù)找下一個為‘1’且未被訪問過的位置，以此類推直至遍歷完整個原數(shù)組即可得到最終結(jié)果。