递推与递归和DFS深度优先搜索
习题课
递推/ 递归 / DFS
P2089 烤鸡 指数
P1088 火星人 全排列
P1149 火柴棒等式 指数 + 预处理
P2036 PERKET 指数
P1135 奇怪的电梯 暴力
迷宫问题
一道很经典的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;
}
Flood Fill 洪水灌溉
DFS
acw1114.棋盘问题 排列
P1025 数的划分 组合
P1019 单词接龙 指数 + 预处理
标签:递归,int,cin,DFS,include,递推 From: https://www.cnblogs.com/harper886/p/17342090.html