方法:记忆化广度优先搜索( MBFSMBFSMBFS )
首先看到从一个点跑到另外一个点,第一反应就是搜索了。可以使用 DFSDFSDFS 或 BFSBFSBFS ,这里选用 BFSBFSBFS 。
BFSBFSBFS 需要使用队列保存待查找的格子,这里还要明确都需要保存哪些信息,坐标( xxx , yyy ) 、当前步数和当前格子颜色。
格子颜色是存在 mapmapmap 数组中的,为什么还有在队列中保存颜色呢?因为空白的格子是可以变色的。所以要将其颜色存进队列,而原色 需要保留作为验证。
本题的思维难点在于将哪些格子入队及如何入队问题,为了优化搜索,使用 valvalval 数组来记忆当前格子需要的步数。
从当前( xxx , yyy )出发四个方向( dxdxdx , dydydy )判断,待考查的格子是否越界,如不越界进入考查。一共分四种情况:
111 、( xxx , yyy ) 与( dxdxdx , dydydy ) 原来都是红或黄的。这样相同颜色步数 +0+0+0 ,不用颜色步数 +1+1+1 ;
222 、( xxx , yyy )原来是有红或黄 ( dxdxdx , dydydy )是白色的。这样需要施展一次魔法改变颜色,这里有一个贪心,改变的颜色和当前颜色相同;
333 、( xxx , yyy )原来是白色的 ( dxdxdx , dydydy )是红或黄的。因为入队格子肯定是曾经有颜色的,所以判断( xxx , yyy )被涂的 颜色和( dxdxdx , dydydy )的颜色增加步数即可;
222 、( xxx , yyy ) 与( dxdxdx , dydydy ) 原来都是白色的。因为魔法无法连续使用,所以,这种情况走不了;