#P2928. 第3题-最小代价相遇的路径规划
-
2000ms
Tried: 1211
Accepted: 217
Difficulty: 6
所属公司 :
华为
时间 :2025年5月7日-暑期实习
-
算法标签>dp
第3题-最小代价相遇的路径规划
题解
题面描述
给定一个大小为 n×n 的非负整数矩阵 grid,其中 grid[i][j] 表示通过位置 [i,j] 所需的代价,若 grid[i][j] = 0 则该位置为障碍物,车辆无法通过。
- 第一辆车从 [0,0] 出发,只能向右或向下移动;
- 第二辆车从 [n−1,n−1] 出发,只能向上或向左移动;
- 任一车辆经过的每个位置(包括起始位置)都会产生对应的代价;
- 两辆车“相遇”定义为:它们最终分别停在一对相邻(上下或左右相邻)的网格位置上,且各自路径都可达;
- 相遇的总代价定义为两条路径代价的较大值;
求两辆车相遇所需的最小代价,若无法相遇则返回 -1。
解题思路
-
子问题划分
- 令
dp1[i][j] =第一辆车从(0,0)到(i,j)的最小代价
只允许向右或向下移动。 - 令
dp2[i][j] =第二辆车从(n−1,n−1)(i,j)$的最小代价
只允许向上或向左移动。
- 令
-
状态转移
- 对于 dp1:

- 对于 dp2:

- 对于 dp1:
-
答案计算
max(dp1[i][j],dp2[i′][j′]).
枚举所有相邻格子对 (i,j) 与 (i′,j′),其中 ∣i−i′∣+∣j−j′∣=1,若 dp1[i][j]<∞ 且 dp2[i′][j′]<∞,则可在这对格子上相遇,其代价为最终取所有相邻对的最小值,即为所求答案;若没有合法的相遇对,则返回
-1。 -
复杂度
- 时间:O(n2)
- 空间:O(n2),也可滚动数组优化到 O(n)。
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> grid(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> grid[i][j];
// dp1[i][j]: 第一辆车从 (0,0) 到 (i,j) 的最小代价
vector<vector<ll>> dp1(n, vector<ll>(n, INF));
if (grid[0][0] != 0) dp1[0][0] = grid[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue; // 障碍
if (i > 0 && dp1[i-1][j] != INF)
dp1[i][j] = min(dp1[i][j], dp1[i-1][j] + grid[i][j]);
if (j > 0 && dp1[i][j-1] != INF)
dp1[i][j] = min(dp1[i][j], dp1[i][j-1] + grid[i][j]);
}
}
// dp2[i][j]: 第二辆车从 (n-1,n-1) 到 (i,j) 的最小代价
vector<vector<ll>> dp2(n, vector<ll>(n, INF));
if (grid[n-1][n-1] != 0) dp2[n-1][n-1] = grid[n-1][n-1];
for (int i = n-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
if (grid[i][j] == 0) continue;
if (i+1 < n && dp2[i+1][j] != INF)
dp2[i][j] = min(dp2[i][j], dp2[i+1][j] + grid[i][j]);
if (j+1 < n && dp2[i][j+1] != INF)
dp2[i][j] = min(dp2[i][j], dp2[i][j+1] + grid[i][j]);
}
}
ll ans = INF;
// 枚举相邻格子对
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp1[i][j] == INF) continue;
for (auto &d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni<0||ni>=n||nj<0||nj>=n) continue;
if (dp2[ni][nj] == INF) continue;
ans = min(ans, max(dp1[i][j], dp2[ni][nj]));
}
}
}
cout << (ans == INF ? -1 : ans) << "\n";
return 0;
}
Python
import sys
import math
def min_meeting_cost(grid):
n = len(grid)
INF = math.inf
# dp1[i][j]: 第一辆车到 (i,j)
dp1 = [[INF]*n for _ in range(n)]
if grid[0][0] != 0:
dp1[0][0] = grid[0][0]
for i in range(n):
for j in range(n):
if grid[i][j] == 0: continue
if i>0 and dp1[i-1][j]!=INF:
dp1[i][j] = min(dp1[i][j], dp1[i-1][j] + grid[i][j])
if j>0 and dp1[i][j-1]!=INF:
dp1[i][j] = min(dp1[i][j], dp1[i][j-1] + grid[i][j])
# dp2[i][j]: 第二辆车到 (i,j)
dp2 = [[INF]*n for _ in range(n)]
if grid[n-1][n-1] != 0:
dp2[n-1][n-1] = grid[n-1][n-1]
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
if grid[i][j] == 0: continue
if i+1<n and dp2[i+1][j]!=INF:
dp2[i][j] = min(dp2[i][j], dp2[i+1][j] + grid[i][j])
if j+1<n and dp2[i][j+1]!=INF:
dp2[i][j] = min(dp2[i][j], dp2[i][j+1] + grid[i][j])
ans = INF
dirs = [(1,0),(-1,0),(0,1),(0,-1)]
for i in range(n):
for j in range(n):
if dp1[i][j] == INF: continue
for di,dj in dirs:
ni, nj = i+di, j+dj
if 0<=ni<n and 0<=nj<n and dp2[ni][nj]!=INF:
ans = min(ans, max(dp1[i][j], dp2[ni][nj]))
return -1 if ans==INF else ans
if __name__ == "__main__":
data = sys.stdin.read().split()
n = int(data[0])
vals = list(map(int, data[1:]))
grid = [vals[i*n:(i+1)*n] for i in range(n)]
print(min_meeting_cost(grid))
Java
import java.io.*;
import java.util.*;
public class Main {
static final long INF = Long.MAX_VALUE / 4;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
int[][] grid = new int[n][n];
for (int i = 0; i < n; i++) {
String[] ss = br.readLine().split("\\s+");
for (int j = 0; j < n; j++) {
grid[i][j] = Integer.parseInt(ss[j]);
}
}
long[][] dp1 = new long[n][n];
long[][] dp2 = new long[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dp1[i], INF);
Arrays.fill(dp2[i], INF);
}
// 第一辆车
if (grid[0][0] != 0) dp1[0][0] = grid[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue;
if (i > 0 && dp1[i-1][j] != INF)
dp1[i][j] = Math.min(dp1[i][j], dp1[i-1][j] + grid[i][j]);
if (j > 0 && dp1[i][j-1] != INF)
dp1[i][j] = Math.min(dp1[i][j], dp1[i][j-1] + grid[i][j]);
}
}
// 第二辆车
if (grid[n-1][n-1] != 0) dp2[n-1][n-1] = grid[n-1][n-1];
for (int i = n-1; i >= 0; i--) {
for (int j = n-1; j >= 0; j--) {
if (grid[i][j] == 0) continue;
if (i+1 < n && dp2[i+1][j] != INF)
dp2[i][j] = Math.min(dp2[i][j], dp2[i+1][j] + grid[i][j]);
if (j+1 < n && dp2[i][j+1] != INF)
dp2[i][j] = Math.min(dp2[i][j], dp2[i][j+1] + grid[i][j]);
}
}
long ans = INF;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp1[i][j] == INF) continue;
for (int[] d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni<0||ni>=n||nj<0||nj>=n) continue;
if (dp2[ni][nj] == INF) continue;
ans = Math.min(ans, Math.max(dp1[i][j], dp2[ni][nj]));
}
}
}
System.out.println(ans == INF ? -1 : ans);
}
}
题目内容
假定有两辆车在给定一个n×n的非负整数矩阵地图grid中行驶,地图左上角位置为[0,0]。我们简化车辆行驶的方式,每辆车可以从一个坐标行驶到相邻 (上下左右)的另一个坐标,并且经过的每个位置都会产生代价,包括起始位置的代价。其中grid[i][j]表示通过网格位置[i,j] 所需的代价。矩阵中,grid[i][j]等于0表示该位置为障碍物,车辆无法通过。两辆车约定好需要在地图中快速相遇进行货物交接。
两辆车相遇的定义为:两辆车最终分别停在相邻的网格位置(上下或左右相邻),并且路径可达。
两辆车相遇所需的代价定义为:两辆车到达各自相遇位置所需代价中的较大值。
注意:路径代价包含车辆的起始位置位置的代价;行驶过程中,车辆可以停在某一个网格位置上,两辆车无需同步行驶。
求两辆车可以相遇需要的最小代价,如果无法相遇则返回−1。
输入描述
第一行输入是一个整数n,代表地图grid[n][n]的大小,即n行n列大小的地图。
后续每一行代表地图中通过每个网格位置所需的时间信息,即grid[n][n]的每一行的元素值。
假设初始状态两辆车分别从左上角[0,0]和右下角 [n−1,n−1] 出发,左上角的车只能向右或向下移动,右下角的车只能向上或向左移动。
参数取值范围:
- 2<=n<=1000
- 0<=grid[i][j]<=100
- grid[0][0]!=0
- grid[n−1][n−1]!=0
输出描述
一个整数,表示两辆车相遇的最小代价;如果两车无法相遇(例如都被障碍物阻挡),则返回−1。
样例1
输入
2
1 2
2 1
输出
3
说明
第一行输入代表该地图大小是2,即2行2列的矩阵。
地图信息为:
grid[n][n]=
[[1,2],
[2,1]]
最快相遇的一种方案是:
第一辆车路径:[0,0]−>[0,1],所需代价:1+2=3
第二辆车路径:[1,1],所需代价:1
两辆车在下方矩阵中小括号标记状态相遇,需要代价是3(取两辆车各自代价的较大值3作为相遇的代价),所以返回3。
[[1,(2)],
[2,(1)]]
样例2
输入
3
1 2 3
1 2 3
1 2 3
输出
5
说明
第一行输入代表该地图大小是3,即3行3列的矩阵。
地图信息为:
grid[n][n]=
[[1,2,3],
[1,2,3],
[1,2,3]]
最快相遇的一种方案是:
第一辆车路径:[e,0]−>[1,e]−>[2,0],所需代价:1+1+1=3 第二辆车路径:[2,2]−>[2,1],所需代价:5
两辆车在下方矩阵中小括号标记状态相遇,需要代价是5(取两辆车各自代价的较大值5作为相遇的代价),所以返回5。
[[1,2,3],
[1,2,3],
[(1),(2),3]]
样例3
输入
3
1 0 3
1 0 3
1 0 3
输出
-1
说明
第一行输入代表该地图大小是3,即3行3列的矩阵。
地图信息为
grid[n][n]=
[[1,0,3],
[1,0,3],
[1,0,3]]
由于地图中的障碍物,使得两辆车无法相遇,所以返回−1。