列公子

用户名：lielielie

访问量：10578

签　名：

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

　　自我简介：

TA的其他文章

蓝桥杯算法提高-学霸的迷宫 BFS- (C++)
浏览：635

蓝桥杯算法提高VIP-8皇后·改 DFS (C++)
浏览：215

蓝桥杯基础练习- 2n皇后问题 DFS (C++代码)
浏览：273

你可能喜欢

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

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

蓝桥杯棋盘多项式 DFS (C++)

　　作者: 列公子　　　　发表时间：2020-02-23 13:43:40 浏览：604　|　评论：1　

原题链接：蓝桥杯算法提高VIP-棋盘多项式

# [蓝桥杯] [算法提高] 棋盘多项式  DFS

## 1. 思路

类似八皇后问题，但由于洞的存在，不能像八皇后那样**逐行**递归搜索，而是**逐行并逐列**地递归搜索。

## 2. 算法

1. 逐行、逐列地递归 DFS，由 ```dfs(int row, int col, int cnt)``` 实现，
注意：在棋盘上放置一个车，则当前棋子总数对应的方案数加一，求出所有方案数只需一次 DFS

2. ```bool check(int row, int col)``` 检查一个坐标能否放置车，由于搜索自上而下、自左向右，```check``` 函数只向上、向左检查。
	- 遇到洞，则跳出这个方向的检查
	- 遇到别的车，则不能在此处放置

## 3. 数据结构

- ```bool vis[maxn][maxn]``` 记录当前位置是否已搜索过
- ```int solutions[maxn * maxn]``` 中 ```solutions[i]``` 的值为 在棋盘上放置 ```i```个车有 ```solutions[i]``` 种方案

## 4. 完成代码 (AC)
```cpp
//
// 蓝桥杯题库 算法提高 1540 棋盘多项式
// DFS
#include <cstdio>
using namespace std;
const int maxn = 10;
int N;
bool board[maxn][maxn];     // false 为洞
bool vis[maxn][maxn];  // 该位置是否放置了
int solutions[100];    // solution[1] 为只放一个车有多少方法

bool check(int row, int col){
    if (row > N || col > N || row < 1 || col < 1)
        return false;
    // 向上查看, 不需要向下和向右, 因为搜索的顺序是自上而下, 自左而右
    for (int rr = row - 1; rr > 0; rr--){
        if (!board[rr][col])    // 遇到洞
            break;
        if (vis[rr][col]){
            return false;
        }
    }
    // 向左查看
    for (int cc = col - 1; cc > 0; cc--){
        if (!board[row][cc])
            break;
        if (vis[row][cc])
            return false;
    }
    return true;
}

void dfs(int row, int col, int cnt){     // 坐标, 已经放了多少个车, 返回最多放了多少个车
    if (cnt <= N * N)
        solutions[cnt]++;

for (int rr = row; rr <= N; rr++){
        int cc;     // 不加入这一部分则时间超限
        if (rr == row)  // 仍在当前行
            cc = col;
        else    // 不在当前行则从第一列开始
            cc = 1;

for (; cc <= N; cc++){
            if (vis[rr][cc] || !board[rr][cc])
                continue;

if (check(rr, cc)){
                vis[rr][cc] = true;
                dfs(rr, cc, cnt+1);
                vis[rr][cc] = false;
            }
        }
    }
}

int main(){
    scanf("%d", &N);
    for (int i = 1; i < N+1; i++) {
        for (int j = 1; j < N + 1; j++) {
            scanf("%d", &board[i][j]);
        }
    }
    dfs(1, 1, 0);
    for (int i = 1; i <= N * N; i++)
        if (solutions[i])
            printf("%d\n", solutions[i]);

return 0;
}
```

0.0分

11 人评分

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

　　评论区

ceiyaeks

我想问一下这个dfs函数为什么没有return呀

2022-03-19 17:07:33

列公子

TA的其他文章

你可能喜欢

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

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

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

不容易系列（C语言代码）

【蟠桃记】（C++代码）（递归计算）

蓝桥杯棋盘多项式 DFS (C++)

评论区

精彩推荐

C语言训练-斐波纳契数列（C语言代码）

C语言训练-自守数问题（C语言代码） long long

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

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

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

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

水仙花（C语言代码）

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

printf基础练习2 （C语言代码）

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

列公子

TA的其他文章

你可能喜欢

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

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

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

不容易系列 （C语言代码）

【蟠桃记】 （C++代码）（递归计算）

蓝桥杯 棋盘多项式 DFS (C++)

评论区

精彩推荐

C语言训练-斐波纳契数列 （C语言代码）

C语言训练-自守数问题 （C语言代码） long long

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

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

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

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

水仙花 （C语言代码）

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

printf基础练习2 （C语言代码）

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

不容易系列（C语言代码）

【蟠桃记】（C++代码）（递归计算）

蓝桥杯棋盘多项式 DFS (C++)

　　评论区

C语言训练-斐波纳契数列（C语言代码）

C语言训练-自守数问题（C语言代码） long long

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

水仙花（C语言代码）