Daily Series #3: Geeking out → The Labyrinth Problem

I will continue with this series for people who like this kind of content, drop "+1" in the chat and I will tag you the next time I post content.

Today, I was in the mood to go through some old CS problems I had solved a few years back.

The problem is described in cses.fi [ https://cses.fi/problemset/task/1193 ] and is as follows:

You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

𝗜𝗻𝗽𝘂𝘁𝘀: You are given n and m: the height and width of the map. Then there are n lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

𝗢𝘂𝘁𝗽𝘂𝘁: Revert with "YES" if a path is possible. Revert with "NO" if no path is possible. If "YES" also mention the path taken to reach B from A as L(left), R (right), U (up), and D (down).

How do you solve a problem like this?

Solution Approach: You traverse through the input and figure out where A and B lie within the input as (i,j) coordinates. Then, we do something called flood fill approach, where we start at A and then we update moves with BFS until we reach B. (L/D/R/U)

Now, what we need to check next is whether it violates some assumptions.

1. Check each adjacent cell and it is not supposed to be a wall(#)
2. Adjacent cell should not be out of bounds, for example cells on the boundary cannot go outside the labyrinth.
3. Lastly we need to track that we have not already visited that cell before.

If none of these cases are violated then we proceed to move in that direction. Then we apply BFS again and check for violation of these cases. All the while we maintain whether we visited that cell before and the path we have taken from A.

We stop when we reach B's location. Now what happens if we don't reach B? Since, we are applying BFS we will end up reaching all cells except B. We would have completed entire traversal of the labyrinth yet no B in sight.