day66 Floyd 算法 A * 算法

embedded/2024/11/17 16:40:02/

97. 小明逛公园 

题目描述

小明喜欢去公园散步,公园内布置了许多的景点,相互之间通过小路连接,小明希望在观看景点的同时,能够节省体力,走最短的路径。 

给定一个公园景点图,图中有 N 个景点(编号为 1 到 N),以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划,每个计划都有一个起点 start 和一个终点 end,表示他想从景点 start 前往景点 end。由于小明希望节省体力,他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。

输入描述

第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。 

接下来的 M 行,每行包含三个整数 u, v, w,表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。 

接下里的一行包含一个整数 Q,表示观景计划的数量。 

接下来的 Q 行,每行包含两个整数 start, end,表示一个观景计划的起点和终点。

输出描述

对于每个观景计划,输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径,则输出 -1。 

输入示例
7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4
输出示例
4
-1
提示信息

从 2 到 3 的路径长度为 4,3 到 4 之间并没有道路。

1 <= N, M, Q <= 1000.

1 <= w <= 10000.

第一种方法(Floyd-基于三维数组):

def main():max_int = 10005 # 设置最大路径,因为边最大距离为10^4n, m = map(int, input().split())grid = [[[float('inf')] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)] # 初始化二维数组for _ in range(m):p1, p2, w = map(int, input().split())grid[p1][p2][0] = wgrid[p2][p1][0] = w# 开始floydfor k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1])# 输出结果z = int(input())for _ in range(z):start, end = map(int, input().split())if grid[start][end][n] == max_int:print(-1)else:print(grid[start][end][n])if __name__ == '__main__':main()

第二种方法(floyd-基于二维数组) :

def main():max_int = 10005 # 设置最大路径,因为边最大距离为10^4n, m = map(int, input().split())grid = [[float('inf')] * (n + 1) for _ in range(n + 1)] # 初始化二维数组for _ in range(m):p1, p2, w = map(int, input().split())grid[p1][p2] = wgrid[p2][p1] = w# 开始floydfor k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])# 输出结果z = int(input())for _ in range(z):start, end = map(int, input().split())if grid[start][end] == max_int:print(-1)else:print(grid[start][end])if __name__ == '__main__':main()

127. 骑士的攻击 

题目描述

在象棋中,马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标,要求根据骑士的移动规则,计算从起点到达目标点所需的最短步数。

棋盘大小 1000 x 1000(棋盘的 x 和 y 坐标均在 [1, 1000] 区间内,包含边界)

输入描述

第一行包含一个整数 n,表示测试用例的数量,1 <= n <= 100。

接下来的 n 行,每行包含四个整数 a1, a2, b1, b2,分别表示骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。

输出描述

输出共 n 行,每行输出一个整数,表示骑士从起点到目标点的最短路径长度。 

输入示例
6
5 2 5 4
1 1 2 2
1 1 8 8
1 1 8 7
2 1 3 3
4 6 4 6
输出示例
2
4
6
5
1
0
提示信息

骑士移动规则如图,红色是起始位置,黄色是骑士可以走的地方。 

第一种方法 (a * 算法):

import heapq
import ren = int(re. sub(r'\D', '', input())) # 移除非数字字符moves = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]# 欧式距离
def distance(a, b):return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5def bfs(start, end):q = [(distance(start, end), start)]step = {start: 0}while q:d, cur = heapq.heappop(q)if cur == end:return step[cur]for move in moves:new = (move[0] + cur[0], move[1] + cur[1])if 1 <= new[0] <= 1000 and 1 <= new[1] <= 1000:step_new = step[cur] + 1if step_new < step.get(new, float('inf')):step[new] = step_newheapq.heappush(q, (distance(new, end) + step_new, new))return Falsefor _ in range(n):try:a1, a2, b1, b2 = map(int, input().split())print(bfs((a1, a2), (b1, b2)))except ValueError:print("Invalid input")


http://www.ppmy.cn/embedded/138292.html

相关文章

信号处理-Hilbert包络谱

Hilbert通常用来得到解析信号&#xff0c;基于此原理&#xff0c;Hilbert可以用来对窄带信号进行解包络&#xff0c;并求解信号的瞬时频率&#xff0c;包络谱是通过提取信号的瞬时幅度信息来揭示信号的动态特性。 基本理论 A-Hilbert变换定义 对于一个实信号x(t)&#xff0c;…

Android 最新的AndroidStudio引入依赖失败如何解决?如:Failed to resolve:xxxx

错误信息&#xff1a; 在引入依赖时报错&#xff1a;Failed to resolve: xxx.xxxx:1.1.0 解决方案&#xff1a; 需要修改maven库的代理&#xff0c;否则就需要翻墙编译 新的AndroidStudio版本比较坑&#xff0c;修改代理的位置发生了变化&#xff1a; 最新变化&#xff1a;…

浙大版《C语言程序设计(第4版)》题目集(一)

✨博客主页&#xff1a; https://blog.csdn.net/m0_63815035?typeblog &#x1f497;《博客内容》&#xff1a;.NET、Java.测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 &#x1f4e2;博客专栏&#xff1a; https://blog.csdn.net/m0_63815035/cat…

【电脑】解决DiskGenius调整分区大小时报错“文件使用的簇被标记为空闲或与其它文件有交叉”

【电脑】解决DiskGenius调整分区大小时报错“文件使用的簇被标记为空闲或与其它文件有交叉” 零、报错 在使用DiskGenius对磁盘分区进行调整时&#xff0c;DiskGenius检查出磁盘报错&#xff0c;报错信息&#xff1a;文件使用的簇被标记为空闲或与其它文件有交叉&#xff0c;…

机器学习—决定下一步做什么

现在已经看到了很多不同的学习算法&#xff0c;包括线性回归、逻辑回归甚至深度学习或神经网络。 关于如何构建机器学习系统的一些建议 假设你已经实现了正则化线性回归来预测房价&#xff0c;所以你有通常的学习算法的成本函数平方误差加上这个正则化项&#xff0c;但是如果…

HarmonyOS App 购物助手工具的开发与设计

文章目录 摘要引言功能需求分析技术方案与设计架构设计技术选型 代码示例Demo数据抓取模块数据存储模块历史价格查询和数据可视化模块完整界面布局和调用示例代码详解 QA环节总结参考资料 摘要 随着促销活动的增多&#xff0c;用户面临真假折扣的困惑&#xff0c;特别是在一些…

【MYSQL】分库分表

一、什么是分库分表 分库分表就是指在一个数据库在存储数据过大&#xff0c;或者一个表存储数据过多的情况下&#xff0c;为了提高数据存储的可持续性&#xff0c;查询数据的性能而进行的将单一库或者表分成多个库&#xff0c;表使用。 二、为什么要分库分表 分库分表其实是两…

uniapp中h5端如何引用本地json数据(json文件)

前言 uniapp读取本地json数据文件&#xff0c;有下面两种方式可以实现&#xff1a; 文件后缀为.json类型文件后缀为.js类型 这里展示后缀为.js类型的处理方式 1、在static中创建后缀为.js的文件存储json数据。 注意使用export导出 2、在要使用的页面导入 <template>…