Quick Overview

This question evaluates competency in grid-based pathfinding, graph modeling, and algorithmic complexity analysis for computing shortest paths in discrete spaces.

Compute maze score using shortest path

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given a grid-based maze game. - The maze is an `R x C` grid of characters: - `'#'` = wall (cannot pass) - `'.'` = empty cell - `'S'` = current player position (exactly one) - `'E'` = exit/goal (exactly one) - The game “score” for a state is defined as the length of the shortest path (minimum number of moves) from `S` to `E`, moving 4-directionally (up/down/left/right) and not passing through walls. - If `E` is unreachable, return `-1`. Write a function that takes the maze grid and returns the score. Clarify in your solution: - Time and space complexity - How you would adapt it if the game state were provided separately as `(startRow, startCol)` instead of embedding `'S'` in the grid.

Quick Answer: This question evaluates competency in grid-based pathfinding, graph modeling, and algorithmic complexity analysis for computing shortest paths in discrete spaces.

You are given a grid-based maze game represented as a list of strings. Each cell contains one of the following characters: '#' for a wall, '.' for an empty cell, 'S' for the player's current position, and 'E' for the exit. The maze score is defined as the length of the shortest path from 'S' to 'E', moving only up, down, left, or right, and never passing through walls. If the exit cannot be reached, return -1.

Constraints

  • 1 <= R, C <= 200
  • All rows have the same length
  • There is exactly one 'S' and exactly one 'E'
  • Movement is allowed only in 4 directions: up, down, left, right

Examples

Input: (['S..', '.#.', '..E'],)

Expected Output: 4

Explanation: A shortest path is right, right, down, down for a total of 4 moves.

Input: (['S#.', '###', '.E.'],)

Expected Output: -1

Explanation: Walls block every possible route from S to E.

Hints

  1. This is an unweighted shortest-path problem on a grid, so consider breadth-first search.
  2. Once you visit a cell for the first time in BFS, you have already found the shortest path to it.

Loading coding console...