【第55题】回溯算法三连发（一）：迷宫，卡bug卡的我有点懵懵的。

知识点

• 回溯算法

题目

题目原文请移步下面的链接

• 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;
}

• 回溯经典模板

代码语言：javascript复制

void search(int t)
{
    if(满足输出条件)
    {
        输出解;
    }
    else
    {
        for(int i=1;i<=尝试方法数;i  )
            if(满足进一步搜索条件)
            {
                为进一步搜索所需要的状态打上标记;
                search(t 1);
                恢复到打标记前的状态;//也就是说的{回溯一步}
            }
    }
}

bug int 搜索 算法 效率

0 人点赞