
牛客-地牢逃脱(BFS)
发布日期:2021-05-06 11:07:37
浏览次数:37
分类:原创文章
本文共 1245 字,大约阅读时间需要 4 分钟。
从给定起点(一定为’.’),按照给定的若干跳跃(可以跨过障碍,但不可以落在’x’上),到达任意一个’.'的最小步骤次数集合中,选择一个最大的!
while True: try: n , m = map(int,input().split()) matrix = [] for i in range(n): te = list(map(str,input())) matrix.append(te) begin_x,begin_y = map(int,input().split()) direction_num = int(input()) direction = [] for i in range(direction_num): direction.append(list(map(int,input().split()))) visited = set() visited.add((begin_x,begin_y)) stack = [(begin_x,begin_y,0)] re = -1 while stack: (x,y,step) = stack.pop(0) re = max(re,step) for [dx,dy] in direction: temp_x = x+dx temp_y = y+dy if 0<= temp_x <= n-1 and 0<= temp_y <= m-1 and (temp_x,temp_y) not in visited and matrix[temp_x][temp_y] == '.': visited.add((temp_x,temp_y)) stack.append((temp_x,temp_y,step+1)) count = 0 for i in range(n): for j in range(m): if matrix[i][j] == '.': count+=1 if len(visited) == count: print(re) else: print(-1) except: break
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2025年03月25日 08时24分55秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
POJ 2299 Ultra-QuickSort(树状数组+离散化+求逆序数)
2019-03-04
BUUCTF web WarmUp
2019-03-04
hcnp笔记
2019-03-04
python数据分析
2019-03-04
MySQL(四)数据库结构设计
2019-03-04
JavaScript 函数作用域
2019-03-04
2021-05-03
2019-03-04
Mybatis-plus 常用注解
2019-03-04
HTML基本结构
2019-03-04
图(三):拓扑排序、关键路径
2019-03-04
mybatis 如何切割字符串 查询多个值
2019-03-04
算法初步 (排序, 散列, 贪心, 二分, two pointers)
2019-03-04
Python学习-基础(五)
2019-03-04
myqsl下载安装
2019-03-04
Tomcat下载安装
2019-03-04
4.10 访问权限
2019-03-04
9.5 正则表达式及字符串的替换与分解
2019-03-04
9.8 Scanner类
2019-03-04
发布npm
2019-03-04