网站备案过期,网站顶部下拉广告,抖音创作服务平台,甘肃省网站建设咨询九九乘法表挂毯
问题描述#xff1a; 在一个古老的城堡里#xff0c;一位名为 Alex 的少年发现了一幅巨大的九九乘法表挂毯。挂毯被划分成了9x9的方格#xff0c;每个方格上写着相应的乘积。Alex 想象自己站在数值为1的方格上#xff0c;他的目标是到达数值为 81 的方格。…九九乘法表挂毯
问题描述 在一个古老的城堡里一位名为 Alex 的少年发现了一幅巨大的九九乘法表挂毯。挂毯被划分成了9x9的方格每个方格上写着相应的乘积。Alex 想象自己站在数值为1的方格上他的目标是到达数值为 81 的方格。然而少年遵循着一项规则:他只能移动到数值为 1、81 或任意偶数的相邻方格上。城堡的图书管理员告诉他只有找到最短路径到达目标他才能解开挂毯的秘密。 请你帮助 Alex计算在遵循上述移动规则的情况下他从1到81的最短路径有多少种可能。
输入格式 无。 输出格式 输出一个整数表示从1到 81 的最短路径的可能数量。
题目分析 这道题深度的考验BFS和DFS的综合运用可以作为考验自己是否对这两种算法熟悉的一道题去练练手下方配py的题解仅供参考。
综合思路就是先用BFS求出最短路径是多少然后用DFS去求符合该步数的路径有多少条。
代码实现
m[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18],
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27],
[0, 4, 8, 12, 16, 20, 24, 28, 32, 36],
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45],
[0, 6, 12, 18, 24, 30, 36, 42, 48, 54],
[0, 7, 14, 21, 28, 35, 42, 49, 56, 63],
[0, 8, 16, 24, 32, 40, 48, 56, 64, 72],
[0, 9, 18, 27, 36, 45, 54, 63, 72, 81]]dirs[[0,1],[0,-1],[-1,0],[1,0]] #四条路
def bfs(m):st,ed[1,1],[9,9]stack[[st,0]]while stack:curnode,stepstack.pop(0)print(curnode)if curnodeed: return stepstep1for i in dirs:a0,a1curnode[0]i[0],curnode[1]i[1]if 9a00 and 9a10 and (m[a0][a1] %20 or m[a0][a1]81):newnode[a0,a1]stack.append([newnode,step])m[a0][a1]1
print(bfs(m))res0
def dfs(x,y,key,step):global resif step16: returnif key81:res1returnelse:for dir in dirs:x0,y0xdir[0],ydir[1]if 9x00 and 9y00 and (m[x0][y0]%20 or m[x0][y0]81):vm[x0][y0]dfs(x0,y0,v,step1)
dfs(1,1,1,0)
print(res)
题目总结
这种题目主要考察对DFS和BFS两种搜索算法的理解和运用能力。所以要求我们必须掌握以下内容 理解DFS和BFS的基本原理DFS是深度优先搜索算法从起始节点开始沿着一条路径一直往下搜索直到无法继续为止然后返回上一个节点继续搜索BFS是广度优先搜索算法从起始节点开始先搜索所有相邻节点再逐层向下搜索。 分析DFS和BFS的应用场景DFS通常用于寻找所有可能的解或路径适用于图的遍历、拓扑排序、连通性检测等问题BFS通常用于求最短路径、最小步数等问题。 比较DFS和BFS的特点DFS递归实现简单但可能会无限循环BFS借助队列实现保证了最优解但空间复杂度较高。 实际应用中如何选择DFS和BFS根据具体问题特点选择合适的搜索算法通常情况下如果需要找到解的所有可能可以使用DFS如果要求最短路径或步数可以使用BFS。
