深搜与回溯——扫地机器人问题解析与代码实现
一、题目内容
题目描述
扫地机器人在一个 n×m 的网格中从左上角(1,1)开始清扫。它按照以下规则移动:
如果当前位置的右边(同一行,下一列)没有被清扫过,它会向右移动。
如果右边无法移动,则向下移动。
如果右边和下方都无法移动,则尝试向左移动。
如果左边也无法移动,则尝试向上移动。
如果四个方向都无法移动,则停止清扫。
要求输出清扫完成后的网格,其中每个位置的值表示机器人清扫该位置的顺序。
输入:
两个整数 n 和 m,表示网格的行数和列数(1≤n,m≤100)。输出:
一个 n×m 的网格,每个位置的值表示机器人清扫该位置的顺序。样例:
输入:
3 4输出:
1 2 3 4
8 9 10 5
7 6 11 12
二、问题分析
问题本质:这是一个经典的“深度优先搜索”(DFS)问题,机器人按照特定规则在网格中移动,类似于“螺旋矩阵”的生成。
移动规则:机器人优先向右移动,其次向下、向左、向上。这可以通过递归实现,每次递归时检查四个方向是否可以移动。
终止条件:当机器人无法向任何方向移动时,递归结束。
数据结构:使用二维数组
a来存储每个位置的清扫顺序。
三、代码解析
以下是代码的详细解析:
# 输入网格的行数和列数 n, m = map(int, input().split())# 初始化一个 (n+1)×(m+1) 的二维数组,用于存储清扫顺序 a = [[0 for i in range(m + 1)] for i in range(n + 1)]def fun(x, y, z):"""递归函数,模拟机器人的清扫过程。:param x: 当前行:param y: 当前列:param z: 当前清扫顺序"""a[x][y] = z # 标记当前位置的清扫顺序# 向右移动(优先级最高)if y + 1 <= m and a[x][y + 1] == 0:fun(x, y + 1, z + 1)# 向下移动elif x + 1 <= n and a[x + 1][y] == 0:fun(x + 1, y, z + 1)# 向左移动elif y - 1 >= 1 and a[x][y - 1] == 0:fun(x, y - 1, z + 1)# 向上移动elif x - 1 >= 1 and a[x - 1][y] == 0:fun(x - 1, y, z + 1)# 从左上角 (1,1) 开始清扫,初始清扫顺序为 1 fun(1, 1, 1)# 输出清扫完成后的网格 for i in range(1, n + 1):for j in range(1, m + 1):print("{: >3}".format(a[i][j]), end='') # 格式化输出,宽度为3print() # 换行四、代码运行逻辑
初始化网格:创建一个大小为 (n+1)×(m+1) 的二维数组
a,并初始化所有值为 0。多出的一行和一列用于简化边界条件的判断。递归函数
fun:
标记当前位置的清扫顺序。
按照“右、下、左、上”的顺序尝试移动。
如果某个方向可以移动(即目标位置未被清扫),则递归调用
fun。递归终止条件:当四个方向都无法移动时,递归结束。
输出结果:格式化输出网格,每个位置的值表示清扫顺序。
五、运行结果示例
输入:
3 4输出:
复制
1 2 3 48 9 10 57 6 11 12解释:
机器人从 (1,1) 开始,依次向右移动,清扫顺序为 1, 2, 3, 4。
无法向右移动时,向下移动,清扫顺序为 5。
继续向左移动,清扫顺序为 6, 7, 8。
继续向下移动,清扫顺序为 9, 10。
最后向上移动,清扫顺序为 11, 12。
六、总结
这道题考察了深度优先搜索(DFS)的实现,以及递归的使用。通过模拟机器人的移动规则,我们可以高效地生成清扫顺序。代码中通过递归实现了四个方向的优先级判断,并通过二维数组存储了清扫顺序。希望这篇文章能帮助你更好地理解和解决类似问题。
相关文章:
深搜与回溯——扫地机器人问题解析与代码实现
一、题目内容 题目描述 扫地机器人在一个 nm 的网格中从左上角(1,1)开始清扫。它按照以下规则移动: 如果当前位置的右边(同一行,下一列)没有被清扫过,它会向右移动。 如果右边无法移动…...
【大数据2025】Hadoop 万字讲解
文章目录 一、大数据通识大数据诞生背景与基本概念大数据技术定义与特征大数据生态架构概述数据存储数据计算与易用性框架分布式协调服务和任务调度组件数仓架构流处理架构 二、HDFSHDFS 原理总结一、系统架构二、存储机制三、数据写入流程四、心跳机制与集群管理 安全模式&…...
win内核内部直接irp读取文件写入文件
#include <ntifs.h> #include <ntddk.h> #define TAG_NAME tlfF // FltF in reverse #define BUFFER_SIZE PAGE_SIZE // 驱动设备扩展结构 typedef struct _DEVICE_EXTENSION { PDEVICE_OBJECT DeviceObject; UNICODE_STRING DeviceName; UNICODE_STRIN…...
1. 基于图像的三维重建
1. 基于图像的三维重建 核心概念三维重建中深度图、点云的区别?深度图点云总结 深度图到点云还需要什么步骤?1. **获取相机内参**2. **生成相应的像素坐标**3. **计算三维坐标**4. **构建点云**5. **处理颜色信息(可选)**6. **去除…...
如何确保Python爬虫不违反微店规定
在使用Python爬虫获取微店商品详情时,确保爬虫行为符合微店的规定和相关法律法规至关重要。以下是一些关键步骤和注意事项,帮助你合法合规地使用爬虫技术: 一、遵守法律法规 在使用爬虫技术时,必须严格遵守《网络安全法》、《个…...
Spring Event和MQ的区别和使用场景
概念 Spring事件(Spring Event)是Spring框架的一项功能,它允许不同组件之间通过发布-订阅机制进行解耦的通信。 MQ一般是一个独立的中间件,它可以通过消息队列对消息进行传递和存储,生产者将消息发送到MQ,…...
SpringBoot:websocket 实现后端主动前端推送数据
简单说明下websocket实用场景。 实时通信领域:社交聊天弹幕多玩家游戏协同编辑股票基金实时报价体育实况更新视频会议/聊天基于位置的应用在线教育智能家居等需要高实时性的场景 一、服务端代码 pom.xml: <dependencies><dependency><…...
嵌入式硬件篇---PID控制
文章目录 前言第一部分:连续PID1.比例(Proportional,P)控制2.积分(Integral,I)控制3.微分(Derivative,D)控制4.PID的工作原理5..实质6.分析7.各种PID控制器P控…...
小程序获取微信运动步数
1、用户点击按钮,在小程序中触发getuserinfo方法,获取用户信息 <scroll-view class"scrollarea" scroll-y type"list"><view class"container"><button bind:tap"getLogin">获取</button&…...
5G 核心网 相关概念快速入门
在我们开始阅读3GPP协议来学习5G核心网之前, 不妨来看看我之前整理的PPT,快速学习核心网相关概念, 以及5G转发面PFCP协议的相关核心知识。 涵盖了最精简的核心骨干内容,助你轻松上阵。 讲解目标 3GPP和相关协议 5G核心网架构模…...
【2024 年度总结】从小白慢慢成长
【2024 年度总结】从小白慢慢成长 1. 加入 CSDN 的契机2. 学习过程2.1 万事开头难2.2 下定决心开始学习2.3 融入技术圈2.4 完成万粉的目标 3. 经验分享3.1 工具的选择3.2 如何提升文章质量3.3 学会善用 AI 工具 4. 保持初心,继续前行 1. 加入 CSDN 的契机 首次接触…...
SAP POC 项目完工进度 - 收入确认方式【工程制造行业】【新准则下工程项目收入确认】
1. SAP POC收入确认基础概念 1.1 定义与原则 SAP POC(Percentage of Completion)收入确认方式是一种基于项目完工进度来确认收入的方法。其核心原则是根据项目实际完成的工作量或成本投入占预计总工作量或总成本的比例,来确定当期应确认的收…...
vue3+three.js加载glb模型
<template><div><!-- 亮度调节滑块 --><div class"controls"><label for"brightness">背景光亮度:</label><inputtype"range"id"brightness"v-model"brightness"min&quo…...
Golang Gin系列-4:Gin Framework入门教程
在本章中,我们将深入研究Gin,一个强大的Go语言web框架。我们将揭示制作一个简单的Gin应用程序的过程,揭示处理路由和请求的复杂性。此外,我们将探索基本中间件的实现,揭示精确定义路由和路由参数的技术。此外ÿ…...
25西湖ctf
2025西湖冬季 图片不全去我blog找👇 25西湖 | DDLS BLOG 文章所有参考将在文末给出 web web1 ssti 太简单的不赘述,知道用就行 {{cycler.__init__.__globals__.__builtins__[__import__](os).popen($(printf "\150\145\141\144\40\57\146\1…...
AI Agent:AutoGPT的使用方法
AutoGPT的使用方法 准备工作: 安装Python:确保你的电脑上安装了Python 3.8或更高版本。获取OpenAI API密钥:访问https://platform.openai.com/account/api-keys获取API密钥,并保存备用。获取Google API及Google Search Engine ID(可选):若要使用谷歌搜索功能,需访问htt…...
2024年博客之星主题创作|Android 开发:前沿技术、跨领域融合与就业技能展望
目录 引言 一、推动 Android 应用创新的核心力量 1.1 人工智能与机器学习的崛起 1.2 增强现实(AR)与虚拟现实(VR)的应用扩展 1.3 5G技术的推动 1.4 跨平台开发技术的成熟 1.4.1 React Native 1.4.2 Flutter 1.4.3 Taro …...
蓝桥杯小白备考指南
一、了解蓝桥杯 蓝桥杯大赛是工业和信息化部人才交流中心举办的全国性专业信息技术赛事 ,旨在促进软件和信息领域专业技术人才培养,提升高校毕业生的就业竞争力。比赛涵盖多个编程语言组别,如 Java、C/C、Python 等。不同组别和参赛类别&…...
面向对象的程序设计:以对象的方式进行思考
1 理解接口与实现的区别 以上一篇文章的电视机需要插电使用的例子继续来讲解: 对电视而言,插电使用,只需要标准的插座即可,具体的电从哪里来,是火力发电厂,或是太阳能发电,亦或是畜电池逆变供电,电视机是不需要关心的。 发电厂或供电设备属于实现,220V交流电插座属于…...
酵母三杂交实验全解析:从技术到应用【泰克生物】
酵母三杂交实验(Yeast Three-Hybrid, Y3H)是酵母双杂交(Y2H)技术的扩展,专门用于研究更复杂的分子相互作用,尤其是小分子与蛋白质间的相互作用。通过引入小分子作为第三方调节因子,酵母三杂交技…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
