← 返回 databricks 的题目列表Optimal Commute
类型：online_judge
Problem: Optimal Commute
You are given a 2D city grid containing:
.: an empty passable cell, which can also be chosen as the home / starting location;
#: an obstacle that cannot be passed through;
A, B, C, D: four required destinations, such as office, gym, school, and station. These cells are passable, but cannot be chosen as the home location.
From any cell, you may move one step up, down, left, or right. You cannot leave the grid or pass through obstacles.
Choose one . cell such that the sum of its shortest path distances to A, B, C, and D is minimized.
If multiple cells have the same minimum distance sum, return the one with the smallest row index; if still tied, return the one with the smallest column index. Rows and columns are 0-indexed.
If no . cell can reach all four destinations, output -1.
Input Format
m n
grid[0]
grid[1]
...
grid[m-1]
Where:
m is the number of rows;
n is the number of columns;
each row is a string of length n;
the grid contains exactly four destination cells: A, B, C, and D.
Output Format
If a valid answer exists, output:
row col min_distance_sum
Otherwise output:
-1
Constraints
1 <= m, n <= 500
The grid contains exactly four destinations: A, B, C, D
The chosen home location must be a . cell
Example
Input:
3 5
A...B
.###.
C...D
Output:
0 1 12
Example
Input
3 5
A...B
.###.
C...D
Output
0 1 12