A visual guide to 0–1 BFS
Novel problems require tailored solutions. Sometimes, taking a detour and a fresh look at the problem can significantly reduce its complexity. Today we’ll talk about one such technique called 0–1 Breadth First Search.
Welcome! To the brand new article of Code Stories where we solve interesting problems using the fundamentals of Computer Science. 🚀
Just like our last post regarding Dynamic Programming, we’ll first understand the problem statement. After that, we’ll start exploring solution approaches and gradually develop the intuition for 0–1 BFS. Following that, we will code the entire solution. 🎉
This article assumes that you have a basic understanding of graphs and how they are traversed.
The Problem ❓
Captain Dlon Husk has finally embarked on an adventure to discover new worlds beyond his own. He is using the latest SpaceY Shuttle for this adventure. 🚀
After a few wormhole jumps he enters into a Space-Time Matrix of NxM dimensions(1 ≤ N, M ≤ 2000). Since it’s a 2-D matrix his Shuttle too can just move in 4 directions Top, Bottom, Left and Right.
He finds out that this part of the universe is pretty strange, as certain cells of the Matrix have the influence of Dormammu, the destroyer of the worlds. Landing on one of these would mean instant death. Luckily he is currently on a Martian cell [R,C]. Dlon likes Martian cells as they give him faith.
But this is not all, he discovers that the space-time jumps have damaged the thrusters which move the Shuttle Left and Right. So now he can only move Left and Right X and Y times respectively (0 ≤ X, Y≤ 10⁹). Note that there are NO restrictions on the Up and Down movement.
Dlon is already missing his son (The one named after a coupon code) and wants to return home. But he needs faith for the journey back home. Your task is to help Dlon determine the number of Martian cells within his reach.
The Strategy 💡
Since this problem involves a lot of visualization, let’s look at the following illustration to understand it better.
So simply put, Starting from the cell situated at [R, C] (R is Row and C is Column) we want to find out how many Martian cells we can potentially reach while avoiding Dormammu cells. (Martians cells are denoted by . while the others with *for simplicity).
Remember, we can only move Left & Right, X & Y times.
I will urge you to pause here for 5 minutes and think of how you can approach this problem. This part is very crucial as it will prime your brain to be more receptive to the content ahead
I hope after thinking for a while, you must have realized the caveat here. If there would have been no restriction on the number of Left and Right moves, we could have made a simple graph traversal (DFS or BFS) to compute all the cells that we could reach.
But the fact that there are certain moves that are fundamentally more costly than others implores us to have a priority based traversal.
To put it differently, we understand that there is no point in using a Left or Right move to reach a cell if it could be reached without it. Since those moves are already limited, we may want to trade them with unlimited Up-Down moves, whenever we can.
Therefore from the source cell, we will like to first traverse to a cell that doesn’t require a Left-Right move. Only when we have exhausted all such cells, we can start exploring cells that require us to spend our limited Left-Right moves.
The following idea will become clearer as we model this priority based traversal on the lines of an interesting technique.
A special kind of BFS
Breadth First Search is a type of graph traversal where we visit nodes of a graph in increasing order of their distance from the source. Therefore, in an unweighted graph, the moment we reach a particular node the number of edges from the source to that node is also the shortest distance.
But this only works when all the edge weights are equal (the graph is unweighted). When we are given a weighted graph we can’t just sum up all the edge lengths to get the shortest path because unlike the previous case, we can in fact use more edges to reach the target node but still end up with a shorter distance. This idea is illustrated below.
Therefore we seek out Algorithms like Dijkstra, Bellman-Ford, etc for a weighted graph. However if the edge weights are more constrained, say either 0 or 1, we can apply an intelligent technique to solve the shortest path conundrum.
We can simply opt to segregate the edge weights encountered during the traversal into 2 buckets. Because we know that all the edge in this graph will be either 0 or 1 at each node, we are faced with just 2 kinds of edge weights.
So to segregate the edges, we can have a Doubly Ended Queue (Deque) to push the edges with 0 weight in the front and those with 1 weight to the back of the Deque.
Also, we will ensure that for the purpose of a BFS traversal we always pop the front element in the Deque.
This step is very crucial as it will always ensure that we pick nodes with distance K before touching nodes with distance K+1 in the Deque.
This leads to a very interesting Queue invariant for our BFS traversal. It is this invariant that makes 0–1 BFS so special.
At any instant, the Deque can only contain nodes having a total distance of K or (K+1)
Let me explain why this will always hold true. When you are on a node situated at distance K the choices of edge weights are only 0 & 1.Therefore any neighbours you add after traversing those edges can only increase the total distance to K+1 .
Hence, the nodes in the Deque are always sorted as per their distance from the source node. As long as we keep popping from the front while adding the edges with weight 0 to front & 1 to the back, our Deque Invariant will remain intact. This is the key idea behind 0–1 BFS as illustrated below.
Applying 0–1 BFS to the problem
Let’s now see how the above idea fits into the current problem.
As mentioned earlier we charted out with an intention to do a priority-based traversal. We further saw how 0–1 BFS always have a preference to lower edge weights ( 0 over 1). It is time to connect the dots now 😛
Our problem is very similar. Here, too we will prefer the cells which are reachable via an Up-Down move to the cells which require a Left-Right move.
Consequently adding the former in the front and the latter at the back.
Hence our matrix is equivalent to a graph where all the cells situated in the vertical direction of the current cell is exactly like nodes connected with 0 edge weight.
While cells in the horizontal direction to the current cell behaves like nodes with 1 edge weight.
You may ask why we need the shortest path algorithm here?
Since 0–1 BFS will reach every node in the graph via a minimum cost path, we too will be able to visit each cell in the matrix optimally.
So, if it is not possible to visit a cell via the shortest path for the given constraints, we can safely say, the cell is out of our reach.
Another way to look at it, if we plan to travel to a cell C with a longer path than the shortest path, we might waste our precious Left-Right moves and reduce our reach further. Let’s see this idea in action below.
We now have a solid understanding of our solution approach. It is time to get Captain Dlon Husk home 🌍
The Code 🎉
Input (1 based indexing)
4 5 // NxM
3 2 // R,C
1 2 // X,Y
.....
.***.
...**
*....Output
10 //Number of cells reachableCode in C++14
Congratulations! Captain, you are home 🏡
Want more content like this?
Let me know in the comments below.You can connect with me on Twitter here: abshekha
