即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

HDU 1016 DFS初步入门基础知识题

编程语言 a912952381 12℃ 0评论

             第一次写博客(其实是第二篇),请大佬们不要打我。以下内容纯手写,保证原创,如有部分雷同纯属巧合。

       其实我很犹豫很害怕,我一个初学者写代码博客,怕极了被网络大佬们“追杀”,犹豫多时,我决定以一个初学者的视角写下这篇东西,如果有什么网络规则啊,错误啊,不好的地方请各位大佬大方指出,我一定改大哭大哭大哭!

       深度优先搜索dfs就是一条路走到底,不通就回头继续下一个尝试,直到所有可能都被尝试完就结束。

       核心思想就是递归,回溯。

       代码框架就是终止条件,标记点,下一步dfs递归调用,返回。dfs多次出现return语句。

题目传送门(个人喜欢蓝色怪我咯)

              正文:我是初学者,希望用CSDN见证我的人生,写的不好,请各位大佬大胆指出,但请言语不要过激,谢谢。我爱ACM。

       这是一道DFS基础题,没什么难点,数据量也低,不容易超时,所以也不需要剪枝(我还没学剪枝大哭大哭 来自咸鱼的绝望)。

       下面这个代码我自我感觉良好啊,哇,写了很久,测试多次,以为能一次AC吧,呵呵!妄想。是菜就是菜,还敢妄想AC。至于错在哪呢?不妨先自己查查bug。

        代码WA+PE+TE,哈哈,错的有点尴尬。




#include 
#include 
#include 
using namespace std;

int n;                      //全局变量,因为dfs中会用到
int a[22];                  //一般dfs数组都定义为全局变量,初值为0
bool book[22];              //标记数组,初始值为false,但最好还是在main里进行清零操作(即memset函数)

bool fun(int t)             //判定素数函数
{
    for(int i=2; i> n;
    memset(book,false,sizeof(book));   //标记数组清零函数,有些oj好像不需要,但写上总没坏处吧
    book[1]=true;             //标记一号点为已走
    a[1]=1;                   //题目默认a[1]=1
    dfs(2);                   //从第二步开始dfs,理由同上
    return 0;
}

   

    上面得代码讲道理是没错得,错就错在HDU有严格得格式要求(人称“坑”)。所以说你完全可以不再看我下面得完整代码,自己修改上面得格式即可得到AC答案



    改用scanf和printf是因为我害怕超时,dfs的时间复杂度很容易超时,一般需要很强的剪枝语句(我还不会,我太菜了)!


#include 
#include 
#include 
#include 
using namespace std;

int n;                      //全局变量,因为dfs中会用到
int a[22];                  //一般dfs数组都定义为全局变量,初值为0
bool book[22];              //标记数组,初始值为false,但最好还是在main里进行清零操作(即memset函数)

bool fun(int t)             //判定素数函数
{
    for(int i=2; i

感谢围观本人的CSDN处女作!我会怀念的。



转载请注明:CodingBlog » HDU 1016 DFS初步入门基础知识题

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情