← 返回 snapchat 的题目列表BFS Shortest Distance on a 2D Grid
类型：online_judge
You are given a 2D grid grid of size m x n. Use BFS to compute shortest distance on the grid.
Implement a function that computes the shortest distance by moving in 4 directions (up/down/left/right) with cost 1 per move.
grid[i][j] may indicate walkable vs blocked (obstacles).
If the target is unreachable, return -1 (or mark unreachable as -1 in a distance matrix).
Input (stdin):
Line 1: two integers m n
Next m lines: n integers for grid
Last line: start and target coordinates sr sc tr tc
Output (stdout):
A single integer: the shortest distance from start to target (-1 if unreachable).
Constraints:
1 <= m, n <= 200
grid[i][j] is 0/1 (0 walkable, 1 blocked in this statement)
Examples:
With obstacles you may need to detour; if fully blocked then unreachable.
Example
Input
3 3
0 0 0
1 1 0
0 0 0
0 0 2 2
Output
4