【算法设计与分析】六、动态规划：（二）上机－1、地牢逃生【理论到程序】

Qomolangma

发布于 2024-07-30 12:50:52

550

发布于 2024-07-30 12:50:52

文章被收录于专栏：深度学习

一、题目

1、问题

用一个 n×n 的矩阵表示一座地牢，矩阵中第 i 行第 j 列的方格的值表示位置 (i,j) 的地势高度 h(i,j)。时间 T=0 的时刻地牢开始下雨，当时间 T=t 时，地牢任意位置的水位都等于t 。任意时刻可以从当前位置游向上下左右四周相邻的任意一个位置，但是游动的前提是：此时水位必须淹没这个位置和其相邻位置，即如果在 T=t 时想从 (i,j) 位置移动到 (i,j+1) 位置，需要满足t≥h(i,j),t≥h(i,j+1) 。假定在方格内部游动不耗时。时间 T 的取值是正整数。求：从 (1,1) 位置出发，最少耗时多久可以到达 (n,n) 。

2、输入输出要求

输入格式
- 第一行一个整数 n 。
- 接下来 n 行，每行 n 个整数，代表 h(i,j) 。
输出格式
- 输出一个整数，表示最少耗时。
输入样例

2
0 2
1 3

输出样例

3、样例说明

时间 T=0 时，位于坐标方格的位置为 (1,1)。此时不能游向任意方向，因为相邻方向平台的高度都大于当前时间为 0 时的水位。
时间 T=1 时，可以游到 (2,1)；
时间 T=2 时，可以游到 (2,1)和(1,2)；
时间 T=3 时，才可以游到 (2,2) 。因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以可以游向坐标方格中的任意位置。

4、数据范围

n≤1000,0≤h(i,j)≤10^6

二、思路

谨以本实验证明AI的能力不够

PS：GPT4/Claude3均无法解决该问题，下附生成结果，具体内容不做解释。。。详细请咨询GPT（假如成功驯化，欢迎评论）

1、GPT4 - fail

这个问题可以使用广度优先搜索（BFS）算法来解决。下面是对算法的详细解释以及使用C++实现的示例：

算法解释

首先定义四个方向：上、下、左、右。
创建一个队列来存储待探索的位置信息，队列中的每个元素包括位置 (x, y) 和到达该位置所需的时间 t。
使用一个集合来记录已经访问过的位置，以避免重复访问。
从起始位置 (0, 0) 开始，将其加入队列和已访问集合中。
从队列中取出位置信息，检查其四个方向的相邻位置：
- 如果相邻位置未被访问过且满足游动条件，则将其加入队列和已访问集合，并更新到达该位置所需的时间。
重复以上步骤，直到队列为空或者到达终点 (n-1, n-1)。

C++ 实现

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int minTimeToEscape(int n, vector<vector<int>>& heights) {
    vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // right, left, down, up

    auto isValid = [&](int x, int y, int t) {
        return x >= 0 && x < n && y >= 0 && y < n && max(t, heights[x][y]) < t + 1;
    };

    queue<tuple<int, int, int>> q; // (x, y, time)
    set<pair<int, int>> visited;

    q.push({0, 0, 0});
    visited.insert({0, 0});

    while (!q.empty()) {
        auto [x, y, t] = q.front();
        q.pop();

        if (x == n - 1 && y == n - 1) {
            return t; // Reached the destination
        }

        for (auto& dir : directions) {
            int nx = x + dir.first, ny = y + dir.second;
            if (visited.count({nx, ny}) == 0 && isValid(nx, ny, t)) {
                visited.insert({nx, ny});
                q.push({nx, ny, t + 1});
            }
        }
    }

    return -1; // No path found
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> heights(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> heights[i][j];
        }
    }

    int result = minTimeToEscape(n, heights);
    cout << result << endl;

    return 0;
}

minTimeToEscape 函数接受地牢大小 n 和高度矩阵 heights 作为参数，并返回到达终点所需的最短时间。它使用了一个队列和一个集合来执行广度优先搜索，并检查是否满足游动条件。

2、Claude3 - fail

问题分析

这个问题可以用图论的方法来解决。我们可以把每个坐标点看作图中的一个顶点,相邻的坐标点之间有可以通行的边,边权为 0。问题转化为从起点 (1,1) 到终点 (n,n) 的最短路径问题。

由于每个位置的水位随时间增加而上涨,所以我们需要在图上添加时间维度,将每个顶点复制 t 个,表示在不同时间点可以到达该顶点。相邻顶点之间的边权为 1,表示耗时 1 单位时间。

对于任意两个相邻的顶点 (x,y,t) 和 (x’,y’,t+1),如果 max(h(x,y), h(x',y')) <= t+1,那么它们之间可以存在一条边,表示可以在 t+1 时刻从 (x,y) 移动到 (x’,y’)。

算法实现

我们可以使用广度优先搜索 (BFS) 算法来找到从起点到终点的最短路径。具体步骤如下:

创建一个三维数组 dist来记录从起点到达每个位置 (x,y,t) 的最短时间。初始化 dist[0][0][0] = 0,其他位置为正无穷大。
创建一个队列 q,将起点 (0,0,0) 加入队列。
每次从队列中取出一个位置 (x,y,t),检查它的上下左右四个相邻位置 (x’,y’,t+1)。如果 max(h[x][y], h[x'][y']) <= t+1 且 dist[x'][y'][t+1] > dist[x][y][t] + 1,更新 dist[x'][y'][t+1] 并将 (x’,y’,t+1) 加入队列。
当 (n-1,n-1) 出现在队列中时,返回对应的最短时间 dist[n-1][n-1][t]。如果队列为空仍未找到目标位置,返回 -1。

下面是 C++ 代码实现:

#include <bits/stdc++.h>
using namespace std;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int shortest_time(int n, vector<vector<int>>& h) {
    vector<vector<vector<int>>> dist(n, vector<vector<int>>(n, vector<int>(n+1, INT_MAX)));
    dist[0][0][0] = 0;
    queue<tuple<int, int, int>> q;
    q.push({0, 0, 0});

    while (!q.empty()) {
        int x, y, t;
        tie(x, y, t) = q.front();
        q.pop();

        if (x == n-1 && y == n-1) {
            return t;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < n && max(h[x][y], h[nx][ny]) <= t+1) {
                if (dist[nx][ny][t+1] > dist[x][y][t] + 1) {
                    dist[nx][ny][t+1] = dist[x][y][t] + 1;
                    q.push({nx, ny, t+1});
                }
            }
        }
    }

    return -1;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> h(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> h[i][j];
        }
    }
    cout << shortest_time(n, h) << endl;
    return 0;
}

这个算法的时间复杂度是

O(n^3)

,空间复杂度是

O(n^3)

,其中

是地牢的大小。

3、个人拙见 - succeed

本题目仅需获得最短耗时，不需要考虑动态规划回溯路径；本方法中每个A[i][j]是相对于已经走过的行、列的最短耗时，，与未来没走过的路没有任何瓜葛~，亦不需要考虑未来的路【贪心方法】？？？ PS：最终除了A[0][0]、A[n-1][n-1]外，每个A[i][j]都可能是假的时间~

初始化 A[0][0] = h[0][0]
- 起点 (0,0) 到达自身的最短时间就是该位置的地势高度。
初始化第一行和第一列的值
- 起点 (0,0) 到达 (i,0) 或 (0,j) 的最短时间,等于当前位置的地势高度和上(左)一个位置的最短时间的最大值。
  - A[i][0] = max(h[i][0], A[i-1][0])
  - A[0][j] = max(h[0][j], A[0][j-1])
递推其他位置的值
- A[i][j] = max(h[i][j], min(A[i-1][j], A[i][j-1]))
- 从起点 (0,0) 到达 (i,j) 的最短时间,等于当前位置的地势高度和上一个位置的最短时间的最大值，这里只需要考虑从上一个位置和左一个位置到达当前位置的最短时间。（瞬移是无敌的好嘛~）
最终答案就是 A[n-1][n-1]。

三、代码实现

//
// Created by Lenovo on 24-4-17.
//
#include <iostream>
using namespace std;
const int MAX = 1001;
int h[MAX][MAX];    // 地牢高度
int A[MAX][MAX];    // 动态规划

int time(int n) {
    int i, j;
    A[0][0] = h[0][0];  // 起始点=地牢高度
    // 初始化
    for (i = 1; i < n; i++) {
        A[i][0] = max(h[i][0], A[i-1][0]);
        A[0][i] = max(h[0][i], A[0][i-1]);
    }
    
    for (i = 1; i < n; i++) {
        for (j = 1; j < n; j++) {
//            假定在方格内部游动不耗时
            // 耗时最短（0,0）——（n-1，n-1）~方向已确定，不必考虑往回游~
            int minlocal = min(A[i][j-1],  A[i-1][j]);
            A[i][j] = max(h[i][j], minlocal);
        }
    }
    return A[n-1][n-1];
}

int main() {
    int n, i, j;
    cin>>n;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cin>>h[i][j];
        }
    }
    cout<<time(n);
    return 0;
}
/*
2
0 2
1 3
*/
/*
3
3 9 7
4 5 4
8 3 5
*/

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2hybf1ppyfc4k

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-07-26，如有侵权请联系 cloudcommunity@tencent.com 删除

队列