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

基础算法bfs -剪枝问题

问题描述:一个迷宫有 NXM 格,有一些格子是地板,能走;有一些格子是障碍,不能走。给一个起点S和一个终点D。一只小狗从 S出发,每步走一块地板,在每块地员不能停留,而且走过的地板都不能再走。给定一个 T,问小狗能正好走 T步到达D吗?输入:有很多测试样例。每个测试中,第1行输入整数 N,M,T(1<N,M<7,0<T<50)。后面N 行中,每行输入M 个字符,有这些字符可以输入:'X':墙;S':起点;D:终点;",:地板。最后一行输入'000',表示输入结束。


输出:每个测试,如果狗能到达,输出YES,否则输出 NO。

#include <iostream>
using namespace std;
char mat[8][8], visit[8][8];
int n, m, t;
int flag;
int a, b, c, d;
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
#define check(xx,yy)(xx>=0&&yy>=0&&xx<n&&yy<n)
void dfs(int time,int x,int y)
{if (flag)return;if (mat[x][y] =='D'){if(time==t)flag = 1;return;}int tem = t - time - (abs(c - x) + abs(d - y));if (tem < 0) return;for (int i = 0; i < 4; i++){int xx = x + dir[i][0];int yy = y + dir[i][1];if (check(xx, yy) && mat[xx][yy] != 'X' && !visit[xx][yy]){visit[xx][yy] = 1;dfs(time + 1, xx, yy);visit[xx][yy] = 0;}}return;
}void solve()
{cin >> n >> m >> t;	for (int i = 0; i < n; i++){int ts = 0;for (int j = 0; j < m; j++){cin >> mat[i][j];if (mat[i][j] == '0')ts++;if ('S'== mat[i][j]){a = i;b = j;}if ('D' == mat[i][j]){c = i;d = j;}}if (ts==3) break;}memset(visit, 0, sizeof(visit));int tem = t - abs(c - a) - abs(d - b);if (tem &1) { cout << "N0"; return; }flag = 0;visit[a][b] = 1;dfs(0, a, b);if (flag){cout << "YES" << endl;}else{cout << "NO" << endl;}
}
signed main()
{ios::sync_with_stdio;cin.tie(0);cout.tie(0);int num = 1;while (num--){solve();}
}

相关文章:

基础算法bfs -剪枝问题

问题描述:一个迷宫有 NXM 格,有一些格子是地板,能走;有一些格子是障碍,不能走。给一个起点S和一个终点D。一只小狗从 S出发,每步走一块地板&#xff0c;在每块地员不能停留&#xff0c;而且走过的地板都不能再走。给定一个 T,问小狗能正好走 T步到达D吗?输入:有很多测试样例。…...

在Meteor Lake上测试基于Stable Diffusion的AI应用

上个月刚刚推出的英特尔新一代Meteor Lake CPU&#xff0c;预示着AI PC的新时代到来。AI PC可以不依赖服务器直接在PC端处理AI推理工作负载&#xff0c;例如生成图像或转录音频。这些芯片的正式名称为Intel Core Ultra处理器&#xff0c;是首款配备专门用于处理人工智能任务的 …...

情人节心动礼物:共度情人节美好时刻的礼物推荐

情人节&#xff0c;这个充满浪漫与爱意的特殊日子&#xff0c;总是让人心跳加速&#xff0c;期待着与爱人共享甜蜜时光。在这一天&#xff0c;送出一份精心挑选的礼物&#xff0c;不仅能够表达你对另一半无尽的爱意&#xff0c;更能让这份爱升华&#xff0c;成为你们爱情故事中…...

远程手机搭建Termux环境,并通过ssh连接Termux

背景 Termux只能通过鼠标点击&#xff0c;无法使用电脑键盘&#xff0c;输入速度很慢&#xff0c;你想通过ssh 连接Termux&#xff0c;获得友好体验搞了个云手机&#xff0c;想像普通手机那样充当服务器想把自己的手机公开到局域网中供同事调试想把自己的模拟器公开到局域网中…...

基于EdgeWorkers的边缘应用如何进行单元测试?

随着各行各业数字化转型的持续深入&#xff0c;越来越多企业开始选择将一些应用程序放在距离最终用户更近的边缘位置来运行&#xff0c;借此降低延迟&#xff0c;提高应用程序响应速度&#xff0c;打造更出色的用户体验。 相比传统集中部署和运行的方式&#xff0c;这种边缘应…...

【linux】校招中的“熟悉linux操作系统”一般是指达到什么程度?

这样&#xff0c;你先在网上找一套完整openssh升级方案&#xff08;不是yum或apt的&#xff0c;要源码安装的&#xff09;&#xff0c;然后在虚拟机上反复安装测试&#xff0c;直到把他理解了、背下来。 面试的时候让你简单说说linux命令什么的&#xff0c;你就直接把这个方案…...

【CSS系列】常用容易忽略的css

user-select user-select 是一个 CSS 属性&#xff0c;用于控制用户是否可以选择文本。通过设置 user-select 的值&#xff0c;可以决定用户是否可以选择元素中的文本&#xff0c;以及如何选择文本。 auto&#xff1a;默认值。浏览器可以选择文本。none&#xff1a;用户不能选…...

Java 数据结构 二叉树(二)红黑树

目录 数据结构图-树 简介 规则 旋转 重新着色 红黑树构建过程 前言-与正文无关 生活远不止眼前的苦劳与奔波&#xff0c;它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中&#xff0c;我们往往容易陷入工作的漩涡&#xff0c;忘记了停下脚步&#xf…...

React18-完成弹窗封装

弹框封装 用法 // 创建 userRef.current?.open(create) // 修改 userRef.current?.open(edit,values){/* 创建用户 */} <CreateUser mRef{userRef} update{} />组件暴露open方法 文档地址&#xff1a;https://react.dev/reference/react/useImperativeHandle useIm…...

蓝桥杯2024/1/31-----底层测试模板

和之前一样建好工程文件夹&#xff0c;里边包含User&#xff08;放工程文件&#xff0c;mian.c&#xff09;、Driver&#xff08;存放底层文件如Led.c&#xff0c;Led.h等&#xff09; 新建的工程先搭建框架&#xff0c;可以先书写底层函数&#xff08;此次书写了四个函数并包含…...

蓝桥杯备战(AcWing算法基础课)-高精度-乘-低精度

目录 前言 1 题目描述 2 分析 2.1 关键代码 2.2 关键代码分析 3 代码 前言 详细的代码里面有自己的理解注释 1 题目描述 给定两个非负整数&#xff08;不含前导 00&#xff09; A 和 B&#xff0c;请你计算 AB 的值。 输入格式 共两行&#xff0c;第一行包含整数 A&a…...

C++设计模式-里氏替换原则

里氏替换原则定义了继承规范。&#xff08;封装、继承、多态&#xff09; 定义1&#xff1a;类型S对象o1&#xff0c;类型T对象o2&#xff0c;o1换成o2时程序意图不变&#xff0c;那么S是T的子类。 定义2&#xff1a;使用子类不破坏父类的意图。 注意&#xff1a;如果子类不…...

compose LazyColumn + items没有自动刷新问题

val dataLists by remember { mutableStateOf(datas) } 数据更改后列表不刷新问题。 val dataLists by remember { mutableStateOf(datas) } LazyColumn(modifier Modifier.padding(top 5.dp)) {items(dataLists) {....}} 可以将mutableStateOf 改为mutableStateListOf解决…...

Java八大常用排序算法

1冒泡排序 对于冒泡排序相信我们都比较熟悉了&#xff0c;其核心思想就是相邻元素两两比较&#xff0c;把较大的元素放到后面&#xff0c;在一轮比较完成之后&#xff0c;最大的元素就位于最后一个位置了&#xff0c;就好像是气泡&#xff0c;慢慢的浮出了水面一样 Jave 实现 …...

编程笔记 html5cssjs 075 Javascript 常量和变量

编程笔记 html5&css&js 075 Javascript 常量和变量 一、JavaScript 变量二、JavaScript 常量三、示例&#xff1a;小结&#xff1a; 在JavaScript中&#xff0c;变量和常量是用来存储数据的占位符。它们的主要区别在于可变性&#xff1a;变量的值可以改变&#xff0c;而…...

题目 1159: 偶数求和

题目描述: 有一个长度为n(n<100)的数列&#xff0c;该数列定义为从2开始的递增有序偶数&#xff08;公差为2的等差数列&#xff09;&#xff0c;现在要求你按照顺序每m个数求出一个平均值&#xff0c;如果最后不足m个&#xff0c;则以实际数量求平均值。编程输出该平均值序…...

呼吸灯--FPGA

目录 1.breath_led.v 2.tb_breath_led.v 呼吸灯就是从完全熄灭到完全点亮&#xff0c;再从完全点亮到完全熄灭。具体就是通过控制PWM的占空比控制亮灭程度。 绘制PWM波的步骤就是&#xff0c;首先灯是在第一个时钟周期保持高电平熄灭状态&#xff0c;在第二个时钟周期保持1/1…...

MySQL数据库①_MySQL入门(概念+使用)

目录 1. 数据库的概念 1.1 数据库的存储介质 1.2 主流数据库 2. MySQL的基本使用 2.1 链接数据库 2.2 服务器管理 2.3 数据库&#xff0c;服务器和表关系 2.4 简单MySQL语句 3. MySQL架构 4. SQL分类 5. 存储引擎 本篇完。 1. 数据库的概念 数据库是按照数据结构来…...

虚幻UE 特效-Niagara特效实战-魔法阵

回顾Niagara特效基础知识&#xff1a;虚幻UE 特效-Niagara特效初识 其他四篇实战&#xff1a;UE 特效-Niagara特效实战-烟雾、喷泉、 虚幻UE 特效-Niagara特效实战-火焰、烛火、 虚幻UE 特效-Niagara特效实战-雨天、 虚幻UE 特效-Niagara特效实战-眩晕。 本篇笔记记录了使用空模…...

Qt多语言翻译

Qt多语言翻译概述 Qt提供了非常简单易用的多语言翻译机制&#xff0c;其核心类为QTranslator.概括来说就是利用Qt的lupdate工具将项目中所有tr函数包裹的字符串提取到.ts文件中&#xff0c;然后使用Qt Linguist由专门的翻译人员对提取的.ts文件进行逐个单词短语的翻译工作. 翻译…...

终极罗技鼠标宏压枪指南:告别PUBG后坐力困扰的3个秘诀

终极罗技鼠标宏压枪指南&#xff1a;告别PUBG后坐力困扰的3个秘诀 【免费下载链接】logitech-pubg PUBG no recoil script for Logitech gaming mouse / 绝地求生 罗技 鼠标宏 项目地址: https://gitcode.com/gh_mirrors/lo/logitech-pubg 还在为绝地求生中的武器后坐力…...

PowerShell-Suite终极指南:10个高级Windows安全工具深度解析

PowerShell-Suite终极指南&#xff1a;10个高级Windows安全工具深度解析 【免费下载链接】PowerShell-Suite My musings with PowerShell 项目地址: https://gitcode.com/gh_mirrors/po/PowerShell-Suite PowerShell-Suite是一个功能强大的Windows安全工具集合&#xff…...

QT开发环境搭建:如何在Linux上快速配置Python和C++支持(含清华镜像源加速)

Linux下高效搭建QT开发环境&#xff1a;Python与C双语言支持实战指南 在Linux系统上搭建QT开发环境是许多跨平台应用开发者的必经之路。不同于Windows或macOS的一键式安装&#xff0c;Linux环境下的配置往往需要处理更多依赖关系和系统级设置。本文将带你从零开始&#xff0c;在…...

MAI-UI-8B应用案例:医疗登记表智能填充实战

MAI-UI-8B应用案例&#xff1a;医疗登记表智能填充实战 1. 医疗表单处理的痛点与解决方案 在医疗信息化系统中&#xff0c;患者登记表是每个医疗机构每天都要处理的基础文档。传统方式下&#xff0c;医护人员需要手动填写大量重复信息&#xff0c;不仅效率低下&#xff0c;还…...

告别景深烦恼:用PyTorch+PyQt5打造你的专属多焦点图像融合桌面工具(附完整源码)

告别景深烦恼&#xff1a;用PyTorchPyQt5打造你的专属多焦点图像融合桌面工具 每次拍摄微距或静物时&#xff0c;是否总在景深和清晰度之间纠结&#xff1f;按下快门后才发现前景清晰时背景模糊&#xff0c;背景聚焦时前景又失焦。专业摄影师会告诉你&#xff1a;这是光学镜头的…...

obsidian-skills高级搜索技巧:快速找到需要的功能

obsidian-skills高级搜索技巧&#xff1a;快速找到需要的功能 【免费下载链接】obsidian-skills Agent skills for Obsidian. Teach your agent to use Markdown, Bases, JSON Canvas, and use the CLI. 项目地址: https://gitcode.com/GitHub_Trending/ob/obsidian-skills …...

BIOS更新全攻略:从版本检查到安全升级的实用指南

1. BIOS更新前的必要准备 每次打开电脑时&#xff0c;那个一闪而过的黑底白字界面就是BIOS&#xff08;基本输入输出系统&#xff09;&#xff0c;它就像是电脑硬件的"总指挥"。我见过太多人因为盲目刷BIOS导致主板报废的案例&#xff0c;所以更新前一定要做好这些准…...

Linux文件系统探秘:当你删除一个文件时,inode位图究竟发生了什么变化?

Linux文件系统探秘&#xff1a;当你删除一个文件时&#xff0c;inode位图究竟发生了什么变化&#xff1f; 在Linux系统中&#xff0c;删除文件看似是一个简单的操作&#xff0c;但背后却隐藏着一系列精密的元数据操作。对于系统开发者和运维人员而言&#xff0c;理解这一过程不…...

OpenClaw云端体验指南:星图平台Qwen3-14B镜像+OpenClaw沙盒部署

OpenClaw云端体验指南&#xff1a;星图平台Qwen3-14B镜像OpenClaw沙盒部署 1. 为什么选择云端沙盒体验&#xff1f; 第一次接触OpenClaw时&#xff0c;我尝试在本地MacBook上部署&#xff0c;结果被复杂的依赖关系和环境配置劝退。直到发现星图平台的Qwen3-14B镜像OpenClaw沙…...

OpenClaw性能调优:Qwen3-14B镜像响应速度提升3倍实操

OpenClaw性能调优&#xff1a;Qwen3-14B镜像响应速度提升3倍实操 1. 为什么需要性能调优&#xff1f; 上周我在用OpenClaw自动处理100份PDF文档时&#xff0c;发现一个奇怪现象&#xff1a;同样的任务&#xff0c;晚上执行比白天快得多。经过排查才发现&#xff0c;白天我的本…...