网站引导页面制作的四个任务名称关键词优化是什么意思?

C++上学抄近路

博主推荐

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

1、C++专栏 

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

 2、Python专栏

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

一、题目要求

1、编程实现

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

2、输入输出

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

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

输入样例：

3 2
3
1 1
3 2
1 2

输出样例：

383

二、算法分析

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

四、运行结果

3 2
3
1 1
3 2
1 2383

五、考点分析

难度级别：中等，这题相对而言在于坐标的处理，具体主要考察如下：

1. 分析题目，找到解题思路
2. 掌握动态规划算法的原理和使用方法
3. 学会STL 容器的灵活运用：尤其是vector动态数组的原理和使用
4. 学会数学建模能力以及数学函数和运算逻辑处理能力
5. 学会循环语句的熟练使用和分支语句的的控制处理（for、if）
6. 学会调试和校对程序设计与逻辑的完整性
7. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
8. 充分掌握数组定义和使用、分支语句、循环语句和动态规划算法的应用

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！