当前位置：首页 > news >正文

C++上学抄近路动态规划算法实现 CCF信息学奥赛C++ 中小学普及组 CSP-J C++算法案例学习

news 2025/6/13 7:54:17

C++上学抄近路

博主推荐

所有考级比赛学习相关资料合集【推荐收藏】

1、C++专栏

电子学会C++一级历年真题解析
电子学会C++二级历年真题解析
蓝桥杯C++选拔赛真题解析
信息素养大赛C++算法编程挑战赛

2、Python专栏

蓝桥杯python选拔赛真题详解
蓝桥杯python省赛真题详解
蓝桥杯python国赛真题详解
信息素养大赛python编程挑战赛
python等级一级真题解析【电子学会】
python等级二级真题解析【电子学会】
python等级三级真题解析【电子学会】

一、题目要求

1、编程实现

小明每天要从家到学校，小区被道路分成许多正方形的块，共有N×M块，一般情况下，小区内的方块建有房屋，只能沿着边上的街道行走，有时方块表示公园，那么就可以直接穿过。请你帮她计算一下从家到学校的最短距离。

2、输入输出

输入描述：第一行是N和M（0＜N，M≤1 000）。注意，小明家坐标在方块(1,1)的西北角，车站在方块(N,M)的东南角。每个方块边长100米。接下来一行是整数K，表示可以对角线穿过的方块数，然后有K行，每行两个数，表示一个坐标。

输出描述：输出最短距离，四舍五入到整数，单位为米。

输入样例：

输出样例：

二、算法分析

从给定题目的初步分析可以看出，本题是一道图论相关的题，但是要求的又是最短距离
所以方法有多种，可以使用广度优先搜索算法BFS，也可以使用动态规划算法DP实现
由于N和M的取值为1000，用BFS有可能出现超时的情况，所以这里使用DP方式实现
DP定义：dp[i][j]表示从起点(1,1)到位置(i,j)的最短距离。
DP初始化：初始化第一行和第一列的距离，因为只能沿街道行走，所以每步增加100米。
状态转移方程：对于每个位置(i,j)，计算从上方或左方移动过来的最短距离。如果当前位置是公园，还可以考虑从对角线方向移动过来的距离（增加141.42米）。
遍历顺序：由于是从家里到学校，且状态转移方程中后一个位置需要用到前一个位置的状态，所以应该是从前往后遍历。
然后还有一点要注意的是：输入的数据是对应的行列，其实这里需要转一下，坐标要从0.0开始，比如输入的（1，1）表示公园可以对角线同行，那就应该从坐标（0，0）的位置到坐标（1，1的位置）进行划线，所以在处理坐标输入的时候需要进行一个处理

三、程序编写

#include<iostream>
#include<vector> 
#include<cmath>
using namespace std;int main(){int n,m,k;float t = sqrt(2) * 100;cin >> n >> m >> k;vector<vector<bool>> isPark(n+1,vector<bool>(m+1,false));for(int i = 0;i < k;i++){int x,y;cin >> x >> y;isPark[x-1][y-1] = true;isPark[x][y] = true;}vector<vector<float>> dp(n+1,vector<float>(m+1,0.0));for(int i = 1;i <= n;i++)dp[i][0] = dp[i-1][0] + 100;	for(int j = 1;j <= m;j++)dp[0][j] = dp[0][j-1] + 100;		for(int i = 1;i <= n;i++)	for(int j = 1;j <= m;j++){float mins = min(dp[i-1][j],dp[i][j-1]) + 100;if(isPark[i-1][j-1] && isPark[i][j])mins = min(mins,dp[i-1][j-1] + t);dp[i][j] = mins;}cout << round(dp[n][m]) << endl;return 0;
}

本文作者：小兔子编程作者首页：小兔子编程-CSDN博客