Show problems as
Classic problem #1559MediumArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Detect Cycles in 2D Grid

Real-world version: Closed Loop Of Matching Floor Tiles
Tracked in this browser only
Read Detect Cycles in 2D Grid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A floor is tiled in a rectangle, and grid[r][c] is a lowercase letter naming the colour of the tile in row r, column c. All rows have the same width.

A closed loop is a route across tiles that all share one colour. Formally it is a sequence of tiles t0, t1, ..., tL where

  • every tile in the sequence has the same colour;
  • consecutive tiles share an edge, so each step moves one square up, down, left or right;
  • tL is the same tile as t0, so the route comes back to where it began;
  • L is at least 4, so the route takes four or more steps;
  • no step goes straight back to the tile the route arrived from, that is t(i+1) is never the same tile as t(i-1).

The last rule stops a route from bouncing between two neighbours and calling it a loop.

Return true when the floor contains at least one closed loop, and false otherwise.

Examples

Example 1

Input
grid = [["r", "r", "s"], ["r", "r", "t"]]
Output
true

The four `r` tiles at rows 0 and 1, columns 0 and 1, can be walked as (0,0), (0,1), (1,1), (1,0) and back to (0,0). That is four steps, each between edge-sharing tiles of the same colour, and no step reverses the one before it.

Example 2

Input
grid = [["m", "m"], ["m", "p"]]
Output
false

The three `m` tiles form a bend from (0,1) through (0,0) to (1,0). Leaving (1,0) the only matching neighbour is (0,0), which is where the route arrived from, so the route dead-ends and never gets back to its start.

Example 3

Input
grid = [["k", "k", "k"], ["k", "w", "k"], ["k", "k", "k"]]
Output
true

The eight `k` tiles ring the single `w` tile, and walking that ring once round takes eight steps between edge-sharing `k` tiles and returns to its start. A loop does not have to be a solid block.

Constraints

  • 1 <= grid.length <= 500
  • 1 <= grid[i].length <= 500
  • Every row of grid has the same length.
  • grid[r][c] is a lowercase English letter.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def has_tile_loop(grid: list[list[str]]) -> bool:
Java
public boolean hasTileLoop(char[][] grid)

More on the same topics