[LeetCode]200.Number of Islands

本文主要是介绍[LeetCode]200.Number of Islands，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

思路

可以参考：Find the number of islands
有一点不同的是本题目只用考虑四个方向，而参考题目是考虑了8个方向。

代码

/*------------------------------------------------------
*   日期：2014-04-10
*   作者：SJF0115
*   题目: 200.Number of Islands
*   网址：https://leetcode.com/problems/number-of-islands/
*   结果：AC
*   来源：LeetCode
*   博客：
--------------------------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;class Solution {
public:int numIslands(vector<vector<char>> &grid) {// 行数int row = grid.size();if(row == 0){return 0;}//if// 列数int col = grid[0].size();if(col == 0){return 0;}//ifint count = 0;for(int i = 0;i < row;++i){for(int j = 0;j < col;++j){// 如果是1且没有被访问过则发现一个新的岛屿if(grid[i][j] == '1'){// 以该岛屿做深度遍历DFS(grid,row,col,i,j);++count;}//if}//for}//forreturn count;}
private:// grid 地图 row 行数 col 列数 (x,y)当前坐标void DFS(vector<vector<char> > &grid,int row,int col,int x,int y){if(x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == '0'){return;}//ifgrid[x][y] = '0';// rightDFS(grid,row,col,x,y+1);// leftDFS(grid,row,col,x,y-1);// topDFS(grid,row,col,x-1,y);// bottomDFS(grid,row,col,x+1,y);}
};int main() {Solution solution;vector<vector<char> > grid ={{'1', '1', '0', '0', '0'},{'1', '1', '0', '0', '0'},{'0', '0', '1', '0', '0'},{'0', '0', '0', '1', '1'}};cout<<solution.numIslands(grid)<<endl;return 0;
}