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

习题课

递推/ 递归 / 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和男家丁的游戏