提供一种判断死循环的思路
查看原帖
提供一种判断死循环的思路
915382
frelow_poem楼主2023/1/2 17:49

rt,不难看出如果进入死循环,那么F和C都已经进入了各自的循环。我们记录每一个格子F和C是否经过和如果经过,方向是什么,再在F和C各自移动的每一步检测是否已经以同样的方向来过一次了。

如果F和C都进入了循环,在这一刻记录F和C各自的位置。然后再在每一步检测F和C是否又一次同时到达了相同的位置,如果是,则一定进入死循环。

想实现这个功能,有以下几点需要注意:

  • 首先要注意对进入循环的判断,如果你在F和C各自每一次行动的开始或结尾判断是不行的(因为转向的时候坐标不发生改变)

  • 其次如果你只在F和C行进的时候判断,也会出现问题(但是我不知道这道题的数据能否通过),是过不了下面这个数据的:

F*.C......
*.........
..........
..........
..........
..........
..........
..........
..........
..........

(因为F一直转向)


这个做法的好处:对于这一道题来说,时间上可以压到27ms以内,空间上理论可以小于700KB(我个人测试的每一次都有出入,最小的一次716KB;而且把代码里的int数组换成几个bool数组大概还能压一点)

当然了这题数据比较弱,追求这个好像没啥用

最后希望大家能在这道题里找到思考的快乐,文中如果错误欢迎指正。

2023/1/2 17:49
加载中...