Minimum Moves to Reach Target with Rotations — Hard Problem & Solution

A snake two cells long lives on an n x n grid where 0 is an empty cell and 1 is a wall.

Difficulty: Hard
Topics: Arrays, Matrix, Breadth-First Search
Asked at: Amazon, Google
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A snake two cells long lives on an n x n grid where 0 is an empty cell and 1 is a wall. It starts horizontally on (0, 0) and (0, 1) and wants to end horizontally on (n-1, n-2) and (n-1, n-1).

In one move the snake can:

move right one cell, if the cells it moves into are empty (its orientation stays the same);
move down one cell, if the cells it moves into are empty (its orientation stays the same);
rotate clockwise, if it is horizontal on (r, c), (r, c+1) and both cells below it, (r+1, c) and (r+1, c+1), are empty — it becomes vertical on (r, c), (r+1, c);
rotate counter-clockwise, if it is vertical on (r, c), (r+1, c) and both cells to its right, (r, c+1) and (r+1, c+1), are empty — it becomes horizontal on (r, c), (r, c+1).

Return the minimum number of moves to reach the target, or -1 if it cannot be reached.

Example 1

Input: grid = [[0,0,0],[0,0,0],[0,0,0]]
Output: 3
Explanation: Down, down, right.

Example 2

Input: grid = [[0,0,0,0],[1,1,0,0],[0,0,0,0],[0,0,0,0]]
Output: 5
Explanation: The wall blocks the left half of row 1, so the snake slides right twice and then moves down three times.

Example 3

Input: grid = [[0,0,1],[1,0,0],[0,0,0]]
Output: -1
Explanation: The snake cannot move right, move down, or rotate from its starting place.

Constraints

2 <= n <= 100
0 <= grid[i][j] <= 1
the snake's two starting cells are empty

How to solve Minimum Moves to Reach Target with Rotations

Model the snake as a state (row, col, orientation) of its tail and run BFS; each of the four moves is an edge whose validity depends on one or two cells.

Approach

Start BFS from (0, 0, horizontal) with distance 0.
Horizontal at (r, c): moving right needs (r, c+2) empty; moving down and rotating clockwise both need (r+1, c) and (r+1, c+1) empty.
Vertical at (r, c): moving down needs (r+2, c) empty; moving right and rotating counter-clockwise both need (r, c+1) and (r+1, c+1) empty.
Return the distance when (n-1, n-2, horizontal) is dequeued; return -1 if the queue empties.

Why it works

All moves have the same cost, so BFS visits states in order of their distance from the start and the first time the target state is dequeued its distance is minimal. The state space is finite (at most 2n² states), so BFS terminates.

Complexity

Time — O(n²)
Space — O(n²)

Pitfalls

Orientation is part of the state: the same tail cell horizontal and vertical are different positions.
A rotation checks the diagonal cell (r+1, c+1) too, not just the cell the head swings into.
The target must be horizontal; being vertical in the bottom-right corner does not count.

Reference solution

Python

from typing import List
from collections import deque

def minimumMoves(grid: List[List[int]]) -> int:
    n = len(grid)
    target = (n - 1, n - 2, 0)
    dist = {(0, 0, 0): 0}
    q = deque([(0, 0, 0)])
    while q:
        r, c, o = q.popleft()
        d = dist[(r, c, o)]
        if (r, c, o) == target:
            return d
        nxt = []
        if o == 0:
            if c + 2 < n and grid[r][c + 2] == 0:
                nxt.append((r, c + 1, 0))
            if r + 1 < n and grid[r + 1][c] == 0 and grid[r + 1][c + 1] == 0:
                nxt.append((r + 1, c, 0))
                nxt.append((r, c, 1))
        else:
            if r + 2 < n and grid[r + 2][c] == 0:
                nxt.append((r + 1, c, 1))
            if c + 1 < n and grid[r][c + 1] == 0 and grid[r + 1][c + 1] == 0:
                nxt.append((r, c + 1, 1))
                nxt.append((r, c, 0))
        for s in nxt:
            if s not in dist:
                dist[s] = d + 1
                q.append(s)
    return -1

JavaScript

var minimumMoves = function(grid) {
    var n = grid.length;
    var dist = new Array(n * n * 2).fill(-1);
    var queue = [0];
    dist[0] = 0;
    var target = ((n - 1) * n + (n - 2)) * 2;
    for (var head = 0; head < queue.length; head++) {
        var s = queue[head];
        if (s === target) return dist[s];
        var o = s % 2, cell = (s - o) / 2, r = Math.floor(cell / n), c = cell % n;
        var nexts = [];
        if (o === 0) {
            if (c + 2 < n && grid[r][c + 2] === 0) nexts.push((r * n + c + 1) * 2);
            if (r + 1 < n && grid[r + 1][c] === 0 && grid[r + 1][c + 1] === 0) {
                nexts.push(((r + 1) * n + c) * 2);
                nexts.push((r * n + c) * 2 + 1);
            }
        } else {
            if (r + 2 < n && grid[r + 2][c] === 0) nexts.push(((r + 1) * n + c) * 2 + 1);
            if (c + 1 < n && grid[r][c + 1] === 0 && grid[r + 1][c + 1] === 0) {
                nexts.push((r * n + c + 1) * 2 + 1);
                nexts.push((r * n + c) * 2);
            }
        }
        for (var t = 0; t < nexts.length; t++) {
            if (dist[nexts[t]] === -1) { dist[nexts[t]] = dist[s] + 1; queue.push(nexts[t]); }
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal