
Since every edge has cost 1 (if it points to a harmful square) or 0 (if it points to a normal square), you can use the regular BFS algorithm with a deque: Push a vertex to the front of the deque in case of distance 0, and a vertex to the back of the deque in case of distance 1. That way, the distance order invariant of the BFS is preserved in the deque, and everything works. 