SGU 235 The Queen (bfs,卡时间过的我会乱说?)

一个n*n的棋盘,棋盘上有黑棋和白棋,白棋的queen可以攻击黑棋并且将其杀死(这个位置的黑棋消失),问queen准确走m步能走到几个点!

当点u离queen的距离在m的范围内并且u点离queen的距离是和m同奇偶性那么u点能够被queen在m步准确到达,因此问题就变成求以queen为源点的最短路径,但是有一种情况,就是碰到黑棋要吃掉它,因为要不要吃掉黑棋是一个决策,下次再碰到黑棋不知道是否吃过了,但是考虑到实际只要计算距离的奇偶性,因此,当碰到黑棋的时候就往后走一步,在往前走,这样将步数奇偶性改变!所以B点只会被走一次。

 

LEAVE A COMMENT