给你一个二维字符网格数组 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;
}
};
标签:遍历,int,网格,len,节点,二维,grid,curlen,LeetCode
From: https://www.cnblogs.com/929code/p/17391064.html