华师一附中OI组

标题: 折线 [打印本页]

作者: admin 时间: 2021-9-29 17:37
标题: 折线
【问题】
　　给定一个m行n列的方格阵，每个方格边长为1。要从方格阵左上方的顶点（0，0）走到右下方的顶点（m，n），中间有若干个格子是障碍物，无法通过。人可以从（x1，y1）走到（x2，y2），当且仅当（x1<=x2）且（y1<=y2）且线段（x1，y1）-（x2，y2）不穿过任意一个障碍方格。求最短路长度。
【输入】
　　文件的第一行包括3个用空格分开的正整数m，n。以下是一个邻接矩阵A，1表示表示障碍。
【输出】
　　文件只有一行。文件应只一个精确到小数点后面2位小数的实数，表示最短路径的长度。
【样例输入】
　　3 　4
　　0 0 1 0
　　0 1 0 0
　　0 0 0 1
【样例输出】
　　5.47
【提示】
以下是示例数据的一种答案：
　　注意：图中红色的部分告诉我们，尽管路线不能穿越障碍方格，但是可以沿着障碍方格行进。
　　数据范围：1≤m，n≤30，输入数据无需判错。

欢迎光临华师一附中OI组 (http://hsyit.cn/)