AC后翻了下题解,好像没有和本蒟蒻方法一样的
查看原帖
AC后翻了下题解,好像没有和本蒟蒻方法一样的
774217
Archmushroom楼主2022/9/10 01:29

一眼BFS,但是每走一步的cost变化有四种情况

  • 不变(走到同色格子上)
  • +1(走到异色格子上)
  • +2(变无色格子为同色并走上去)
  • +3(变无色格子为异色并走上去)

如果直接BFS,容易造成每格最小cost反复更新。能否保证第一次访问每格就能找到它的最小cost呢?也就是说,我们希望先访问完所有0 cost能到达的格子,再访问完所有1 cost能到达的格子,再访问完所有2 cost能到达的格子......

萌新的想法是:维护四个vector来保存搜到的格子:vector0vector_0vector1vector_1vector2vector_2vector3vector_3。访问vector0vector_0时,将搜到的cost +i的格子放进vectorivector_i中。一旦vector0vector_0搜完则将它们进行调换(使vector1vector_1变成vector0vector_0vector2vector_2变成vector1vector_1,......)这样,每个vector中都保存着cost一致的格子,且vector0vector_0的cost总最小。

2022/9/10 01:29
加载中...