首页 > 其他分享 >递推与递归和DFS深度优先搜索

递推与递归和DFS深度优先搜索

时间:2023-04-21 22:45:12浏览次数:47  
标签:递归 int cin DFS include 递推

递推与递归和DFS深度优先搜索

跳台阶

递归实现指数级枚举

递归实现排列型枚举

递归实现组合型枚举

P1036 选数

习题课

递推/ 递归 / DFS

P2089 烤鸡 指数

P1088 火星人 全排列

P1149 火柴棒等式 指数 + 预处理

P2036 PERKET 指数

P1135 奇怪的电梯 暴力

迷宫问题

P1683 入门

P1605 迷宫

一道很经典的DFS迷宫问题

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
int sx, sy, fx, fy;
const int N = 9;
int n, m;
char mp[N][N];//地图
int dx[6] = {1, -1, 0, 0};
int dy[6] = {0, 0, 1, -1};
bool st[N][N];//状态数组
;
int ans = 0;
void dfs(int x, int y) {
	if (x == fx && y == fy) {//到达终点
		ans++;//路径加1
		return;
	}
	for (int i = 0; i < 4; i++) {
//		cout<<x+dx[i]<<' '<<y+dy[i]<<'\n';

		if ((x + dx[i] >= 1 && x + dx[i] <= n && y + dy[i] >= 1 && y + dy[i] <= m) && mp[x + dx[i]][y + dy[i]] == '.') {//判断有没有出地图范围以及当前地图的点能不能走
			if (st[x + dx[i]][y + dy[i]] == false) {//当前没有被访问过
				st[x + dx[i]][y + dy[i]] = true;//标记为访问
				dfs(x + dx[i], y + dy[i]);//继续深搜
				st[x + dx[i]][y + dy[i]] = false;//恢复现场
			}
		}
	}


}
signed main () {
	memset(mp, '.', sizeof(mp));//'.'代表可以通过
	cin >> n >> m;
	int t;
	cin >> t;
	cin >> sx >> sy >> fx >> fy;
	while (t--) {
		int x, y;
		cin >> x >> y;
		mp[x][y] = '#';//'#'代表是障碍
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<mp[i][j];
//		}
//		cout<<'\n';
//
//
//	}
	st[sx][sy] = true;//起点标记为已经搜索过
	dfs(sx, sy);//开始搜索
	cout << ans << '\n';//打印结果

	return 0;
}

P1443 马的遍历

P1747 好奇怪的游戏

P2298 Mzc和男家丁的游戏

Flood Fill 洪水灌溉

P1596 Lake Counting S

P1451 求细胞数量

DFS

acw1114.棋盘问题 排列

P1025 数的划分 组合

P1019 单词接龙 指数 + 预处理

标签:递归,int,cin,DFS,include,递推
From: https://www.cnblogs.com/harper886/p/17342090.html

相关文章

  • 使用递归完成RBAC
     先使用ling查询将每个角色下的权限进行查询其次调用并返回这个GetFor方法,第一个参数是当前角色下的权限,第二个是权限的父ID顶级为0,GetFor方法是查询当前list集合用Printid作为条件,然后返回类型是一对多的样式所以创建dto进行赋值,然后那个集合需要反复调用这个方法来查询这......
  • js递归查询id所对应的节点,查询该节点的父节点,查询该节点的所有子节点
    在工作项目中经常遇到树形结构的数据,而往往我们需要用递归来实现,下面就给大家列举常用的递归操作。   lettreeList=[{id:'1',name:'父一',children:[{id:'1-1',......
  • 牛顿迭代法求方程根(递归算法)
    #include<iostream>#include<cmath>usingnamespacestd;doublef_origianal(doublea,doubleb,doublec,doubled,doublenewx){ returna*pow(newx,3)+pow(newx,2)*b+c*newx+d;}doublef_after_or(doublea,doubleb,doublec,doubled,......
  • bfs与dfs详解(经典例题 + 模板c-代码)
    文章目录模板+解析dfsbfs1562.微博转发3502.不同路径数165.小猫爬山模板+解析DFS(深度优先搜索)和BFS(广度优先搜索)是图论中两个重要的算法。dfs其中DFS是一种用于遍历或搜索树或图的算法,BFS则是一种用于搜索或遍历树或图的算法。两种算法都有其自身的优点和缺点,应用于不同的场景中......
  • docker安装FastDFS教程
    以下是在Docker中安装FastDFS集群的详细教程,适用于生产环境:下载FastDFS镜像文件:dockerpullseason/fastdfs创建一个网络用于容器之间的通讯:dockernetworkcreatefastdfs启动tracker容器:dockerrun-d--nametracker--netfastdfs--restartalwaysseason/fastdfstracke......
  • 图结构练习——BFSDFS——判断可达性
    图结构练习——BFSDFS——判断可达性TimeLimit:1000MSMemorylimit:65536K题目描述 输入第一行包含两个整数n,m(分别代表n个隘口,这些隘口之间有m个通道)。下面m行每行包含两个整数a,b;表示从a出发有一条通道到达b隘口(注意:通道是单向的)。输出......
  • LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前3题非常简单,但第4题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大夜......
  • 兔子产子问题(递归算法)
    #include<iostream>usingnamespacestd;intf(intn){ if(n==1||n==2) return1; returnf(n-1)+f(n-2);}intmain(){ inti; for(i=0;i<30;i++) { if((i+1)%5==0) cout<<endl; cout<<f(i+1); cout<<&q......
  • DFS
    DFSTimeLimit:5000/2000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):6254    AcceptedSubmission(s):3850ProblemDescriptionADFS(digitalfactorialsum)numberisfoundbysummingthefactorialofevery......
  • FastDFS服务搭建
    以下是搭建FastDFS集群服务的详细文档教程:准备工作在准备开始前,需要准备好以下环境和软件:CentOS764位系统FastDFSv5.11FastDHTv5.11Nginxlibfastcommonv1.0.43安装libfastcommon下载并解压libfastcommon源码包,执行以下命令编译和安装:wgethttps://github.com/hap......