蓝桥杯训练15——穿越雷区

from collections import deque

def bfs(leiqu):
    n = len(leiqu)
    
    # 定义四个方向:右、下、左、上
    directions=[(0,1),(0,-1),(1,0),(-1,0)]
    
    # 初始化访问标记矩阵
    visited = [[False] * n for _ in range(n)]
    queue = deque()
    # 找到起点 A 和终点 B 的位置
    for i in range(n):
        for j in range(n):
            if leiqu[i][j] == 'A':
                start = (i, j)
            elif leiqu[i][j] == 'B':
                end = (i, j)
    

    # 初始化队列,将起点加入队列
    
    queue.append((start, 0, leiqu[start[0]][start[1]]))
    
    # 开始 BFS
    while queue:
        (x, y), step, current_energy = queue.popleft()
        
        # 标记当前节点为已访问
        visited[x][y] = True
        
        # 遍历四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 检查新节点是否在矩阵范围内且未被访问过
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                next_energy = leiqu[nx][ny]
                
                # 检查能量区是否与当前节点的能量区不同
                if next_energy != current_energy:
                    # 如果找到了终点 B,返回步数
                    if (nx, ny) == end:
                        return step + 1
                    
                    # 将新节点加入队列
                    visited[nx][ny] = True
                    queue.append(((nx, ny), step + 1, next_energy))
    
    # 如果遍历完所有可能的路径都没有找到 B,返回 -1
    return -1

# 读取输入
n = int(input())
leiqu = [input().split() for _ in range(n)]

# 调用 BFS 函数并输出结果
result = bfs(leiqu)
print(result)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/34319.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【STL】用一张哈希表封装unordered_set和unordered_map

哈希表源代码 这里是使用开散列实现的哈希表&#xff0c;为了和库里的哈希表进行区分&#xff0c;我将哈希表放入到了命名空间中 //确保取余运算符两边是正整数&#xff0c;下标不能是负整数 template<class K> struct DefaultHashFunc {size_t operator()(const K&…

搜索二维矩阵 II

搜索二维矩阵 II 编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9…

嵌入式入门Day24

数据结构Day5 树形结构相关概念二叉树相关概念二叉树的状态二叉树性质二叉树的存储二叉树根据已有序列推出树的结构练习 算法相关概念算法特性算法的设计要求时间复杂度排序算法冒泡排序&#xff08;改良版&#xff09;选择排序&#xff08;O(n^2)&#xff09;直接插入排序&…

百度网盘qzxing-master.zip

qzxing 这是一个针对 ZXing 条形码图像处理库的 Qt/QML 封装库。 支持以下类型的条形码解码&#xff1a; UPC-AUPC-EEAN-8EAN-13ITFCode 39Code 93Code 128&#xff08;GS1&#xff09;Codabar二维码数据矩阵Aztec&#xff08;测试版&#xff09;PDF 417 支持以下类型的条形…

Ping32与天锐绿盾加密软件对比:哪款防泄密软件适合您的企业?

企业数据泄漏事故层出不穷&#xff0c;为了有效防止机密信息的泄露&#xff0c;选择一款合适的防泄密软件显得尤为重要。Ping32和天锐绿盾加密软件都是市场上比较受欢迎的防泄密工具&#xff0c;那么它们各自的优势和差异是什么呢&#xff1f;让我们一起来了解。 1. 安全性&…

PDF拆分之怎么对批量的PDF文件进行分割-免费PDF编辑工具分享

>>更多PDF文件处理应用技巧请前往 96缔盟PDF处理器 主页 查阅&#xff01; ——————————————————————————————————————— 当然了&#xff0c;单个文件或者其他任意的文件个数的拆分也是支持的&#xff01; 序言 我之前的文章也有…

简易url解码器(定义python单行函数工具)

被%编码的url如同天书&#xff0c;自拟一个单行函数解析还原&#xff0c;方便相认。 (笔记模板由python脚本于2024年12月05日 15:14:17创建&#xff0c;本篇笔记适合学习Url的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&…

JavaWeb项目打包、部署至Tomcat并启动的全程指南(图文详解)

前言 我们想要部署一个javaWeb项目到tomcat上&#xff0c;需要了解一些概念 什么是tomcat&#xff1f; Tomcat 是 Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;下的一个开源项目&#xff0c;主要用于实现 Java Servlet、JavaServer Pages&#xff08;…

【笔记2-5】ESP32:freertos消息队列

主要参考b站宸芯IOT老师的视频&#xff0c;记录自己的笔记&#xff0c;老师讲的主要是linux环境&#xff0c;但配置过程实在太多问题&#xff0c;就直接用windows环境了&#xff0c;老师也有讲一些windows的操作&#xff0c;只要代码会写&#xff0c;操作都还好&#xff0c;开发…

亚马逊云科技大语言模型加速OCR应用场景发展

目录 前言Amazon Bedrock关于OCR解决方案Amazon Bedrock进行OCR关键信息提取方案注册亚马逊账号API调用环境搭建 总结 前言 大语言模型是一种基于神经网络的自然语言处理技术&#xff0c;它能够学习和预测自然语言文本中的规律和模式&#xff0c;可以理解和生成自然语言的人工…

贪心算法 part03

文章参考来源代码随想录 134. 加油站 方法一分类讨论&#xff1a; 情况一&#xff1a;如果gas的总和小于cost总和&#xff0c;那么无论从哪里出发&#xff0c;一定是跑不了一圈的 情况二&#xff1a;rest[i] gas[i]-cost[i]为一天剩下的油&#xff0c;i从0开始计算累加到最…

【JAVA练习】力扣860.柠檬水找零

题目&#xff1a; 解题思路&#xff1a; 可能面临3种面额&#xff0c; 5美元&#xff0c;不找还&#xff0c;5美元钞票数量加110美元&#xff0c;找还5美元&#xff0c;5美元钞票数量减1&#xff0c;10美元钞票加120美元&#xff0c;找还15美元&#xff0c;分为一张10美元 一…

Telnet不安全?如何配置使用更安全的STelnet远程登录华为AR1000V路由器?

在上一篇文章中&#xff0c;我们介绍了如何配置一台全新的AR1000V&#xff0c;来实现通过Telnet远程登录设备&#xff08;如何配置使用Telnet远程登录华为AR1000V路由器&#xff1f;&#xff09;。其实&#xff0c;在之前的文章中&#xff0c;我们已经介绍过Telnet是一种不安全…

UE----Ios打包笔记

UE 打包 IOS 软件 1.前期准备 1.1. 首先我们需要 一台装有Xcode 的MAC笔记本&#xff08;知道开机密码 最好是空的笔记本 剩余内存要大 &#xff09; 1.2. 一台IOS手机 1.3. 一个申请了开发者账户的 Apple ID (苹果账号) 知晓账号与密码最好 因为很麻烦 1.4. UE 需要 的 兼…

计算机毕业设计Python轨道交通客流预测分析可视化 智慧交通 机器学习 深度学习 人工智能 爬虫 交通大数据

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

windows10电脑缺少dll文件的解决方案,系统缺少dll修复指南

在使用Windows 10操作系统时&#xff0c;有时会遇到由于缺少某些动态链接库&#xff08;Dynamic Link Library, 简称DLL&#xff09;文件而导致程序无法正常运行的问题。本指南将介绍几种解决此类问题的方法。 什么是DLL文件&#xff1f; DLL文件是Windows系统中的一种特殊类型…

并发编程(15)——基于同步方式的线程安全的栈和队列

文章目录 十四、day141. 线程安全的栈1.1 存在隐患的栈容器1.2 优化后的栈容器 2. 线程安全的队列2.1 基于智能指针的线程安全的队列2.2 不同互斥量管理队首、队尾的队列 十四、day14 在并发编程&#xff08;1&#xff09;并发编程&#xff08;5&#xff09;中&#xff0c;我们…

装箱问题的三种解法

有一个箱子容量为V&#xff08;正整数&#xff0c;0≤v≤20000&#xff09;&#xff0c;同时有n个物品&#xff08;0< n ≤30&#xff09;&#xff0c;每个物品有一个体积&#xff08;正整数&#xff09;。 要求n个物品中&#xff0c;任取若干个装入箱内&#xff0c;使箱子的…

万物可爬(以爬取浏览器井盖图片为例)

我们以爬取 井盖图片 这个链接中的图片为例&#xff1a; 点击F12 并选中其中一张图片 &#xff0c;得到它的信息。具体如下&#xff1a;我们可以编写对应的正则表达式&#xff1a; <img[^>]*src"(.*?)"[^>]*alt"井盖图片 的图像结果"[^>]*&g…

【AI系统】轻量级CNN模型新进展

CNN 模型小型化&#xff08;下&#xff09; 在本文会接着介绍 CNN 模型的小型化&#xff0c;除了第二篇文章提到的三个模型外&#xff0c;在本章节会继续介绍 ESPNet 系列&#xff0c;FBNet 系列&#xff0c;EfficientNet 系列和 GhostNet 系列。 ESPNet 系列 ESPNetV1 ESP…