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.
Overview: This question evaluates competency in grid-based pathfinding, graph modeling, and algorithmic complexity analysis for computing shortest paths in discrete spaces.
Read the full Airbnb Software Engineer interview experience this question came from
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
- This is an unweighted shortest-path problem on a grid, so consider breadth-first search.
- Once you visit a cell for the first time in BFS, you have already found the shortest path to it.
Community answers
Answer by psiinyou
package dsa;
import java.util.LinkedList;
import java.util.Queue;
public class MazeScore {
public static class Node {
int row;
int col;
int distance;
public Node(int row, int col, int distance) {
this.row = row;
this.col = col;
this.distance = distance;
}
}
/**
Calculates the minimum number of moves to reach 'E' from 'S'.
@param maze The grid representing the maze.
@return The shortest pat«h length, or -1 if unreachable.
*/
public int getScore(char[][] maze) {
// TODO: Implement your Breadth-First Search (BFS) or Pathfinding logic here.
Node cell = getStartCell(maze);
if(cell == null)
return -1;
Queue q = new LinkedList<>();
q.add(cell);
boolean[][] visited = new boolean[maze.length][maze[0].length];
visited[cell.row][cell.col] = true;
int[][] dir = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
while(!q.isEmpty()){
Node curr = q.poll();
if(maze[curr.row][curr.col] == 'E')
return curr.distance;
for(int i = 0; i < 4; i++){
int nr = curr.row+dir[i][0];
int nc = curr.col+dir[i][1];
if(canVisit(nr, nc, maze, visited)){
visited[nr][nc] = true;
q.add(new Node(nr, nc, curr.distance+1));
}
}
}
return -1;
}
Node getStartCell(char[][] maze){
for(int i = 0; i < maze.length; i++){
for(int j = 0; j < maze[0].length; j++){
if(maze[i][j] == 'S')
return new Node(i, j, 0);
}
}
return null;
}
boolean canVisit(int r, int c, char[][] maze, boolean[][] visited){
if(r >= maze.length || r < 0 || c >= maze[0].length || c < 0 || visited[r][c] == true || maze[r][c] == '#')
return false;
return true;
}