知识点
- 回溯算法
题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1605
- 参考题解：https://www.luogu.com.cn/problem/solution/P1605
- 标签：
OI、搜索、回溯法
题解
- 大致就是dfs然后回溯法剪枝，主要叙述一下几个坑点。
- 如果有人像我一样喜欢用动态数组的话，一定要注意多给点空间，要不然dfs里面第一步判断容易越界，因为是后判断是否越界的
- cnt别忘了初始化！（说到底是我太大意了……神犇绕道）
- 一定是先判断有没有障碍，因为终点也可能是有障碍的，那cnt就是0，后判断会卡bug的
- 这个点走完往回走下一个分支时别忘了把状态恢复成没有走过的，要不然就卡bug了
- 题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/solution/P1605
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
void dfs(int x, int y, int fx, int fy, int &cnt, int n, int m, vector<vector<bool>> &b) {
if (b[x][y]) {
return;
}
if (x == fx && y == fy) {
cnt;
return;
}
if (x <= 0 || x > n || y <= 0 || y > m) {
return;
}
b[x][y] = true;
dfs(x 1, y, fx, fy, cnt, n, m, b);
dfs(x - 1, y, fx, fy, cnt, n, m, b);
dfs(x, y 1, fx, fy, cnt, n, m, b);
dfs(x, y - 1, fx, fy, cnt, n, m, b);
b[x][y] = false;
}
void best_coder() {
int sx, sy, fx, fy, cnt = 0, n, m, t;
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
vector<vector<bool>> b(n 5, vector<bool> (m 5));
for (int i = 0; i < t; i) {
int x, y;
cin >> x >> y;
b[x][y] = true;
}
dfs(sx, sy, fx, fy, cnt, n, m, b);
cout << cnt;
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 返回
return 0;
}
- 回溯经典模板
void search(int t)
{
if(满足输出条件)
{
输出解;
}
else
{
for(int i=1;i<=尝试方法数;i )
if(满足进一步搜索条件)
{
为进一步搜索所需要的状态打上标记;
search(t 1);
恢复到打标记前的状态;//也就是说的{回溯一步}
}
}
}
