首页 > 其他分享 >P1605 迷宫

P1605 迷宫

时间:2023-11-18 14:45:35浏览次数:37  
标签:le int 迷宫 sx 坐标 100 P1605

题目描述

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

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

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

输入格式

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

第二行为四个正整数 \(SX,SY,FX,FY\),\(SX,SY\) 代表起点坐标,\(FX,FY\) 代表终点坐标。

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

输出格式

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

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

1

提示

对于 \(100\%\) 的数据,\(1 \le N,M \le 5\),\(1 \le T \le 10\),\(1 \le SX,FX \le n\),\(1 \le SY,FY \le m\)。

DFS的裸题 搜到一种符合的答案ans++即可,注意的需要回溯!!!

using namespace std;
int sx,sy,ex,ey,n,m,q;
int ans=0;
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
int vis[100][100];
int mp[100][100];
void dfs(int x,int y){
	if(x==ex&&y==ey){
		ans++;
		return;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!mp[nx][ny]&&vis[nx][ny]==0){
			vis[nx][ny]=1;
			dfs(nx,ny);
			vis[nx][ny]=0;
		}
	}
	return;
}
int main(){
	cin>>n>>m>>q>>sx>>sy>>ex>>ey;
	vis[sx][sy]=1;
	for(int i=1;i<=q;i++){
		int xx,yy;
		cin>>xx>>yy;
	    mp[xx][yy]=1;
	}
	dfs(sx,sy);
	cout<<ans;
	return 0;
} 

标签:le,int,迷宫,sx,坐标,100,P1605
From: https://www.cnblogs.com/yufan1102/p/17840466.html

相关文章

  • T399752 The Maze of the Imperial Sister(御姐的迷宫)题解
    LinkT399752TheMazeoftheImperialSister(御姐的迷宫)Question判断图内是否有环Solution先判断连通性,所有点是不是在一个块内,然后用树的性质,点数\(=\)边数\(+1\)判断Code#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+5,maxe=maxn*2;structI......
  • 迷宫逃脱
    链接:迷宫逃脱【算法赛】-蓝桥云课(lanqiao.cn)题意 可以考虑记忆化搜索本人代码只能通过75%样例,写的很乱,一眼丁真鉴定为依托答辩,代码贴最后了,先附上ac代码#include<bits/stdc++.h>usingnamespacestd;usingull=unsignedlonglong;usingll=longlong;usin......
  • 1112.迷宫
    dfs模板#include<iostream>#include<cstring>usingnamespacestd;constintN=105;charg[N][N];intk,n;boolvis[N][N];intsx,sy,ex,ey;intdx[]={-1,1,0,0};intdy[]={0,0,-1,1};voiddfs(intx,inty){vis[x][y]=1;......
  • 逃离迷宫
    你好,欢迎使用由do_it_tomorrow开发的小游戏,这个游戏仅限于课下娱乐,造成任何损失作者概不负责。如果对于游戏有任何问题或者建议,欢迎进行反馈。在游戏中,玩家将在迷宫中尝试逃离,但是会有各种的怪物伺机而动,只有三思而后行才能在考验重重的迷宫中成功逃生。本游戏支持存档,并且具有......
  • 【算法】万圣节前夕的迷宫挑战
    这一天阳光和煦,小悦将捣蛋的侄子小明送回家后,紧绷的神经终于得以放松。在过去的一周里,小悦以无比的耐心和细心照顾着小明,同时也不忘在编程的道路上引领他迈出第一步。万圣节前夕的一天,书房中的陈设在阳光下显得庄重而温暖,小悦正专心致志地处理着手头的工作。突然,一封邮件如不速之......
  • [SWPUCTF 2021 新生赛]老鼠走迷宫(详细版
    附件下载https://wwvc.lanzouj.com/iYLez1br84jg解题思路用pyinstxtrator解析exe重点:将无后缀的5先修改后缀为pyc,然后随便找一个pyc文件补齐5.pyc的前16位十六进制数值(这道题以struct.pyc为例)将.pyc反编译为.py找到maze,从而找到最短路径改后缀下载附件,拿到一个无后缀的......
  • 逆波兰表达式与迷宫算法
    中项表达式是人类的算术思路,逆波兰表达式是机器结合栈结构完成算式解析的最佳结构。文章链接:https://zhuanlan.zhihu.com/p/357982040迷宫算法文章链接:https://blog.csdn.net/m0_53157173/article/details/114486303......
  • 题解 hdu 1269 迷宫城堡
    找点图论练习题写,发现hdu又寄了,那就发到blog里吧。思路:tarjan缩点判断DAG中点数是否为1。若是,则该图为强连通图。 //producedbymiya555//stupidmistakes:多测记得清空//ideas:tarjan模板#include<bits/stdc++.h>usingnamespacestd;constintN=10010;intn,m,low[......
  • 算法题 逃离迷宫
     题目描述:你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在......
  • 我的心理之旅:探索_MMPI_测验的迷宫
    引言人的心灵是一个奇妙而复杂的迷宫。有时候,我们甚至对自己也是个谜。这就是为什么心理学家们发明了各种工具来揭示我们的内心世界。明尼苏达多相人格调查表(MMPI)就是其中之一。在我最近的一次人格探索中,我决定深入了解MMPI,看看它能否为我揭示一些未知的真相。第一次邂逅MMPI......