当前位置: 首页 > news >正文

AcWing 24:机器人的运动范围 ← BFS、DFS

【题目来源】
https://www.acwing.com/problem/content/description/22/


【题目描述】
地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0) 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请依次输入k,m,n,问该机器人能够达到多少个格子?

注意:0<=m<=50,0<=n<=50,0<=k<=100

【算法分析】
◆DFS算法模板:
https://blog.csdn.net/hnjzsyjyj/article/details/125801217

void dfs(int step){判断边界{输出解 }尝试每一种可能{满足check条件{标记继续下一步:dfs(step+1)恢复初始状态(回溯的时候要用到)}}
}

◆BFS算法模板:https://blog.csdn.net/hnjzsyjyj/article/details/118736059

助记:建-入-量:头-出-入”。其中,“建-入-量:头-出-入”各字的解析如下:
建:建队
入:入队
量:队中元素个数。作为while循环的条件。
头:队头
出:出队
入:入队

一个记忆场景,“小猫咪在好的洞口,想洞。先用胡子过洞口大小后,然后用头出入洞”。

【算法代码:DFS】

#include <bits/stdc++.h>
using namespace std;const int maxn=105;
int flag[maxn][maxn];
int sum=0;int dfs(int x,int y,int k,int m,int n) {if(flag[x][y]==1 || x>=m || y>=n || (x/10+x%10+y/10+y%10)>k) return 0;flag[x][y]=1;sum=dfs(x+1,y,k,m,n)+dfs(x,y+1,k,m,n)+1;return sum;
}int movingCount(int k,int m,int n){for(int i=0;i<m;i++){for(int j=0;j<n;j++){flag[i][j]=0;}}return dfs(0,0,k,m,n);
}int main(){int k,m,n;cin>>k>>m>>n;cout<<movingCount(k,m,n)<<endl;return 0;
}/*
in:5 0 0
out:0in:7 4 5
out:20in:18 40 40
out:1484
*/

【算法代码:BFS】

#include <bits/stdc++.h>
using namespace std;const int maxn=105;
int flag[maxn][maxn];
int sum=0;int movingCount(int k,int m,int n) {if(m==0 || n==0) return 0; //very importantfor(int i=0; i<m; i++) {for(int j=0; j<n; j++) {flag[i][j]=0;}}queue<pair<int,int>> q;q.push({0,0});flag[0][0]=1;int dx[]= {0,0,-1,1};int dy[]= {-1,1,0,0};while(!q.empty()) {auto t=q.front(); //pair<int,int> t=q.front();q.pop();int x=t.first;int y=t.second;sum++;for(int i=0; i<4; i++) {int nx=x+dx[i];int ny=y+dy[i];if(nx<0 || ny<0) continue;if(flag[nx][ny]==1 || nx>=m || ny>=n || (nx/10+nx%10+ny/10+ny%10)>k) continue;q.push({nx,ny});flag[nx][ny]=1;}}return sum;
}int main() {int k,m,n;cin>>k>>m>>n;cout<<movingCount(k,m,n)<<endl;return 0;
}/*
in:5 0 0
out:0in:7 4 5
out:20in:18 40 40
out:1484
*/




【参考文献】
https://blog.csdn.net/qq_40184885/article/details/89483505
https://www.cnblogs.com/wzw0625/p/12731031.html




 

相关文章:

AcWing 24:机器人的运动范围 ← BFS、DFS

【题目来源】https://www.acwing.com/problem/content/description/22/【题目描述】 地上有一个 m 行和 n 列的方格&#xff0c;横纵坐标范围分别是 0∼m−1 和 0∼n−1。 一个机器人从坐标 (0,0) 的格子开始移动&#xff0c;每一次只能向左&#xff0c;右&#xff0c;上&#…...

RF手机天线仿真介绍(一):金属边框天线和LDS天线

目录 简介LDS天线LDS天线仿真 金属边框天线金属边框天线仿真 简介 最早的手机是外置式天线&#xff0c;从NOKIA开始采用内置式天线&#xff0c;开始采用内置金属片&#xff08;一般是0.1MM厚的不锈钢片冲压而成&#xff09;&#xff0c;随后为降低成本&#xff0c;后来改用FPC…...

动手学深度学习—深度学习计算(层和块、参数管理、自定义层和读写文件)

目录 1. 层和块1.1 自定义块1.2 顺序块1.3 在前向传播函数中执行代码 2. 参数管理2.1 参数访问2.1.1 目标参数2.1.2 一次性访问所有参数2.1.3 从嵌套块收集参数 2.2 参数初始化2.2.1 内置初始化2.2.2 自定义初始化 2.3 参数绑定 3. 自定义层3.1 不带参数的层3.2 带参数的层 4. …...

Pytest学习教程_测试报告生成pytest-html(三)

前言 pytest-html 是一个用于生成漂亮的 HTML 测试报告的 pytest 插件。它可以方便地将 pytest 运行的测试结果转换为易于阅读和理解的 HTML 报告&#xff0c;提供了丰富的测试结果展示功能和交互性。 一、安装 # 版本查看命令 pytest版本&#xff1a; pytest --version pyte…...

模块化原理:source-map

1. webpack打包基本配置 1.安装webpack与webpack-cli npm i webpack webpack-cli 2.配置 "build":"webpack" 3. 新建webpack.config.js const path require(path); module.exports {// mode: "development",// 默认production&#xff08;什么…...

【C++】开源:ncurses终端TUI文本界面库

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍ncurses终端文本界面库。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下…...

C语言的_Bool类型

C99 新增了 _Bool 类型&#xff0c;用于表示布尔值&#xff0c;即逻辑值 true 和 false。 _Bool 类型也是一种整数类型。 原则上 _Bool 类型只占用一位存储空间。 C语言将非 0 的数当为 true&#xff0c;0 当为 false。 代码示例&#xff1a; #include<stdio.h> int…...

【python爬虫】获取某一个网址下面抓取所有的a 超链接下面的内容

import requests as rq from bs4 import BeautifulSoup as bs import re# rooturl是传的是我需要查询和抓取的一个网址&#xff0c;可以是html js 等 def gethtml(rooturl, encoding"utf-8"):#默认解码方式utf-8response rq.get(rooturl)response.encoding encodin…...

AutoDL从0到1搭建stable-diffusion-webui

前言 AI绘画当前非常的火爆&#xff0c;随着Stable diffusion&#xff0c;Midjourney的出现将AI绘画推到顶端&#xff0c;各大行业均受其影响&#xff0c;离我们最近的AI绘画当属Stable diffusion&#xff0c;可本地化部署&#xff0c;只需电脑配备显卡即可完成AI绘画工作&…...

手动调整broker扩容后的旧topic分区

在broker扩容了两台机器之后&#xff0c;想让旧topic&#xff1a;quickstart76-events的分区也能铺满broker 1、创建一个topics-to-move.json json文件 $ vim topics-to-move.json json {"topics": [{"topic":"quickstart76-events"}],"v…...

【LeetCode-简单】剑指 Offer 25. 合并两个排序的链表(详解)

题目 入两个递增排序的链表&#xff0c;合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1&#xff1a; 输入&#xff1a;1->2->4, 1->3->4 输出&#xff1a;1->1->2->3->4->4 本题与主站 21 题相同&#xff1a;力扣 题目地址&#x…...

Java版工程行业管理系统源码-专业的工程管理软件-em提供一站式服务

​ Java版工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离 功能清单如下&#xff1a; 首页 工作台&#xff1a;待办工作、消息通知、预警信息&#xff0c;点击可进入相应的列表 项目进度图表&#xff1a;选择&#xff08;总体或单个&#xff09;项目…...

【Spring】简化事件的使用,Spring提供了2种使用方式

Spring中事件可以配置顺序&#xff0c;利用线程池还可以做异步线程通知。怎么样使用事件&#xff1f;Spring简化事件的使用&#xff0c;Spring提供了2种使用方式&#xff1a;面向接口和面向EventListener注解。 1,面相接口的方式 案例 发布事件 需要先继承ApplicationEventP…...

探究Spring事务:了解失效场景及应对策略

在现代软件开发中&#xff0c;数据的一致性和完整性是至关重要的。为了保证这些特性&#xff0c;Spring框架提供了强大的事务管理机制&#xff0c;让开发者能够更加自信地处理数据库操作。然而&#xff0c;事务并非银弹&#xff0c;存在一些失效的情景&#xff0c;本文将带您深…...

Maven Manifold 条件编译

Maven 配置 通过 Maven 的不同 profile 实现不同环境传递不同符号。另外 lombok 可以 manifold 一同使用&#xff0c;见下方配置。 <properties><maven.compiler.source>8</maven.compiler.source><maven.compiler.target>8</maven.compiler.targ…...

4.数组与基本数学函数

一、数组 1.概念 数组是存放相同类型对象的容器&#xff0c;数组中存放的对象没有名字&#xff0c;而是要通过其所在的位置访问。数组中的每一个元素都相当于一个普通的变量&#xff0c;可以和普通变量一样进行赋值操作。 数组可以帮助我们批量地处理相同数据类型的相关数据…...

python与深度学习(十六):CNN和宝可梦模型二

目录 1. 说明2. 宝可梦模型的CNN模型测试2.1 导入相关库2.2 加载模型2.3 设置保存图片的路径2.4 加载图片2.5 数据处理和归一化2.6 对图片进行预测2.7 显示图片 3. 完整代码和显示结果4. 多张图片进行测试的完整代码以及结果 1. 说明 本篇文章是对上篇文章宝可梦模型训练的模型…...

PTA 1030 Travel Plan

个人学习记录&#xff0c;代码难免不尽人意。 A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/h…...

MFC、Qt、WPF?该用哪个?

MFC、Qt和WPF都是流行的框架和工具&#xff0c;用于开发图形用户界面&#xff08;GUI&#xff09;应用程序。选择哪个框架取决于你的具体需求和偏好。MFC&#xff08;Microsoft Foundation Class&#xff09;是微软提供的框架&#xff0c;使用C编写&#xff0c;主要用于Windows…...

使用logback记录日志

1. Pom引用依赖 <dependency> <groupId>ch.qos.logback</groupId> <artifactId>logback-classic</artifactId> <version>1.2.11</version> </dependency> 2. logback.xml <?xml version"1.0" encoding"U…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...