leetcode--200--岛屿数量

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

示例 1:

输入:
11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3

链接：https://leetcode-cn.com/problems/number-of-islands

思路：
1、这道题可以用dfs来解决。遍历这个数组，如果当前元素为1，则进入感染函数，并将岛屿数+1
2、感染函数是一个dfs搜索函数，分别将当前元素上下左右的元素均进行递归感染，并将当前元素的值设置为2这样下次就不会走到这个位置

Python代码：

class Solution(object):

    def __init__(self):
        self.ans = 0
    
    def infect(self, grid, i, j):
        if (i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]!='1'):
            return 
        
        grid[i][j] = 2
        self.infect(grid, i+1, j)
        self.infect(grid, i-1, j)
        self.infect(grid, i, j+1)
        self.infect(grid, i, j-1)

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        m = len(grid)
        if m==0:
            return 0
        n = len(grid[0])
        if n==0:
            return 0

        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    self.infect(grid, i, j)
                    self.ans += 1
        return self.ans

C++代码：

class Solution {
public:

    void infect(vector<vector<char>>& grid, int i, int j){
        if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]!='1'){
            return ;
        }
        grid[i][j] = 2;
        infect(grid, i+1, j);
        infect(grid, i-1, j);
        infect(grid, i, j+1);
        infect(grid, i, j-1);
    }

    int numIslands(vector<vector<char>>& grid) {
        int ans=0;
        int m = grid.size();
        if (m==0) return 0;
        int n = grid[0].size();
        if (n==0) return 0;

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]=='1'){
                    infect(grid, i, j);
                    ans ++ ;
                }
            }
        }
        return ans;
    }
};