1. Dotcpp
  2. 题解列表
  3. 1878题题解

1878: 蓝桥杯2017年第八届真题-青蛙跳杯子（Python3）BFS

734 阅读 1 评论
原题链接：蓝桥杯2017年第八届真题-青蛙跳杯子

解题思路:
    1.BFS遍历所有状态，储存状态及其对应的步数；

    2.发现和结果吻合则退出。

注意事项:
    1.使用字典存储某一状态和对应步数，便于查找重复状态，降低时间复杂度；

    2.不要使用列表存储状态，因为列表不能作为字典键值，而应用字符串；

    3.“跳杯”的过程可以用列表实现。

参考代码:

def bfs():
    global start, end, cache_state, around
    stack = [start]
    while stack:
        temp_state = stack.pop(0)
        idx = temp_state.index('*')
        for i in around:
            if 0 <= idx + i < len(start) and temp_state[idx + i] != '*':
                temp = list(temp_state)
                temp[idx], temp[idx + i] = temp[idx + i], temp[idx]
                a = "".join(temp)
                if a not in cache_state:
                    cache_state.setdefault(a, cache_state[temp_state] + 1)
                    stack.append(a)
                    if a == end:
                        return cache_state[a]


start, end = [input() for _ in range(2)]
cache_state = {start: 0}
around = [-3, -2, -1, 1, 2, 3]
print(bfs())


点赞(0)
　

0.0分

3 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

c++使用bool变量的简便方法
c++使用bool变量的简便方法
c++的两种解法
c++的两种解法
利用c语言写出九九乘法表（循环嵌套）
利用c语言写出九九乘法表（循环嵌套）
2856: 潜伏者
2856: 潜伏者

评论列表 共有 1 条评论

小业 2年前 回复TA 
import os
import sys
from collections import deque
import copy

start = input()
target = input()
result = 0

def bfs():
  global result
  q = deque([[start,0]])
  while q:
    A,n = q.popleft()
    if A == target:
      print(n)
      break
    empty = A.index("*")
    for i in [-3,-2,-1,1,2]:
      x = i+empty
      if 0<=x<len(start):
        B = list(A)
        a = B[x]
        B[x] = "*"
        B[empty] = a
        q.append(["".join(B),n+1])
bfs()
请问我这个代码为什么会内存超限