Leetcode:200.岛屿个数

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

示例 1:

示例 2:

解题思路：

连通域识别，深度优先搜索。遍历图中的每一个元素，如果遇到1，并且没有访问，那么在该点搜索一个连通域。最终输出整个区域中连通域的个数。

Leetcode:200.岛屿个数

C++代码
class Solution { public: int numIslands(vector<vector<char>>& grid) { //计算连通域的个数 int nums = 0,i,j; sizex = grid.size(); if (sizex == 0 ) return 0; sizey = grid[0].size(); if (sizey == 0) return 0; copy_grid = grid; visit= vector<vector<bool>>(sizex, vector<bool>(sizey, false)); for (i = 1; i <= sizex; i++) { for (j = 1; j <= sizey; j++) { if (copy_grid[i - 1][j - 1] == '1'&& visit[i - 1][j - 1] == false) { find_area(i, j); nums++; } } } return nums; } private: void find_area(int x, int y) { visit[x - 1][y - 1] = true; if (x > 1 && visit[x - 2][y - 1] == false && copy_grid[x - 2][y - 1] == '1') find_area(x - 1, y); if (x < sizex&&visit[x][y - 1] == false && copy_grid[x][y - 1] == '1') find_area(x + 1, y); if (y > 1 && visit[x - 1][y - 2] == false && copy_grid[x - 1][y - 2] == '1') find_area(x, y - 1); if (y < sizey&&visit[x - 1][y] == false && copy_grid[x - 1][y] == '1') find_area(x, y + 1); } private: vector<vector<bool>> visit; vector<vector<char>> copy_grid; int sizex, sizey; };