Mr.K 018 发布于四月 30, 2020 分享 发布于四月 30, 2020 (已修改) · 只看该作者 第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 四月 30, 2020，由Mr.K 018修改 注释 苍雨瞬 80.00节操 糖 1 链接到点评
yhz012 发布于四月 30, 2020 分享 发布于四月 30, 2020 (已修改) · 只看该作者 来了来了 首先基本图算法能跑个最短路径出来，拿A*配曼哈顿距离问题不大，暴力一点BFS也可以 假设最短路径是d，那很显然如果d>s，那就别挣扎了，等死吧 如果大于等于d，那么需要进一步讨论 显然，如果d-s为偶数，那么左右横跳等着开门就完了（除非只有1个空间只能自闭 如果d-s是奇数，那么等死吧（因为不存在奇数长度的环。另一个说法是如果要回到原位，一定要执行和L同样次数的R，和U同样次数的D） 四月 30, 2020，由yhz012修改 1 链接到点评
随性而为 发布于四月 30, 2020 分享 发布于四月 30, 2020 (已修改) · 只看该作者 感觉就是经典的递归问题…… 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，由随性而为修改 链接到点评
Mr.K 018 发布于四月 30, 2020 作者 分享 发布于四月 30, 2020 (已修改) · 只看该作者 1 小时前, 随性而为 说道: //这里我觉得只要提前到了终点处就算没开也应该要等在那啊，不应该还在失了智的左右横跳等出口啊 终点没开之前是墙，而且不允许停（那样就太没意思了（笑）） 而且，这个DFS是没法找到最短路径的，会导致有些能yes的例输出no 四月 30, 2020，由Mr.K 018修改 链接到点评
随性而为 发布于四月 30, 2020 分享 发布于四月 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，由随性而为修改 随性而为在文学领地阅读作品时遇到了穿着女仆装的文学少女，待她离开后找到了遗落的8节操 链接到点评
推荐贴