娱乐 每 日 算 法 挑 战 【第0x12期】

[随性而为]

感觉就是经典的递归问题……

struct maze

{

    char chara;

    int visited;//这个就废除了吧

}

struct maze[m][n];

(此处略去将maze的每个元素中chara的初始化和visited都为0的操作)

int check(int row,int col,struct maze[][],top)

{

     if(row==final_row&&col==final.col)

    {

         if(top<=s)

             printf("yes");

         else

             printf("no");//这里我觉得只要提前到了终点处就算没开也应该要等在那啊，不应该还在失了智的左右横跳等出口啊

    }

     if(row<=m-1&&col<=n-1&&maze[row][col].chara!='#'&&top<=s)

    {

          check(row,col+1,maze,top+1);

          check(row,col-1,maze,top+1);

          check(row+1,col,maze,top+1);

          check(row-1,col,maze,top+1);

    }

}

int main()

{

  int top=0,start_row(初始化),start_col(初始化);

   check(start_row,start_col,maze,top);

}

四月 30, 2020，由随性而为修改

[随性而为]

2 小时前, Mr.K 018 说道:

终点没开之前是墙，而且不允许停（那样就太没意思了（笑））

而且，这个DFS是没法找到最短路径的，会导致有些能yes的例输出no

怎么说呢，这个DFS虽然可能有点问题（繁琐），但是绝对可以找到最短路径，因为递归的本质就是把所有的可能都走一遍，这其中包括了最短路径，当然我上面的代码可能会输出很多的yes或者no（因为除了最短路径可能会有其他路径），这样的话我们可以声明一个flag=0，把原来输出yes的操作改为通过指针使flag++；当递归结束后判断flag的值，0为no，非0为yes

如果说硬要反复横跳的话，那就把判断的条件改一下呗，就像2楼说得还是比较方便的，判断s-top是否为奇偶。

四月 30, 2020，由随性而为修改