一眼BFS,但是每走一步的cost变化有四种情况
- 不变(走到同色格子上)
- +1(走到异色格子上)
- +2(变无色格子为同色并走上去)
- +3(变无色格子为异色并走上去)
如果直接BFS,容易造成每格最小cost反复更新。能否保证第一次访问每格就能找到它的最小cost呢?也就是说,我们希望先访问完所有0 cost能到达的格子,再访问完所有1 cost能到达的格子,再访问完所有2 cost能到达的格子......
萌新的想法是:维护四个vector来保存搜到的格子:vector0,vector1,vector2,vector3。访问vector0时,将搜到的cost +i的格子放进vectori中。一旦vector0搜完则将它们进行调换(使vector1变成vector0,vector2变成vector1,......)这样,每个vector中都保存着cost一致的格子,且vector0的cost总最小。