Solve grid path and robot navigation
Overview
This question evaluates proficiency in graph traversal and pathfinding, state representation for unknown environments, exploration and backtracking, and rigorous reasoning about correctness and time/space complexity.
Part A — Shortest path in a grid with obstacles: Given an m×n grid of 0/1 cells (0 = open, 1 = obstacle), start at (0, 0) and end at (m−1,n− 1). You may move in four directions (up, down, left, right), each move costs 1. Return the length of the shortest path; return −1 if unreachable. Describe your algorithm, prove correctness, and analyze time/space complexity.
Part B — Robot search in an unknown room (LeetCode-inspired, original prompt): You do not have the grid map. You control a robot in a finite 2D room with walls/obstacles. The robot starts at an arbitrary cell. Available APIs:
- bool move(Direction d): attempts to move one cell in {up, down, left, right}; returns false if blocked and the robot stays put.
- void turnLeft(), void turnRight() (optional; use if needed to manage orientation).
- bool atTarget(): returns true if the current cell is the target. Design and implement an algorithm that explores the room, locates the target, and returns the minimal number of steps from the start to the target. Explain how you: (
- represent coordinates without a given grid, (
- avoid revisiting and handle backtracking, (
- ensure optimality of the returned step count, and (
- analyze complexity in terms of R, the number of reachable cells.