Glacier Gridlock

# Glacier Gridlock ## Problem Bessie is trapped on a massive glacier and needs to navigate from her starting position **S** to the target location **T**. The glacier terrain is a grid where each cell has different traversal costs: - **Normal ice** cells cost **0** to enter - **Snowdrift** cells cost **1** to enter Bessie can move in four directions: up, down, left, and right. She wants to find the path that minimizes the total number of snowdrift cells she must cross. ## Input The first line contains two integers **N** and **M** (1 ≤ N, M ≤ 100), the dimensions of the glacier grid. The next **N** lines each contain a string of **M** characters representing the glacier. Each character is one of: - `S` - Bessie's starting position - `T` - The target location - `.` - Normal ice (cost 0) - `#` - Snowdrift (cost 1) ## Output Output a single integer: the minimum number of snowdrifts Bessie must cross to reach **T** from **S**. If it's impossible to reach the target, output `-1`. ## Constraints - 1 ≤ N, M ≤ 100 - There will always be exactly one `S` and one `T` in the grid - All paths use Manhattan-adjacent moves (up/down/left/right) ## Sample Input ``` 2 3 S#. #.T ``` ## Sample Output ``` 1 ``` ## Explanation Bessie starts at (0,0) marked with `S`. The optimal path is: - Start at S (0,0) - Move down to (1,0), which is a snowdrift `#` (cost 1) - Move right to (1,1), which is normal ice `.` (cost 0) - Move right to (1,2), which is the target `T` (cost 0) Total snowdrifts crossed: **1**