class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    //本题的思路为采用深度优先遍历，如果当前来到的是1且没有走过那就看这个位置的上下左右哪个位置是1就往哪走
    //用used数组标记一个位置是否被走过
    int res=0;//最终的返回结果
    bool used[10000][10000];
    int solve(vector<vector<char> >& grid) {
        // write code here
        int rows=grid.size();//行数
        int cows=grid[0].size();//列数
        for(int i=0;i<rows;i++){
            for(int j=0;j<cows;j++)
                used[i][j]=true;//初始化
        }
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]=='1'&&used[i][j]==true){
                    res++;
                    used[i][j]=false;
                    process(grid, i, j);
                }
            }
        }
        return res;
    }
    //该函数的含义为从row行cow列开始走，只能走为1且没走过的地方，把所有能走的地方走一次且仅走一次
    void process(vector<vector<char> >grid,int row,int cow)
    {
        //base case
        //当来到一个地方时它的上下左右全都是0或者都走过此时说明已经把所有能走的地方都走了一遍，返回
        if(row>=grid.size()||cow>=grid[0].size())//越界
            return;
        //可以往上走
        if(row-1>=0&&grid[row-1][cow]=='1'&&used[row-1][cow]){//说明此时可以往上走
            used[row-1][cow]=false;//修改used数组，说明这个位置已经被走过
            process(grid, row-1, cow);
        }
        //注意这里不能用else if
        //如果可以往下走
        if(row+1<grid.size()&&grid[row+1][cow]=='1'&&used[row+1][cow]){
            used[row+1][cow]=false;
            process(grid, row+1, cow);
        }
        //可以往左走
        if(cow-1>=0&&grid[row][cow-1]=='1'&&used[row][cow-1]){
            used[row][cow-1]=false;
            process(grid, row, cow-1);
        }
        //可以往右走
        if(cow+1<grid[0].size()&&grid[row][cow+1]=='1'&&used[row][cow+1]){
            used[row][cow+1]=false;
            process(grid, row, cow+1);
        }
        //上下左右四个方向能走的都走了一遍，返回
        return;
    }
};