草庐IT

【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs（8）

戊子仲秋 2023-04-11 原文

目录

写在前面：

题目：1114. 棋盘问题 - AcWing题库

题目描述：

输入格式：

输出格式：

数据范围：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：1114. 棋盘问题 - AcWing题库

题目描述：

输入格式：

输入含有多组测试数据。

每组数据的第一行是两个正整数 n, k，用一个空格隔开，

表示了将在一个 n ∗ n 的矩阵内描述棋盘，以及摆放棋子的数目。

当为-1 -1时表示输入结束。

随后的 n 行描述了棋盘的形状：每行有 n 个字符，其中 # 表示棋盘区域，

 . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出格式：

对于每一组数据，给出一行输出，输出摆放的方案数目 C （数据保证 C < 231）。

数据范围：

n ≤ 8,k ≤ n 

输入样例：

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

输出样例：

2
1

解题思路：

我们使用深度优先搜索的时候，

第一个要注意的点是搜索的顺序，

因为我们要保证，

我们写出的递归结构能够遍历所有情况。

（以上递归搜索的基本思路，多熟悉总是好的）

 接下来是具体思路：

根据题意我们可以总结出两个问题：

1. 我们只能在‘#’位置下棋，不能在‘.’位置下棋；

2. 每行每列只允许下一个棋，那如何遍历棋盘的所有情况？

第一个问题我们加判断即可，

第二个问题，我们需要模拟一下：（以棋盘是3行3列为例）

画一个递归搜索树：

我们假设每一个横线是一行，每次递归搜索下一列：

根节点：

然后，第一行能放的位置有，1、2、3列，

我们据此往下递归搜索：

 放过的列在继续递归之后就不能放了：

 继续递归搜索：

我们发现这其实就是一个全排列，我们根据全排列的思想去做即可。

下面是代码实现： 

代码：

//包常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n, k;

const int N = 10;

//计数
int res;

char g[N][N];

//记录这一列有没有下棋
bool used[N];

void dfs(int u, int cnt)
{
    //下的棋数符合题目要求，方案++
    if(cnt == k)
    {
        res++;
        return;
    }
    
    //已经到行底了
    if(u == n) return;
    
    for(int i = 0; i < n; i++)
    {
        if(!used[i] && g[u][i] == '#')
        {
            used[i] = true;
            dfs(u + 1, cnt + 1);
            used[i] = false;//恢复现场
        }
    }
    //如果前面（下的棋数符合题目要求，方案++），就会返回，导致到不了下一行，这里让他强行往下走一行
    dfs(u + 1, cnt);
}

int main()
{
    //多组输入
    while(cin >> n >> k && n > 0 && k > 0)
    {
        for(int i = 0; i < n; i++)
        {
            cin >> g[i];
        }
        //每组输入重新计数
        res = 0;
        dfs(0, 0);
        printf("%d\n", res);
    }
    return 0;
}

AC ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。

蓝桥AcWingquotampgt

有关【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs（8）的更多相关文章

  1. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  2. 深度学习部署：Windows安装pycocotools报错解决方法 - 2

    深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal

  3. ruby - 如何搜索有用的 ruby - 2

    寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是ruby​​gems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和ruby​​gems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko

  4. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  5. ruby - Ruby 中的必应搜索 API - 2

    我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是

  6. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  7. ruby - 使用 Ransack 搜索枚举字段 - 2

    我有一个表，'jobs'和一个枚举字段'status'。status具有以下枚举集:enumstatus:[:draft,:active,:archived]使用ransack，我如何过滤表，比如说，所有事件记录？ 最佳答案 你可以像这样在模型中声明自己的掠夺者:ransacker:status,formatter:proc{|v|statuses[v]}do|parent|parent.table[:status]end然后您可以使用默认的搜索语法_eq来检查相等性，如下所示:Model.ransack(status_eq:'ac

  8. ruby-on-rails - Rails 4 postgres 全文搜索错误(范围) - 2

    我一直在使用postgres关注railscast的全文搜索，但我不断收到以下错误#的未定义局部变量或方法“作用域”我关注了railscast确切地。我安装了所有正确的gem。(pg_search，pg)。这是我的代码文章Controller(我在这里也使用acts_as_taggable)defindex@articles=Article.text_search(params[:query]).page(params[:page]).per_page(3)ifparams[:tag]@articles=Article.tagged_with(params[:tag])else@art

  9. ruby - 如何使用部分字符串搜索数组并返回索引？ - 2

    我想使用部分字符串搜索数组，然后获取找到该字符串的索引。例如:a=["Thisisline1","Wehaveline2here","andfinallyline3","potato"]a.index("potato")#thisreturns3a.index("Wehave")#thisreturnsnil使用a.grep将返回完整的字符串，使用a.any?将返回正确的true/false语句，但都不会返回匹配的索引找到了，或者至少我不知道该怎么做。我正在编写一段代码，该代码读取文件、查找特定header，然后返回该header的索引，以便它可以将其用作future搜索的偏移量。如果

  10. 深度学习12. CNN经典网络 VGG16 - 2

    深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG

随机推荐