Quick Overview

This question evaluates understanding of grid traversal and shortest-path graph search, including modeling a 2D grid with obstacles and reasoning about boundary and edge cases, within the Coding & Algorithms domain.

Solve grid shortest path with BFS

Company: Disney

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a 2D grid containing 0s (open cells) and 1s (walls), and coordinates for a start (sr, sc) and a target (tr, tc), return the length of the shortest path from start to target using 4-directional moves (up, down, left, right). If no path exists, return -1. Specify the algorithm, analyze time and space complexity, and discuss edge cases such as starting equals target, boundaries, and large grids.

Quick Answer: This question evaluates understanding of grid traversal and shortest-path graph search, including modeling a 2D grid with obstacles and reasoning about boundary and edge cases, within the Coding & Algorithms domain.

Return the length of the shortest four-directional path from start to target in a 0/1 grid, or -1 if unreachable.

Constraints

  • Inputs are provided as Python literals matching the function signature.
  • Return a deterministic exact-match result.

Examples

Input: ([[0,0,0],[1,1,0],[0,0,0]], (0,0), (2,2))

Expected Output: 4

Explanation: Path around walls.

Input: ([[0,1],[1,0]], (0,0), (1,1))

Expected Output: -1

Explanation: Blocked target.

Hints

  1. Choose a representation that makes the core operation simple.
  2. Handle empty and boundary inputs before the main algorithm.

Loading coding console...