LeetCode/二维网格图中探测环

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在相同值形成的环。
一个环是一条开始和结束于同一个格子的长度大于等于 4 的路径。对于一个给定的格子
你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有相同的值

1. 深度优先

遍历每一个节点，从每一个节点递归周围相同节点
同时使得深度加一，记录每个节点的深度，当再次碰到已遍历节点时，计算长度，判断是否满足条件
遍历失败要剔除该节点（这样不用遍历重复路径）

class Solution {
public:
    int m,n;
    vector<vector<int>> len;
    int dir[5] = {0,1,0,-1,0};
    bool containsCycle(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        len.resize(m,vector<int>(n));
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(grid[i][j]=='0') continue;//已经遍历过
                if(dfs(grid,i,j,1)) return true;
            }
        return false;
    }
    bool dfs(vector<vector<char>>& grid,int x,int y,int curlen){
        if(len[x][y]>0){//之前已经遍历过,不再扩张
            if(curlen-len[x][y]>=4) return true;//存在大于等于4的环
            else return false;
        }
        len[x][y] = curlen;//记录当前长度
        for(int i=0;i<4;i++){//遍历四个方向
            int nx = x + dir[i];
            int ny = y + dir[i+1];
            if(nx<0||ny<0||nx>=m||ny>=n) continue;//超出边界
            if(grid[nx][ny]!=grid[x][y]) continue;//不符合条件
            if(dfs(grid,nx,ny,curlen+1)) return true;
        }
        len[x][y] = 0;//撤销选择
        grid[x][y] = '0';//剪枝，不再遍历已遍历的
        return false;
    }
};