LeetCode 200.岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:

输出: 1

示例 2:

输入:

输出: 3

和之前的DFS寻找最短路径不同，这道题没有了终点，所以不需要我们回退时，将点设置为可行。首先找到一个可行点，然后将这个可行点可以到达的地方全部感染，这就是一个岛。我们再搜寻是否有其他未感染可行点，继续感染。

#include <iostream>

#include <vector>

using namespace std;

int arr[][] = { , , -, , , , , - };

void infact(vector<vector<char> >& grid, int i, int j) {

    if (i <  || i >= grid.size() || j <  || j >= grid[].size() || grid[i][j] != '') {

        return;

    }

    for (int k = ; k < ; ++k) {//上下左右全部都要搜寻完

        grid[i][j] = '';

        int ni = i + arr[k][];

        int nj = j + arr[k][];

        infact(grid, ni, nj);

    }

}

int numIslands(vector<vector<char>>& grid) {

    int island = ;

    for (size_t i = ; i < grid.size(); ++i) {

        for (size_t j = ; j < grid[].size(); ++j) {

            if (grid[i][j] == '') {

                infact(grid, i, j);

                ++island;

            }

        }

    }

    return island;

}

int main()

{

    vector<vector<char> >  map = {

    {'','','','',''},

    {'','','','',''},

    {'','','','',''},

    {'','','','',''}

    };

    cout << numIslands(map);

    system("PAUSE");

    return ;

}