离谱思路BFS,TLE掉一个点 求dalao帮调QAQ(给出hack也行)
查看原帖
离谱思路BFS,TLE掉一个点 求dalao帮调QAQ(给出hack也行)
421805
fzy1026楼主2022/7/24 20:22

不是常规思路,轻喷qwq

浅说一下思路:倒着BFS,在地图中找到四面都上不去的点作为起点,往上进行BFS,途中记录每个格子的步数最大值,最后全局遍历找出最大值

mp[][]为地图,dp[][]为步数最大值

我在其中加了两个个优化:

1.(line 50)

if(dp[i][j])
{
	continue;
}

不以扫过的地方作为起点(好像没啥用)

2.(line 81)

if(Step > dp[X][Y])
{

防止里面的一个格子被重复搜,如果这个格子本身已经找到了最优解,就不用更新他以及与它相连的格子了

最后结果是AC 9个 TLE 1个

我觉得这个思路可以,但又不知道这个玩意还能不能提个速

求dalao帮帮忙吧,谢谢了

2022/7/24 20:22
加载中...