1559. Detect Cycles in 2D Grid

题目信息

题号:

1559

难度:

Medium

主题:

网格、图搜索、环检测

原题:

LeetCode 1559

重点:

环由至少四个值相同的格子组成,相邻格必须共享边;路径不能立即返回上一个格子

题目重述

给定字符矩阵 grid。上下左右相邻且字符相同的格子之间可以连边。

请判断该图中是否存在一个环:从某格出发,经过至少四个格子后回到起点,路径中除起点与终点外不能重复使用格子,并且不能在一步后立即沿原边返回。

1 <= grid.length, grid[i].length <= 500,字符均为小写英文字母。

自建示例

同字符方形边界构成长度四的环:

输入:grid = [["a","a"],["a","a"]]
输出:true
解释:四个格子沿矩形边界首尾相连。

所有相邻字符都不同时不存在环:

输入:grid = [["a","b"],["c","d"]]
输出:false
解释:没有两个相同字符的相邻格。