首页 > 其他分享 >LeetCode/二维网格图中探测环

LeetCode/二维网格图中探测环

时间:2023-05-11 15:14:47浏览次数:46  
标签:遍历 int 网格 len 节点 二维 grid curlen 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;
    }
};

标签:遍历,int,网格,len,节点,二维,grid,curlen,LeetCode
From: https://www.cnblogs.com/929code/p/17391064.html

相关文章

  • LeetCode 459. 重复的子字符串
    题目链接:LeetCode459.重复的子字符串题意:给定一个非空的字符串s,检查是否可以通过由它的一个子串重复多次构成。解题思路:本题就是kmp算法的经典应用,n-next[n]是原字符串的最小周期完整代码如下:funcrepeatedSubstringPattern(sstring)bool{//kmp的经典应用:求......
  • LeetCode 151. 反转字符串中的单词
    题目链接:LeetCode151.反转字符串中的单词题意:给你一个字符串s,请你反转字符串中单词的顺序。解题思路:如果我们将整个字符串都反转过来,那么单词的顺序指定是倒序了,只不过单词本身也倒序了,那么再把单词反转一下,单词不就正过来了。所以解题思路如下:移除多余空格将整个字......
  • LeetCode 541. 反转字符串 II
    题目链接:LeetCode541.反转字符串II题意:给定一个字符串s和一个整数k,从字符串开头算起,每计数至2k个字符,就反转这2k字符中的前k个字符。如果剩余字符少于k个,则将剩余字符全部反转。如果剩余字符小于2k但大于或等于k个,则反转前k个字符,其余字符保持原样。......
  • LeetCode 剑指 Offer 05. 替换空格
    题目链接:LeetCode剑指Offer05.替换空格题意:输入一个字符串s,然后将s中的每个空格替换成"%20"。解题思路:直接遍历一遍字符串,如果当前字符不是空格,则加入到结果中如果是空格,则将“%20”加入到结果集完整代码如下:funcreplaceSpace(sstring)string{varres......
  • LeetCode 344. 反转字符串
    题目链接:LeetCode344.反转字符串题意:输入一个字符串,将其在原地进行反转。解题思路:对于字符串,我们定义两个指针(也可以说是索引下标),一个从字符串前面,一个从字符串后面,两个指针同时向中间移动,并交换元素。完整代码如下:funcreverseString(s[]byte){//原地反转字符......
  • leetcode bash题--统计词频
    写一个bash脚本以统计一个文本文件words.txt中每个单词出现的频率。为了简单起见,你可以假设:words.txt只包括小写字母和''。每个单词只由小写字母组成。单词间由一个或多个空格字符分隔。示例:假设words.txt内容如下:thedayissunnythethethesunnyisis你的脚......
  • LeetCode刷题记录|LeetCode热题100|136.只出现一次的数字(easy)
    题目描述:给你一个非空整数数组nums,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。时间复杂度:O(n),其中n是数组长度。只需要对数组遍历一次。空间复......
  • leetcode 626 換座位
    leetcode626換座位SELECT(CASEWHENMOD(id,2)!=0ANDcounts!=idTHENid+1WHENMOD(id,2)!=0ANDcounts=idTHENidELSEid-1END)ASid,studentFROMseat,(SELECTCOUNT(*)AScountsFRO......
  • leetcode 619 只出現一次的最大數字
    leetcode619只出現一次的最大數字 selectmax(num)asnumfrom(selectnumasnumfromMyNumbersgroupbynumhavingcount(num)=1)asmn selectif(count(num)=1,num,null)asnumfromMyNumbersgroupbynumorderbynumdesclimit0,......
  • leetcode 1679
    1.排序双指针先排序sort(nums.begin(),nums.end());在双指针查找while(left<right){if(nums[left]+nums[right]<k){left++;}elseif(nums[left]+nums[right]>k){right--;}else{left++;right--;count++;}}2.......