CSP/信奥赛C++刷题训练:经典深搜例题(1):洛谷1605 :迷宫

CSP/信奥赛C++刷题训练:经典深搜例题(1):洛谷1605 :迷宫

在这里插入图片描述

题目描述

给定一个 N × M N \times M N×M 方格的迷宫,迷宫里有 T T T 处障碍,障碍处不可通过。

在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 N , M , T N,M,T N,M,T,分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 S X , S Y , F X , F Y SX,SY,FX,FY SX,SY,FX,FY S X , S Y SX,SY SX,SY 代表起点坐标, F X , F Y FX,FY FX,FY 代表终点坐标。

接下来 T T T 行,每行两个正整数,表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

1

提示

对于 100 % 100\% 100% 的数据, 1 ≤ N , M ≤ 5 1 \le N,M \le 5 1N,M5 1 ≤ T ≤ 10 1 \le T \le 10 1T10 1 ≤ S X , F X ≤ n 1 \le SX,FX \le n 1SX,FXn 1 ≤ S Y , F Y ≤ m 1 \le SY,FY \le m 1SY,FYm

使用深搜解题

#include<bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,fx,fy,ans=0; 
int a[6][6];//地图 
bool vis[6][6];//标记数组 
int dx[4]={-1,0,1,0};//上、右、下、左 
int dy[4]={0,1,0,-1};
void dfs(int x,int y){if(x==fx && y==fy){//边界条件 ans++;return;}for(int i=0;i<=3;i++){//遍历四个方向 int nx=x+dx[i];int ny=y+dy[i];//如果不超出边界,且不是障碍点,且没有走过 if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]==0 && vis[nx][ny]==0){vis[nx][ny]=1;//标记 dfs(nx,ny);//递归深搜 vis[nx][ny]=0;//回溯 } }}
int main(){cin>>n>>m>>t;cin>>sx>>sy>>fx>>fy;int x,y;for(int i=1;i<=t;i++){cin>>x>>y;a[x][y]=1;//障碍 }vis[sx][sy]=1; dfs(sx,sy);cout<<ans;return 0;
} 

文末彩蛋:

点击王老师青少年编程主页有更多精彩内容

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

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

相关文章

yolov8涨点系列之Concat模块改进

文章目录 Concat模块修改步骤(1) BiFPN_Concat3模块编辑(2)在__init_.pyconv.py中声明&#xff08;3&#xff09;在task.py中声明yolov8引入BiFPN_Concat3模块yolov8.yamlyolov8.yaml引入C2f_up模块 在YOLOv8中&#xff0c; concat模块主要用于将多个特征图连接在一起。其具体…

越权访问漏洞

V2Board Admin.php 越权访问漏洞 ## 漏洞描述 V2board面板 Admin.php 存在越权访问漏洞&#xff0c;由于部分鉴权代码于v1.6.1版本进行了修改&#xff0c;鉴权方式变为从Redis中获取缓存判定是否存在可以调用… V2Board Admin.php 越权访问漏洞 漏洞描述 V2board面板 Admin.ph…

安装和运行开发微信小程序

下载HBuilder uniapp官网 uni-app官网 微信开发者工具 安装 微信小程序 微信小程序 官网 微信小程序 配置 运行 注意&#xff1a;运行前需要开启服务端口 如果运行看不到效果&#xff0c;设置下基础库选别的版本 配置

小檗碱和卤代苄基异喹啉生物碱的代谢工程合成-文献精读79

De novo biosynthesis of berberine and halogenated benzylisoquinoline alkaloids in Saccharomyces cerevisiae 在 酿酒酵母&#xff08;Saccharomyces cerevisiae&#xff09;中从头合成小檗碱和卤代苄基异喹啉生物碱 小檗碱的酵母代谢工程生物合成-文献精读78 苄基异喹…

鸿蒙开发案例:七巧板

【1】引言&#xff08;完整代码在最后面&#xff09; 本文介绍的拖动七巧板游戏是一个简单的益智游戏&#xff0c;用户可以通过拖动和旋转不同形状的七巧板块来完成拼图任务。整个游戏使用鸿蒙Next框架开发&#xff0c;利用其强大的UI构建能力和数据响应机制&#xff0c;实现了…

【TS】九天学会TS语法——1.TypeScript 是什么

今天学习的是TypeScript 基础&#xff0c;目标是了解 TypeScript 的基本概念&#xff0c;安装 TypeScript&#xff0c;编写第一个 TypeScript 程序。 TypeScript 简介安装 TypeScriptTypeScript 编译过程编写第一个 TypeScript 程序 随着前端开发的不断发展&#xff0c;TypeScr…

Docker学习—Docker的安装与使用

Docker安装 1.卸载旧版 首先如果系统中已经存在旧的Docker&#xff0c;则先卸载&#xff1a; yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine2.配置Docker的yum库 首先…

69.ov5640摄像头HDMI灰度显示

&#xff08;1&#xff09;理论学习 灰度像素&#xff1a;在 RGB 颜色模型下&#xff0c;图像中每个像素颜色的 R、G、B 三种基色的分量值相等的像素。由灰度像素组成的灰度图像只能表现256中颜色&#xff08;或亮度&#xff09;&#xff0c;通常把灰度图像中像素的亮度称为灰…

Star Tower:开启数据存储新纪元

在科技飞速发展的当今时代&#xff0c;数据如同璀璨的星辰&#xff0c;闪耀着无尽的价值。而数据存储系统&#xff0c;则是承载这些星辰的浩瀚宇宙。Star Tower 以其卓越的性能和创新的理念&#xff0c;开启了数据存储的新纪元。 Star Tower 的分布式存储架构&#xff0c;是一…

基于SSM的企业管理系统(源码+lw+调试+技术指导)

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…

鸿蒙应用App测试-通用测试

注意&#xff1a;大家记得学完通用测试记得再学鸿蒙专项测试 鸿蒙应用App测试-专项测试&#xff08;DevEco Testing&#xff09;-CSDN博客 注意&#xff1a;博主有个鸿蒙专栏&#xff0c;里面从上到下有关于鸿蒙next的教学文档&#xff0c;大家感兴趣可以学习下 如果大家觉得…

掌握Qt调试技术

文章目录 前言一、Qt调试的基本概念二、Qt调试工具三、Qt调试实践四、Q调试技巧五、总结前言 在软件开发中,调试是一个至关重要的环节。Qt作为一个广泛使用的跨平台C++图形用户界面应用程序开发框架,其调试技术也显得尤为重要。本文将深入探讨Qt调试技术,帮助读者更好地掌握…

Qt中时间戳转化为时间

QT中时间和时间戳互相转化_currentsecssinceepoch-CSDN博客 qDebug()<<QDateTime::currentMSecsSinceEpoch(); 1730838034770 时间戳(Unix timestamp)转换工具 - 在线工具 (tool.lu) [static] qint64 QDateTime::currentMSecsSinceEpoch() Returns the number of milli…

势不可挡 创新引领 | 生信科技SOLIDWORKS 2025新品发布会·苏州站精彩回顾

2024年11月01日&#xff0c;由生信科技举办的SOLIDWORKS 2025新产品发布会在江苏苏州圆满落幕。现场邀请到制造业的专家学者们一同感受SOLIDWORKS 2025最新功能&#xff0c;探索制造业数字化转型之路。 在苏州站活动开场&#xff0c;达索系统专业客户事业部华东区渠道经理马腾飞…

ArcGIS006:ArcMap常用操作151-200例动图演示

摘要&#xff1a;本文介绍了ArcMap邻域分析、栅格表面分析、水文分析、区域分析、提取分析等工具箱中的工具功能。包括计算图层间点、线、面要素间的距离、位置和角度&#xff0c;创建缓冲区&#xff0c;添加计算信息到属性表&#xff0c;分割面要素&#xff0c;编号&#xff0…

关于马达驱动芯片AT6237的开发指南(兼容DRV8837)

一、芯片引脚介绍 1.芯片引脚 二、系统结构图 三、功能描述 逻辑功能

利用AI提升SEO效果的关键词策略

内容概要 在当今数字化时代&#xff0c;人工智能&#xff08;AI&#xff09;正逐步成为提升搜索引擎优化&#xff08;SEO&#xff09;效果的重要工具。SEO的核心在于关键词的选择与运用&#xff0c;而AI技术则为我们提供了一种智能化的分析和优化方案。通过对大量数据进行挖掘…

了解数据库设计中的反规范化

反规范化是指通过增加冗余数据来提高数据库的读取效率。也就是说,反规范化通过在表中增加冗余字段来减少数据库中的表连接,以提高查询速度。规范化和反规范化是关系型数据库设计中的两个重要方面,它们分别代表了数据组织方式上的两个不同方向。规范化是为了减少数据冗余和提…

【系统集成项目管理工程师教程】第10章 启动过程组

启动过程组包含制定项目章程和识别干系人两个过程&#xff0c;是项目的起始阶段&#xff0c;旨在协调各方期望&#xff0c;明确项目范围、目标与干系人&#xff0c;确保项目符合组织战略&#xff0c;为项目成功奠定基础&#xff0c;在项目管理中起着至关重要的引领作用。 10.…

斑马打印机如何与工业系统(如MES、ERP、数据库等)自动化通讯?

摘要&#xff1a;本文将介绍OPC Router与斑马&#xff08;Zebra&#xff09;打印机相结合的优势&#xff0c;探讨其在工业4.0和物联网领域的应用&#xff0c;以及如何通过简单配置实现数据传输和智能监控。 在工业生产过程中&#xff0c;标签打印环节至关重要。斑马&#xff08…