0743MediumArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Closed Loop Of Matching Floor Tiles

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def has_tile_loop(grid: list[list[str]]) -> bool:

Java

public boolean hasTileLoop(char[][] grid)

The intended approach

Time O(rows * cols) up to the near-constant disjoint-set lookup factor.Space O(rows * cols) for the forest.

Read the floor as a graph whose vertices are tiles and whose edges join edge-sharing tiles of the same colour. Because every step of a route moves between neighbours and never reverses immediately, a closed loop in the statement's sense is exactly a cycle in that graph, and the shortest cycle a grid can hold already spans four tiles. So sweep the tiles in reading order, keeping a disjoint-set forest, and for each tile try to join it to its upper and left neighbours when the colours match. Each edge of the graph is offered exactly once this way, and the first time a join is asked for between two tiles already in the same group, that edge closes a cycle and the answer is `true`. The sweep is a flat double loop, so nothing recurses and a 500 by 500 floor is safe.

Pythonentry point: has_tile_loop

def has_tile_loop(grid):
    # Join each tile to the neighbour above it and to its left when the colours
    # match. A loop exists exactly when a join is asked for between two tiles
    # already in the same joined group.
    # O(rows * cols) time up to the near-constant disjoint-set factor.
    rows = len(grid)
    cols = len(grid[0])
    root = list(range(rows * cols))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for r in range(rows):
        row = grid[r]
        for c in range(cols):
            here = r * cols + c
            colour = row[c]
            if r > 0 and grid[r - 1][c] == colour:
                a, b = find((r - 1) * cols + c), find(here)
                if a == b:
                    return True
                root[a] = b
            if c > 0 and row[c - 1] == colour:
                a, b = find(r * cols + c - 1), find(here)
                if a == b:
                    return True
                root[a] = b
    return False

The obvious version

Backtracking straight from the definition: from every tile, walk routes of matching tiles that never revisit a tile and never step back to the tile just left, and succeed when a route returns to its own starting tile after four or more steps. Exponential, but it encodes the rules literally.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_has_tile_loop(grid):
    """Walk every simple route of matching tiles out of every starting tile,
    never stepping straight back, and report success the moment a route returns
    to its own start after four or more steps."""
    rows = len(grid)
    cols = len(grid[0])

    def walk(start, cell, came_from, steps, seen):
        r, c = cell
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] != grid[start[0]][start[1]]:
                continue
            if (nr, nc) == came_from:
                continue
            if (nr, nc) == start:
                if steps + 1 >= 4:
                    return True
                continue
            if (nr, nc) in seen:
                continue
            seen.add((nr, nc))
            if walk(start, (nr, nc), cell, steps + 1, seen):
                return True
            seen.discard((nr, nc))
        return False

    for r in range(rows):
        for c in range(cols):
            if walk((r, c), (r, c), None, 0, {(r, c)}):
                return True
    return False

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in