学习笔记（算法）——路径之谜（蓝桥杯官网）（dfs,回溯)

学习+1

学习目标：

蓝桥杯省奖

学习内容：

每日一题
题目源于蓝桥杯官网

题目描述

解题思路

1.先定义最大行列值，输入行列值，行列靶数，答案数组，访问标记数组，辅助数组

2.定义dfs(深度优先搜索）函数

2.1记录当前位置
2.2如果到达右下角&&行列只剩一靶
2.2.1做循环：如果前面的靶子都打完，退出函数（检查）
2.2.2做循环：输出答案路径
2.3标记为true,行列靶数减一
2.4循环得到新位置，判断是否可以递归
2.5回溯

3.主函数

3.1输入矩阵大小，列，行
3.2调用dfs
3.3结束

代码

#include<iostream>
using namespace std;

const int N = 25;  //定义一个常量，表示最大值
int n, r[N], c[N], ans[N * N];  //定义输入的n行n列，行列靶数数组，答案数组
bool re[N][N];  //定义访问标记数组
int a[] = { -1,0,1,0 }, b[] = { 0,1,0,-1 };  //辅助数组（表示顺时针方向）

//深度优先搜索（dfs）函数
void dfs(int x, int y, int pos) {
    ans[pos] = x * n + y;  //记录当前位置
    //如果走到了最后一格且最后一格的北方和西方各只剩一靶
    if (x == n - 1 && y == n - 1 && r[n - 1] == 1 && c[n - 1] == 1) {
        //检查除最后的一行一列外其他靶数是否大于0，若等于0，执行下一步，若大于0，则结束函数，无解
        for (int i = 0; i < n - 1; i++) {
            if (r[i] > 0 || c[i] > 0) return;
        }
        //输出正确路径
        for (int i = 0; i <= pos; i++) {
            cout << ans[i] << " ";
        }
        return;
    }
    re[x][y] = true;
    r[x]--;
    c[y]--;
    //得到新位置并判断该位置是否可用
    for (int k = 0; k < 4; k++) {
        int t1 = x + a[k];
        int t2 = y + b[k];
        if (!re[t1][t2] && t1 >= 0 && t1 < n && t2 >= 0 && t2 < n && r[t1]>0 && c[t2]>0) {
            //调用递归
            dfs(t1, t2, pos + 1);
        }
    }
    //回溯
    ans[pos] = 0;
    re[x][y] = false;
    r[x]++;
    c[y]++;
}

int main() {
    cin >> n;
    //注意：先输入每一行的靶数，但他是按列排列的，所以先输入列
    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 0; i < n; i++) cin >> r[i];
    dfs(0, 0, 0);
    return 0;
}

总结

这道题主要运用的知识点有dfs和回溯，其中dfs一般用来解迷宫，本题的打箭靶算是这类题目的变形，本质还是和原来一样，只要熟练掌握知识点，就能灵活运用！加油呀，宝子们！！

学习时间：

周三

学习产出：

蓝桥杯的真题*1
dfs熟练度+1
回溯熟练度+1