Solving Puzzle: Death first search ep1

https://www.codingame.com/ide/puzzle/death-first-search-episode-1

This game need to identify shortest path between 2 node.

Firstly, I build a 2D array to represent a map with link 2 nodes.

Next we need to find the shortest path between two nodes. Once we found the shortest path, we can identify which node we should block.

Pseudo code for shortest path

1. define queue for storing node between start and end
2. start from end node e. find all possible path n1 from e. Put the path to queue
3. get the first object from queue [n1, n0], find all possible path n2 from n1. Put the path [n2, n1 ... e] from queue
4. repeat until s node found

#BFS #Pathfinding