首页 > 其他分享 >1.5--1792:迷宫

1.5--1792:迷宫

时间:2024-11-08 18:30:10浏览次数:5  
标签:1.5 lb la -- 1792 int && hb ha

迷宫

题目传送门

思路:

  • 迷宫必须用深搜(我是深搜党)

  • 递归出口条件:

if(ha==hb&&la==lb) 
	{
		cout<<"YES"<<endl;
		flag=1;
}//判断是否是终点
  • 判断越界
if(dx>=0&&dx<n&&dy>=0&&dy<n&&s[dx][dy]=='.')
  • 主函数:
int main()
{
	int k;
	cin>>k;
	while(k--)//效果与for(int i=1;i<=k;i++)一样
	{
		cin>>n;
		for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>s[i][j];
		cin>>ha>>la>>hb>>lb;//输入
		if(s[ha][la]=='#'||s[hb][lb]=='#') cout<<"NO"<<endl;//判断起点和终点是否为障碍物,说实话题目没讲的话其实不加也没什么问题,只是会优化
		else
		{
			flag=0;//标记0
			dfs(ha,la);//用自定义函数
		}	
		if(flag==0) cout<<"NO"<<endl;//如果一种都没有,就是不行
	}
	return 0;
}

AC代码:

#include<bits/stdc++.h>
using namespace std;
char s[105][105];
int n,ha,la,hb,lb,dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}},flag;
void dfs(int ha,int la)
{
	if(ha==hb&&la==lb) 
	{
		cout<<"YES"<<endl;
		flag=1;
	}//判断是否是终点
	if(flag) return;
	for(int i=0;i<4;i++)
	{
		int dx=ha+dir[i][0];
		int dy=la+dir[i][1];//dx和dy移动
		if(dx>=0&&dx<n&&dy>=0&&dy<n&&s[dx][dy]=='.')//判断是否越界和是不是障碍物
		{
			s[dx][dy]='#';//标记为障碍物
			dfs(dx,dy);//递归调用
		}
	}
}
int main()
{
	int k;
	cin>>k;
	while(k--)//效果与for(int i=1;i<=k;i++)一样
	{
		cin>>n;
		for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>s[i][j];
		cin>>ha>>la>>hb>>lb;//输入
		if(s[ha][la]=='#'||s[hb][lb]=='#') cout<<"NO"<<endl;//判断起点和终点是否为障碍物,说实话题目没讲的话其实不加也没什么问题,只是会优化
		else
		{
			flag=0;//标记0
			dfs(ha,la);//用自定义函数
		}	
		if(flag==0) cout<<"NO"<<endl;//如果一种都没有,就是不行
	}
	return 0;
}

标签:1.5,lb,la,--,1792,int,&&,hb,ha
From: https://www.cnblogs.com/yhy2013/p/18535648

相关文章

  • [ZR] 城市
    source:zr二十联测day15C题意给定\(n\)个点\(m\)条边的图,求该图导出连通子图数量对2取模的结果。保证一条边两个端点编号差\(\le13\)。\(n\le50\)。分析原题相当于求连通块数量为1的导出子图的数量。考虑利用模数为2的性质。性质:答案等于\(\dfrac{\sum2^......
  • [2024.11.8]NOIP 模拟赛
    省流:若为IOI赛制,则全机房一定同分。赛时T1看上去不太会。首先发现最大的数字的位置是固定的,然后我大胆考虑将数字从大到小依次填充。对于当前数字,一共会有四种情况:\(a,b\)数组都有,此时显然位置固定。\(a\)有或\(b\)有,此时能填的位置显然是一行或一列,即这一行或一列上......
  • 使用 Mercury 语言编写简单 OCR 程序
    以下代码展示了如何使用Mercury语言实现基本的光学字符识别(OCR)功能。由于Mercury是一种逻辑编程语言,这里展示了它如何通过特定图像模式和字符的特征进行匹配。代码实现mercury:-modulesimple_ocr.:-interface.:-import_moduleio.更多内容访问ttocr.com或联系143642......
  • 【场景削减】基于DBSCAN密度聚类风电-负荷确定性场景缩减方法(Matlab代码实现)
     ......
  • 【多微电网】基于粒子群优化算法的面向配电网的多微电网协调运行与优化(Matlab代码实现
     ......
  • DDWT Pokemon League
    DDWTAssignmentTwoVersionChangesDetailsVersion1.0InitialReleaseVersion1.1UpdatedTask1toreflecttaskistocoverallcardtypes PokemonLeague Allworkistobedoneindividually andmustbeyourownwork.Youmust......
  • WPF+MVVM案例实战与特效(二十六)- 3D粒子方块波浪墙效果实现
    文章目录1、案例效果2、案例实现1、文件创建2.功能代码实现3、粒子功能应用1、前端布局与样式2、代码解释2、后端功能代码1、案例效果2、案例实现1、文件创建打开Wpf_Examples项目、Models文件夹下创建3D粒子模型类ParticleCubeWaveMode......
  • LLM APPLICATIONS ABILITIES LIMITS
    applicationandabilityhttps://arxiv.org/pdf/2402.15116LMAs,proficientinprocessingdiversedatamodalities,surpasslanguage-onlyagentsindecision-makingandresponsegenerationacrossvariedscenarios.Theiradaptabilitymakesthemexceptionallyu......
  • MECH E4320 Batch_Reactor_Ignition
    MECHE4320(Fall2024):Homework#4PleaseturninyourhomeworkbeforethedateandtimeindicatedinCourseworks.Pleaseshowandexplainyourworkclearlyandcompletelyinordertoearnfullcredit.Pleaseincludeallpartsofthehomeworkyouwantto......
  • 第1篇Scrum冲刺博客
    软件工程班级链接作业要求作业要求作业目标项目冲刺团队成员姓名学号王睿娴3222003968张颢严3222004426梁恬(组长)3222004467潘思言3222004423一、各个成员在Alpha阶段认领的任务二、明日各个成员的任务安排三、整个项目预期......