【算法设计与分析】六、动态规划:(二)上机-1、地牢逃生【理论到程序】

2024-05-05 07:28

本文主要是介绍【算法设计与分析】六、动态规划:(二)上机-1、地牢逃生【理论到程序】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、题目
    • 1、问题
    • 2、输入输出要求
    • 3、样例说明
    • 4、数据范围
  • 二、思路
    • 1、GPT4 - fail
      • 算法解释
      • C++ 实现
    • 2、Claude3 - fail
      • 问题分析
      • 算法实现
    • 3、个人拙见 - succeed
  • 三、代码实现

一、题目

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

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 ) ≤ 1 0 6 n≤1000,0≤h(i,j)≤10^6 n1000,0h(i,j)106

二、思路

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

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

1、GPT4 - fail

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

算法解释

  1. 首先定义四个方向:上、下、左、右。
  2. 创建一个队列来存储待探索的位置信息,队列中的每个元素包括位置 (x, y) 和到达该位置所需的时间 t
  3. 使用一个集合来记录已经访问过的位置,以避免重复访问。
  4. 从起始位置 (0, 0) 开始,将其加入队列和已访问集合中。
  5. 从队列中取出位置信息,检查其四个方向的相邻位置:
    • 如果相邻位置未被访问过且满足游动条件,则将其加入队列和已访问集合,并更新到达该位置所需的时间。
  6. 重复以上步骤,直到队列为空或者到达终点 (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, upauto 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) 算法来找到从起点到终点的最短路径。具体步骤如下:

  1. 创建一个三维数组 dist来记录从起点到达每个位置 (x,y,t) 的最短时间。初始化 dist[0][0][0] = 0,其他位置为正无穷大。
  2. 创建一个队列 q,将起点 (0,0,0) 加入队列。
  3. 每次从队列中取出一个位置 (x,y,t),检查它的上下左右四个相邻位置 (x’,y’,t+1)。如果 max(h[x][y], h[x'][y']) <= t+1dist[x'][y'][t+1] > dist[x][y][t] + 1,更新 dist[x'][y'][t+1] 并将 (x’,y’,t+1) 加入队列。
  4. 当 (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) O(n3),空间复杂度是 O ( n 3 ) O(n^3) O(n3),其中 n n n 是地牢的大小。

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
*/

这篇关于【算法设计与分析】六、动态规划:(二)上机-1、地牢逃生【理论到程序】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/961117

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表