赣州律师网站建设,丰台石家庄网站建设,网站域名是什么东西,岳阳招聘网C上学抄近路
博主推荐
所有考级比赛学习相关资料合集【推荐收藏】
1、C专栏
电子学会C一级历年真题解析电子学会C二级历年真题解析蓝桥杯C选拔赛真题解析信息素养大赛C算法编程挑战赛 2、Python专栏
蓝桥杯python选拔赛真题详解蓝桥杯python省赛真题详解蓝桥杯python国赛…
C上学抄近路
博主推荐
所有考级比赛学习相关资料合集【推荐收藏】
1、C专栏
电子学会C一级历年真题解析电子学会C二级历年真题解析蓝桥杯C选拔赛真题解析信息素养大赛C算法编程挑战赛 2、Python专栏
蓝桥杯python选拔赛真题详解蓝桥杯python省赛真题详解蓝桥杯python国赛真题详解信息素养大赛python编程挑战赛python等级一级真题解析【电子学会】python等级二级真题解析【电子学会】python等级三级真题解析【电子学会】
一、题目要求
1、编程实现
小明每天要从家到学校小区被道路分成许多正方形的块共有N×M块一般情况下小区内的方块建有房屋只能沿着边上的街道行走有时方块表示公园那么就可以直接穿过。 请你帮她计算一下从家到学校的最短距离。
2、输入输出
输入描述第一行是N和M0NM≤1 000。注意小明家坐标在方块(1,1)的西北角车站在方块(N,M)的东南角。每个方块边长100米。接下来一行是整数K表示可以对角线穿过的方块数然后有K行每行两个数表示一个坐标。
输出描述输出最短距离四舍五入到整数单位为米。
输入样例
3 2
3
1 1
3 2
1 2
输出样例
383
二、算法分析
从给定题目的初步分析可以看出本题是一道图论相关的题但是要求的又是最短距离所以方法有多种可以使用广度优先搜索算法BFS也可以使用动态规划算法DP实现由于N和M的取值为1000用BFS有可能出现超时的情况所以这里使用DP方式实现DP定义dp[i][j]表示从起点(1,1)到位置(i,j)的最短距离。DP初始化初始化第一行和第一列的距离因为只能沿街道行走所以每步增加100米。状态转移方程对于每个位置(i,j)计算从上方或左方移动过来的最短距离。如果当前位置是公园还可以考虑从对角线方向移动过来的距离增加141.42米。遍历顺序由于是从家里到学校且状态转移方程中后一个位置需要用到前一个位置的状态所以应该是从前往后遍历。然后还有一点要注意的是输入的数据是对应的行列其实这里需要转一下坐标要从0.0开始比如输入的11表示公园可以对角线同行那就应该从坐标00的位置到坐标11的位置进行划线所以在处理坐标输入的时候需要进行一个处理
三、程序编写
#includeiostream
#includevector
#includecmath
using namespace std;int main(){int n,m,k;float t sqrt(2) * 100;cin n m k;vectorvectorbool isPark(n1,vectorbool(m1,false));for(int i 0;i k;i){int x,y;cin x y;isPark[x-1][y-1] true;isPark[x][y] true;}vectorvectorfloat dp(n1,vectorfloat(m1,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
五、考点分析
难度级别中等这题相对而言在于坐标的处理具体主要考察如下
分析题目找到解题思路掌握动态规划算法的原理和使用方法学会STL 容器的灵活运用尤其是vector动态数组的原理和使用学会数学建模能力以及数学函数和运算逻辑处理能力学会循环语句的熟练使用和分支语句的的控制处理for、if学会调试和校对程序设计与逻辑的完整性学会分析题目算法分析将复杂问题模块化简单化从中找到相应的解题思路充分掌握数组定义和使用、分支语句、循环语句和动态规划算法的应用
PS方式方法有多种小朋友们只要能够达到题目要求即可
