题目地址

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

简析

循环整个二维数组中的点，如果这个点为1，则将岛屿总数+1，同时从这个点出发进行搜索，把每个它能到达的点都设为2。这样同一片岛屿，就只产生一次+1。

1 移动方式定义

属于迷宫类问题，所有迷宫类问题，都要根据行走方式定义一个关于行走方式的数组，数组就两种方式：

• 只能垂直移动，不能斜着走

int mv[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//要么横向加减1，竖直方向不动；要么纵坐标加减1，水平方向不动；

• 可以斜着走

int mv[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,-1},{1,1},{-1,1},{-1,-1}};//在上述基础上,增加斜着的变化，即横纵都加减一，共四种情况

2 确定for循环范围

任何复杂问题都由简单问题组合而成，解决每一个简单问题，复杂问题自然迎刃而解。参见另一篇搜索与回溯综述，第一步，我们先确定每个可能的选择的范围，即for循环的范围。
此题只能垂直移动，顾for循环范围为0~4，就是走mv数组中的一步。

for(int i=0;i<4;i++){
            int xx=x+mv[i][0];
            int yy=y+mv[i][1];
}

3 判断是否可选

选择的范围有了，但并不是范围内的任何一个点都可以使用，我们要加一个判断，如果判断条件过于复杂，则要增加一个函数。
此处的判断需要判断两件事，

• 一是下标有没有超过给定数组的范围。
• 二是判断这个点是否是1，如果是0则表示水面，不用处理

if(xx>=0&&xx<grid.size()&&yy>=0&&yy<grid[xx].size()&&grid[xx][yy]=='1')

4 选择后的处理

if条件成立后，

• 把这个点标记成2，表示这块地已经到达过了，
• 搜索下一层
• 不用回溯，因为只要标记过了就可以了。

5 完整代码

class Solution {
public:
    int mv[4][4]={{1,0},{-1,0},{0,1},{0,-1}};
    int numIslands(vector<vector<char>>& grid) {
        int count=0;
        for(int i=0;i<grid.size();i++)
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]=='1'){
                    grid[i][j]='2';
                    search(grid,i,j);
                    count++;
                }
            }
        return count;
    }
    void search(vector<vector<char>>& grid,int x,int y){
        for(int i=0;i<4;i++){
            int xx=x+mv[i][0];
            int yy=y+mv[i][1];
            if(xx>=0&&xx<grid.size()&&yy>=0&&yy<grid[xx].size()&&grid[xx][yy]=='1'){
                grid[xx][yy]='2';
                search(grid,xx,yy);
            }
        }
    }
};