GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

PROBLEM SET

最短路径

按知识点筛选题目，系统巩固该考点。

共 60 题

重置

全部知识点基础数学知识模拟枚举深度优先搜索递推贪心基础排序栈区间动态规划最短路算法队列字符串结构体排序动态规划前缀和拓扑排序线性动态规划树形动态规划递归背包动态规划最近公共祖先二分答案并查集线段树 sort排序基础算法高精度分治素数筛法

题目列表

共 60 题

A16904 中国象棋中，“马”走一步的规则是：从“日”字的一角走到另一角。例如，下图中的“马”一步能走到用红圈标出的 8 个位置。下图棋盘上有一个红色的“马”，要把所有的黑棋都吃光，最少需要走（）步。注意：1. 只有红棋走，黑棋不走2. 红棋吃完后不必回到原来位置 蓝桥杯-SW-L3 广度优先搜索最短路径状态空间搜索中等 -- A16941 中国象棋中，“马”走一步的规则是：从“日”字的一角走到另一角。例如，下图中的“马”一步能走到红圈标出的 8 个位置。下图棋盘上有一个红色的“马”，要把所有的黑棋都吃光，最少需要走（）步。注意：1.只有红棋走，黑棋不走2.红棋吃完后不必回到原来位置 蓝桥杯-SW-L3 广度优先搜索最短路径中国象棋马走日中等 -- A16943 蚂蚁洞虽然只有一个洞口，地下却是个庞大的王国。下图的每个圆点代表一个房间，线代表通道，每条线的长度为 1。洞里住着 5 只蚂蚁，它们有着不同的分工。每只蚂蚁每天出洞的次数如下表所示，回洞的次数与出洞次数相同：为了不打扰其他蚂蚁的生活，蚂蚁们住的房间，都不能在其他蚂蚁出洞的路上。请你给每只蚂蚁安排一个房间，要使这 5 只蚂蚁每天“到洞口”+“回房间”行走的总路程最短，这个最短路程是（）。 蓝桥杯-SW-L3 贪心算法最短路径树形结构中等 -- A16973 中国象棋中，“马”走一步的规则是：从“日”字的一角走到另一角。例如，下图中的“马”一步能走到红圈标出的 8 个位置。下图棋盘上有一个红色的“马”，要把所有的黑棋都吃光，最少需要走（）步。注意：1.只有红棋走，黑棋不走2.红棋吃完后不必回到原来位置 蓝桥杯-SW-L3 广度优先搜索最短路径状态空间搜索中等 -- A16975 小蜜蜂要穿过一个由小正方体组成的，6×6×6 的迷宫。每个小正方体的棱长为 1。如下图所示：小蜜蜂可以向上、下、左、右、前、后飞行。每飞行 1 个单位距离，需要 10 秒。在博士院长的帮助下，小蜜蜂得到了迷宫的三维扫描地图。为了描述迷宫的内部构造，扫描仪将迷宫竖着分成像书一样的 6 页，每页是 6 行 6 列的正方体，厚度是 1，如下图所示：再通过打印机，将每页打印在纸上，如下图所示：在熟记这个… 蓝桥杯-SW-L3 广度优先搜索最短路径三维迷宫中等 -- A16979 山区修了一条路，将 10 个村庄连在了一起。下图相邻两个村庄之间的数字，代表它们之间的距离：政府决定从 10 个村中选择一个村，在那里建一所小学，使得所有村庄到小学的距离总和最小。这个最小的距离总和是（）。 蓝桥杯-SW-L3 图论最短路径枚举法中等 -- A16982 蚂蚁洞虽然只有一个洞口，地下却是个庞大的王国。下图的每个圆点代表一个房间，线代表通道。两个房间之间的通道，长度都是 1。洞里住着 5 只蚂蚁，它们有着不同的分工。每只蚂蚁每天出洞的次数如下表所示，回洞的次数与出洞次数相同。为了不打扰其他蚂蚁的生活，蚂蚁们住的房间，都不能在其他蚂蚁出洞的路上。请你给每只蚂蚁安排一个房间，要使这 5 只蚂蚁每天“到洞口”+“回房间”行走的总路程最短，这个最短路程是（… 蓝桥杯-SW-L3 图论贪心算法最短路径树形结构中等 -- A63256 蓝桥杯Python编程题：给定两个房间的编号A和B，请找出从房间A到达房间B最少需要经过几个传送门。编程实现：在一个神奇空间里有N个房间，房间从1到N编号，每个房间可能有一个或多个传送门，每个传送门都有一个编号，如果相同编号的传送门同时出现在多个房间中，表示这些房间可以互通。给定两个房间的编号A和B，请找出从房间A到达房间B最少需要经过几个传送门。例如：N = 3，3个房间中传送门的编号分别为：… 创意编程组 广度优先搜索最短路径图论建模字符串解析 -- -- A66550 青少年软件编程（C语言）等级考试试卷（八级）：最短路径问题。平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。第一行为整数n。第2行到… 2023年 图论最短路径 Dijkstra算法坐标距离 -- -- A66546 青少年软件编程（C语言）等级考试试卷（七级）:走出迷宫.当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。接下来n行，每行一个长为m的字符串，… 2023年 队列广度优先搜索最短路径二维数组 -- -- A66545 青少年软件编程（C语言）等级考试试卷（七级）:拯救公主。多灾多难的公主又被大魔王抓走啦！国王派遣了第一勇士阿福去拯救她。身为超级厉害的术士，同时也是阿福的好伙伴，你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图，上面标记了阿福和公主所在的位置，以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门，通过一个传送门可以瞬间转移到任意一个传送门，当然阿福也可以选择不通过传送门瞬移… 2023年 广度优先搜索最短路径状态压缩网格地图 -- -- A58677 小明家在A点的位置，学校在B点的位置，如果不绕路，从A到B的路线共有几条？ 2022年 排列组合最短路径路径计数 -- -- A66049 C语言等级考试五级编程题：玩具摆放。在一个4*4的方框内摆放了若干个相同的玩具。某人想通过移动玩具，将这些玩具重新摆放成为他心中理想的状态。要求每次移动时，只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框，并且移动的目标位置不能已经放置有玩具。请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。输入前4行表示玩具的初始状… 2022年 广度优先搜索位运算最短路径状态压缩 -- -- A66048 C语言等级考试真题：哥斯拉大战金刚。众所周知，哥斯拉和金刚是时代仇敌，大战一触即发。金刚为了打败哥斯拉，要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图，S表示金刚目前的位置，T表示地心空洞的入口，X表示障碍物，.表示平地。在前往地心空洞之前，金刚必须先获得一系列打开地心空洞的钥匙（在地图上通过数字1,2,…,k表示），并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-… 2022年 广度优先搜索最短路径网格图状态压缩 -- -- A66039 青少年C语言等级考试八级真题：道路（roads）。N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后，Bob和她分手了，并且决定搬到城市N。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的… 2022年 动态规划图论最短路径状态约束 -- -- A63241 小蓝从公司出发，要去拜访N（3≤N≤15）个客户，已知公司到每个客户的路程时间，及N个客户之间的路程时间。请计算出小蓝拜访完所有客户并返回到公司，最少需要多少时间。（道路双向通行，可重复走）例如：N = 3，有3个客户需要拜访，公司到1号、2号、3号客户的路程时间依次为9，7，5，客户1到客户2和客户3的路程时间依次是4，6，客户2到客户3的路程时间是3。从公司出发拜访完3名客户并返回公司最少需… 创意编程组 动态规划位运算最短路径状态压缩 -- -- A66485 道路。 N 个以 1 ... N 标号的 2023年 动态规划图论最短路径费用约束 -- -- A63208 两名宇航员在探索一个未知行星，行星上有一些障碍物，这些障碍物用数字1表示，没有障碍物用数字0表示。行星被表示成一个N*M的矩阵。探索过程中两名宇航员走散了。已知A宇航员的位置(x1,y1)和B宇航员的位置(x2,y2)，请你帮助A宇航员找到一条最短路径到达B宇航员的位置，并输出最短路径的长度（不包括起点）。注意：1.x1、x2表示矩阵的行号，y1、y2表示矩阵的列号；2.左上角的位置为（0，0）… 创意编程组 广度优先搜索最短路径二维数组坐标与方向 -- -- A63648 家到学校：下图的黄色线代表路，路上的数代表走过这段路消耗的体力值。多多从家到学校，最少需要消耗的体力值为( ) 计算思维组 动态规划图论最短路径 -- -- A61303 如图所示，图中每条边上的数字表示该边的长度，则从 A 到 E 的最短距离是_________。 2014年 图论最短路径加权图 -- --