1559. Detect Cycles in 2D Grid¶
题目信息¶
- 题号:
1559
- 难度:
Medium
- 主题:
网格、图搜索、环检测
- 原题:
- 重点:
环由至少四个值相同的格子组成,相邻格必须共享边;路径不能立即返回上一个格子
题目重述¶
给定字符矩阵 grid。上下左右相邻且字符相同的格子之间可以连边。
请判断该图中是否存在一个环:从某格出发,经过至少四个格子后回到起点,路径中除起点与终点外不能重复使用格子,并且不能在一步后立即沿原边返回。
1 <= grid.length, grid[i].length <= 500,字符均为小写英文字母。
自建示例¶
同字符方形边界构成长度四的环:
输入:grid = [["a","a"],["a","a"]]
输出:true
解释:四个格子沿矩形边界首尾相连。
所有相邻字符都不同时不存在环:
输入:grid = [["a","b"],["c","d"]]
输出:false
解释:没有两个相同字符的相邻格。