题解

题面描述

给定一个大小为 $n\times n$ 的非负整数矩阵 grid，其中 grid[i][j] 表示通过位置 $[i,j]$ 所需的代价，若 grid[i][j] = 0 则该位置为障碍物，车辆无法通过。

• 第一辆车从 $[0,0]$ 出发，只能向右或向下移动；
• 第二辆车从 $[n-1,n-1]$ 出发，只能向上或向左移动；
• 任一车辆经过的每个位置（包括起始位置）都会产生对应的代价；
• 两辆车“相遇”定义为：它们最终分别停在一对相邻（上下或左右相邻）的网格位置上，且各自路径都可达；
• 相遇的总代价定义为两条路径代价的较大值；

求两辆车相遇所需的最小代价，若无法相遇则返回 -1。

解题思路

1. 子问题划分

   • 令
     $dp1[i][j]$ =第一辆车从$(0,0)$到$(i,j)$的最小代价
     只允许向右或向下移动。
   • 令
     $dp2[i][j]$ =第二辆车从$(n-1,n-1)$(i,j)$的最小代价
     只允许向上或向左移动。

2. 状态转移

   • 对于 $dp1$：
     
   • 对于 $dp2$：
     

3. 答案计算
   枚举所有相邻格子对 $(i,j)$ 与 $(i',j')$，其中 $|i-i'|+|j-j'|=1$，若 $dp1[i][j]<\infty$ 且 $dp2[i'][j']<\infty$，则可在这对格子上相遇，其代价为

   $$\max\bigl(dp1[i][j],\;dp2[i'][j']\bigr).$$

   最终取所有相邻对的最小值，即为所求答案；若没有合法的相遇对，则返回 -1。

4. 复杂度

   • 时间：$O(n^2)$
   • 空间：$O(n^2)$，也可滚动数组优化到 $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$。