列公子

用户名：lielielie

访问量：10577

签　名：

等　　级
排　　名	1695
经　　验	2703
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯 3000米排名预测 - DFS/全排列
浏览：260

蓝桥杯发现环 DFS+并查集
浏览：483

蓝桥杯路径之谜 DFS
浏览：132

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

蓝桥杯路径之谜 DFS

　　作者: 列公子　　　　发表时间：2020-03-15 12:27:13 浏览：132　|　评论：0　

原题链接：蓝桥杯2016年第七届真题-路径之谜

# 路径之谜 DFS
## 完整代码 (AC)
```cpp
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 25;
int unums[maxn];        // 上边的数字
int lnums[maxn];        // 左边的数字
int upper[maxn];        // 上边的数字, 临时值
int left[maxn];         // 左边的数字, 临时值
int N;
vector<int> path;   // 路径

int xx[4] = {-1, 1, 0, 0};
int yy[4] = {0, 0, -1, 1};

bool vis[maxn][maxn];

void dfs(int x, int y){
    unums[y] ++;
    lnums[x] ++;
    vis[x][y] = true;
    path.push_back(x * N + y);

// 到达终点
    if (x == N-1 && y == N-1){
        bool flag = true;
        for (int i = 0; i < N; i++) {
            if (upper[i] != unums[i] || left[i] != lnums[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i = 0; i < path.size(); i++)
                printf("%d ", path[i]);
        }
    }

for (int i = 0; i < 4; i++){
        int cx = x + xx[i];
        int cy = y + yy[i];
        // 坐标合法, 剪枝
        if (cx > -1 && cy > -1 && cx < N && cy < N && !vis[cx][cy] && unums[cy] + 1 <= upper[cy] && lnums[cx] + 1 <= left[cx])
            dfs(cx, cy);
    }
    unums[y] --;        // 回溯
    lnums[x] --;
    vis[x][y] = false;
    path.pop_back();
}

int main(){
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &upper[i]);
    for (int i = 0; i < N; i++)
        scanf("%d", &left[i]);
    dfs(0, 0);
    return 0;
}

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C二级辅导-等差数列（C语言代码）

蓝桥杯路径之谜 DFS

评论区

精彩推荐

Tom数（C++代码）

数列排序（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

WU-输入输出格式练习（C++代码）

幸运数（C++代码）

格式化数据输出（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）

C语言训练-字符串正反连接（C语言代码）

明明的随机数（C语言代码）

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C二级辅导-等差数列 （C语言代码）

蓝桥杯 路径之谜 DFS

评论区

精彩推荐

Tom数 （C++代码）

数列排序 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

WU-输入输出格式练习 （C++代码）

幸运数 （C++代码）

格式化数据输出 （C语言代码）

青年歌手大奖赛_评委会打分 （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

明明的随机数 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C二级辅导-等差数列（C语言代码）

蓝桥杯路径之谜 DFS

　　评论区

Tom数（C++代码）

数列排序（C语言代码）

WU-输入输出格式练习（C++代码）

幸运数（C++代码）

格式化数据输出（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）

C语言训练-字符串正反连接（C语言代码）

明明的随机数（C语言代码）