tym777

用户名：timorthy7

访问量：5295

签　名：

老菜鸡了ToT

等　　级
排　　名	4191
经　　验	1743
参赛次数	0
文章发表	16
年　　龄	0
在职情况	学生
学　　校	仙交
专　　业	软件工程

　　自我简介：

TA的其他文章

1426: 蓝桥杯历届试题-九宫重排（双向BFS）用列表做队列实现！（最精简版本）
浏览：1861

1434: 蓝桥杯历届试题-回文数字
浏览：258

1433: 蓝桥杯2013年第四届真题-危险系数
浏览：271

你可能喜欢

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

1426: 蓝桥杯历届试题-九宫重排（双向BFS）用列表做队列实现！（最精简版本）

　　作者: tym777　　　　发表时间：2021-11-13 13:36:43 浏览：1861　|　评论：1　

原题链接：蓝桥杯历届试题-九宫重排

双向BFS遍历。
##算法思想：
用BFS的思想，从队列中拿出一种情况作为当前情况进行一次搜寻。在当前的情况下将所有可能的移动（上下左右交换）都检查一次，有意义的情况就将其加入队列，以用来继续下一次搜寻。

###判断方式
####标记方式
设置一个字典visited，key就是这个当前情况的字符串，value是一个2元组含义分别是（从哪端找到这里的，到达当前情况所走的步数）对于第一个元素的话从start找到这里的就是1，从end找到这里的就是2.
####找到目标的条件
当我们做判断的时候，
1.如果visited字典中有当前情况，即next_mat in visited.keys() 再判断一下当前cur_mat和下一步的next_mat，他们的值中的：从那段到这里的 这个标记位是否不同，即相加是否等于3。 等于三说明是两边交汇了，直接返回结果
2.如果visited字典中没有当前情况，直接把下一步的next_mat入对，等待下一次对这个情况进行搜寻。同时在visited字典中加入这个键值对，值为的一个元素就是和当前的相同（表示都是从一个方向找过来），第二个元素就是当前的加1
####可能的错误情况
- 第一个出错的就是下面的搜寻新情况的那个函数gen_next_mat()，里面的第6行，j循环的时候出大问题，找了好久，最后才发现的hhh，还是语言基础有点拉。。。也希望各位引起注意，不要像我一样笨批
- 关于bfs的话，如果不了解的话需要学习一下数据结构的知识。
- 双向BFS的需要有一个标记位。

def gen_next_mat(cur_mat, i):  产生新的可能情况
    	idx = cur_mat.find('.')
    	x = int(idx / 3)
    	y = int(idx % 3)
    	dx = [0, 1, 0, -1]
    	dy = [-1, 0, 1, 0]
    	for j in range(i+1):            #这个地方我做的时候又一次出错了，i是上一级循环传过来的，i从0开始，所以下一层循环次数用i控制是绝对要小心的，j in range(i)的话 i等于0 是每次都要少执行一次的！所以必须是 i+1 
    		x2 = x + dx[i]
    		y2 = y + dy[i]
    		if not (x2 > 2 or x2 < 0 or y2 > 2 or y2 < 0):  #判断新情况是否合理
    			idx2 = x2 * 3 + y2
    		else:
    			return None
    		if idx > idx2:
    			idx2, idx = idx, idx2
    		lis = list(cur_mat)
    		lis[idx], lis[idx2] = lis[idx2], lis[idx]
    		next_mat_str = ''.join(lis)
    		return next_mat_str
    
    
    def BFS(start, end):
    	if start == end:
    		return 0
    	queue = []
    	visited = {start: (1, 0), end: (2, 0)}  #情况记录的字典。初试队列中加入一头一尾，1表示从start这一端开始找的，2表示从end这一端开始找的。0就是记录到这个情况的步数
    	queue.append(start)
    	queue.append(end)
    	while len(queue) != 0:
    		cur_mat = queue[0]
    		flag, count = visited[cur_mat]
    		queue.pop(0)
    		for i in range(4):
    			next_mat = gen_next_mat(cur_mat, i)
    			if next_mat:
    				if next_mat in visited.keys():   #这种情况问过
    					if visited[next_mat][0] != flag:  是否是从不同方向访问的
    						return visited[next_mat][1] + visited[cur_mat][1] + 1
    				else:
    					queue.append(next_mat)
    					visited[next_mat] = flag, count + 1
    	return -1
    
    start = input().strip()
    end = input().strip()
    print(BFS(start, end))

0.0分

20 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

dotcpp0586235

搜寻的那个函数是啥意思呀

2022-07-21 17:48:24

tym777

TA的其他文章

你可能喜欢

Hello, world! （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1426: 蓝桥杯历届试题-九宫重排（双向BFS）用列表做队列实现！（最精简版本）

评论区

精彩推荐

数列排序（C语言代码）

C语言训练-素数问题（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

tym777

TA的其他文章

你可能喜欢

Hello, world! （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1426: 蓝桥杯历届试题-九宫重排 （双向BFS）用列表做队列实现！（最精简版本）

评论区

精彩推荐

数列排序 （C语言代码）

C语言训练-素数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1426: 蓝桥杯历届试题-九宫重排（双向BFS）用列表做队列实现！（最精简版本）

　　评论区

数列排序（C语言代码）

C语言训练-素数问题（C语言代码）

【亲和数】（C语言代码）

用筛法求之N内的素数。（C++代码）