转跳到内容

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


推荐贴

第18期来啦!

第18期 汉化组的吃人陷阱1

MrK-019有一次不小心暴露了自己会中日英三语和视频剪辑的事实,现在某个汉化组已经布下了天罗地网,只要时机一到就要把他收入囊中,调教成无情的汉化机器!

已知汉化组布下的天罗地网是一种格子迷宫,只有一个出口。迷宫大概是这样的:

######
#K...#  
####.#  
#S...#  
######

如图所示,图上标为#的地方都是墙,标.的地方都是可以走的部分。MrK-019初始所在的地方也是可以走的部分。MrK-019一秒可以走一格。出口只在某一秒开放,平时都是不能走的墙;如果MrK-019在出口开放的那一秒到达出口,他就能逃脱汉化组的吃人陷阱,否则就会被抓住吃掉(指调教成无情的汉化机器)。同时,由于汉化组的人就在后面穷追不舍,MrK-019必须不停地移动才行!

MrK-019能不能从汉化组的吃人陷阱里逃出来呢?

输入

第一行是三个整数m,n,s,分别表示迷宫的长和宽,以及出口在第几秒开放。

接下来是一个m*n的字符矩阵,表示汉化组设下的迷宫。格式见题干和输入样例。

输出

如果MrK-019能逃出来,就输出一行Yes,否则输出一行No

样例输入1

5 6 8
######
#K...#  
####.#  
#S...#  
######

样例输出1

Yes

样例输入2

5 6 9
######
#K...#  
####.#  
#S...#  
######

样例输出2

No

,由Mr.K 018修改
注释
苍雨瞬 苍雨瞬 80.00节操
链接到点评

来了来了

 

首先基本图算法能跑个最短路径出来,拿A*配曼哈顿距离问题不大,暴力一点BFS也可以

 

假设最短路径是d,那很显然如果d>s,那就别挣扎了,等死吧

 

如果大于等于d,那么需要进一步讨论

显然,如果d-s为偶数,那么左右横跳等着开门就完了(除非只有1个空间只能自闭

如果d-s是奇数,那么等死吧(因为不存在奇数长度的环。另一个说法是如果要回到原位,一定要执行和L同样次数的R,和U同样次数的D)

,由yhz012修改
链接到点评

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

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);

}

,由随性而为修改
链接到点评
1 小时前, 随性而为 说道:

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

终点没开之前是墙,而且不允许停(那样就太没意思了(笑))

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

,由Mr.K 018修改
链接到点评
2 小时前, Mr.K 018 说道:

终点没开之前是墙,而且不允许停(那样就太没意思了(笑))

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

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

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

,由随性而为修改

随性而为在文学领地阅读作品时遇到了穿着女仆装的文学少女,待她离开后找到了遗落的8节操

链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款