一.方法介绍

  1. 网格问题即为二维矩阵，在二维网格中进行遍历

    用dfs解决网格问题框架

  2. 解决递归过程中的重复遍历问题的方法：额外申请visited[][]矩阵进行标记；对原有grid[][]进行某种修改，来判断当前{i,j}是否已经访问过，是否需要从当前(i,j)往四个方向递归。

    1. void Dfs(int[][] grid ,int i, int j){
    2.  //1.边界base case判断，超过则返回
    3.  if ()
    5.  //2.对当前grid[i][j]进行标记，防止重复遍历（或者进行相关操作）
    7.  //3.深优
    8.  Dfs(grid,i+1,j);
    9.  Dfs(grid,i-1,j);
    10.  Dfs(grid,i,j+1);
    11.  Dfs(grid,i,j-1);
    12.  return;
    13. }

二.相关题目

200.岛屿数量

题目链接

  1. 主函数对grid遍历，每遍历到一个’1’，就从这个位置开始，利用Dfs把该位置接壤的所有’1’都变成0，结束Dfs后，count++;

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

 }
 int numIslands(vector<vector<char>>& grid) {
     int i,j,count=0,row=grid.size(),col=grid[0].size();
     for(i=0;i<row;i++) {
         for (j=0;j<col;j++) {
             if (grid[i][j]=='1'){
                 Dfs(grid,i,j);
                 ++count;
             }
         }
     }
     return count;
 }