← 返回 meta 的题目列表Mouse Find Cheese (Grid Shortest Path)
类型：online_judge
Problem: Mouse Finds Cheese (Shortest Path)
You are given a 2D grid grid where:
S is the mouse start (exactly one)
C is the cheese (exactly one)
# is a wall (blocked)
. is free cell (walkable)
The mouse can move one step at a time in 4 directions (up/down/left/right). It cannot leave the grid or pass through walls.
Return the minimum number of steps needed to reach C from S. If it is impossible, return -1.
Input (stdin)
First line: two integers R C (rows and columns)
Next R lines: each a string of length C describing the grid
Output (stdout)
One integer: the minimum steps, or -1 if unreachable
Constraints
1 <= R, C <= 200
Grid contains only S, C, #, .
Examples / Tests
Test 1
3 4
S..#
.#..
...C
Output
5
Test 2
2 3
S##
..C
Output
-1
Test 3
1 2
SC
Output
1
Test 4
3 3
S..
###
..C
Output
-1
Test 5
4 5
S....
.###.
...#.
...C.
Output
6
Example
Input
3 4
S..#
.#..
...C
Output
5