深搜与回溯——扫地机器人问题解析与代码实现
一、题目内容
题目描述
扫地机器人在一个 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)技术的扩展,专门用于研究更复杂的分子相互作用,尤其是小分子与蛋白质间的相互作用。通过引入小分子作为第三方调节因子,酵母三杂交技…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
Matlab实现任意伪彩色图像可视化显示
Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中,如何展示好看的实验结果图像非常重要!!! 1、灰度原始图像 灰度图像每个像素点只有一个数值,代表该点的亮度(或…...
Python常用模块:time、os、shutil与flask初探
一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...
