Solving Advanced 4D BFS problem: 'Mario & Luigi' Explained

Make sure you have a solid understanding of the BFS algorithm before starting with this post by reading:

https://blog.garybricks.com/bfs-and-dfs-beginners-overview-in-c

The Mario & Luigi Problem

Imagine a parallel universe where our beloved characters, Mario and Luigi, find themselves in a challenging situation. They are trapped within an intricate maze filled with rocks and spaces ablaze with fire. Navigating through these hazards is no easy task - the brothers cannot move through the fire, and the rocks form impregnable barriers.

Luckily, this world has an interesting mechanism - buttons distributed randomly within the maze. When either of the brothers steps on one of these buttons, something miraculous happens: every fire within the maze is instantly extinguished. This only happens as long as the brother is on top of the button, the moment he moves out of the button, all fires reappear.

The brothers are aware that somewhere within this maze lies an elusive exit. They are desperate to find a path to this escape route but two pressing questions loom in their minds: "Is it even feasible for both of us to reach this exit together?" and "If so, what is the quickest time in which we can both safely reach the exit?"

Here's where you come in. Your mission is to assist Mario and Luigi in finding answers to these questions. Keep in mind the following rules of movement:

For each second that ticks by, only one brother can make a move. This means they must strategize and choose their steps wisely.
Mario and Luigi can only move to the four adjacent spaces (up, down, left, right) in the maze, provided that the spaces are free from fire or rocks.
Lastly, don't worry about them colliding - both brothers are able to occupy the same space within the maze.

This is a tale of brotherhood, strategy, and survival. Are you ready to guide Mario and Luigi toward their escape?

Inputs

The first line of input will consist of a single integer, N, representing the dimensions of the maze. The maze itself is represented by a character matrix of size N x N, with specific characters symbolizing different elements within the maze. Here's what each character represents:

'.' Empty space
'*' Fire
'L' Luigi
'M' Mario
'S' Exit point
'#' Rock (forming an impenetrable wall)

Examples:

For a clearer understanding, let's look at a few examples:

-------- EXAMPLE1 ---------
6
######
#S.B.#
#****#
#L.M.#
#B...#
######
output: 8
-------- EXAMPLE2 ---------
7
#######
#S.*LB#
#...**#
#....B#
#....*#
#...*M#
#######
output: 13
---------------------------

Constraints

The size of the maze, N, is bounded as follows: 5 ≤ N ≤ 50.

Output

Your code should generate a single-line output. Depending on the maze configuration and the feasibility of the problem, it can be one of two possible statements:

"Not possible for both Brothers to reach the exit" - This output should be returned when it is impossible for both Mario and Luigi to arrive at the exit given the current maze conditions.
"The minimum time for both brothers to reach the exit is: X" - This statement should be the output when there exists a path for both brothers to reach the exit. Here, 'X' should be replaced with an integer representing the minimum time required for both Mario and Luigi to reach the exit.

Problem-Solving as a Human

We'll begin our problem-solving journey by dissecting the relationship between the provided input and output examples.

In our first example, it's apparent that the exit is entirely encircled by fire. As a consequence, Luigi is compelled to rush to the closest button, thereby allowing Mario to activate the button adjacent to the exit. This course of action then provides Luigi with a clear path to the exit, which he can take before Mario. Two crucial insights were gleaned from this analysis:

If the exit is enveloped by fire, both characters can only reach the exit if a button is located within the fiery perimeter.
To determine the shortest possible path in this instance, we must evaluate both potential routes. This entails testing scenarios in which Mario reaches the first button prior to Luigi and vice versa.

Let's now turn our attention to the second example. Notably, a button exists within the fiery exit zone, suggesting that a viable solution may be at hand. However, Mario is entirely ensnared, immobilized by the fire. Thankfully, Luigi is free to move and can reach a button. Upon pressing this button, Luigi frees Mario, who can then head to the button within the exit zone. This subsequently paves the way for Luigi to arrive at the exit, followed closely by Mario.

Based on the insights drawn from these examples, I began formulating a general solution. My initial idea involved testing all possible moves for Mario. This would involve him attempting to reach all buttons and the exit. Then, for each of these scenarios, we would repeat the process for Luigi. This essentially amounts to exploring all possible routes and then identifying the most efficient one.

Solution Implementation

Retaining our initial thought:

"Explore all feasible movements for Mario and Luigi to identify the most efficient path."

My first instinct was to employ Breadth-First Search (BFS) independently for Mario, tracing all accessible buttons. For each of these options, Luigi should also execute a BFS to reach all buttons located within the fire zone surrounding the exit, as well as the exit itself. Following each of Luigi's paths, Mario should again perform a BFS towards the exit. We then repeat all these steps, this time initiating with Luigi. Quite a whirlwind of thoughts, right? 🤯😵

This solution, although exhaustive, appears immensely complex and potentially riddled with challenges during implementation. Primarily, it involves launching multiple BFS procedures, each accompanied by unique conditions.

The intricacy of this implementation mainly stems from the fact that we're dealing with Mario and Luigi separately. This prompts us to ask, "Could we conduct a single BFS that examines all potential routes, treating Mario and Luigi as a unified entity?"

And that, dear readers, is indeed the golden key to unlocking this problem.

BFS Implementation for Mario only

Assuming you're familiar with BFS and have taken a glance at my BFS beginners overview, implementing a solution for this problem would be fairly straightforward if it only concerned one character. The completed code for such a scenario might look like this:

// ( Scenario with Mario only )
#include<iostream>
#include<queue>
using namespace std;
int X[4] = {1,0,-1,0}; // helper directions for X (right, up, left, down)
int Y[4] = {0,1,0,-1}; // helper directions for Y (right, up, left, down)
int dist[60][60], n;
char MAP[60][60];

struct node{int x, y;}; // node represented by coordinates

bool valid(int x, int y){
    // checks if the coordinate is within the map, is not fire and not rock, and has not been visited
    return x >= 0 && x < n && y >= 0 && y < n && dist[x][y] == -1 && MAP[x][y] != '*' && MAP[x][y] != '#';
}

int main(){
    int mx, my, ex, ey; // mario {x, y} and exit {x, y}
    cin >> n;
    // --------- getting input --------- //
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            dist[i][j] = -1; // initializing the Dist for that node to not visited
            cin >> MAP[i][j];
            if(MAP[i][j] == 'S'){ex = i, ey = j;} // exit found
            if(MAP[i][j] == 'M'){mx = i, my = j;} // mario found
        }
    }
    queue<node> BFS;
    BFS.push({mx, my}); // starting BFS
    dist[mx][my] = 0; // starting node distance set to 0

    while (BFS.size()){
        node current_node = BFS.front();
        BFS.pop();
        // visiting all 4 adjacent coords
        for (int d = 0; d<4; d++){
            int newX = current_node.x + X[d];
            int newY = current_node.y + Y[d];
            if(valid(newX, newY)){
                BFS.push({newX, newY});
                dist[newX][newY] = dist[current_node.x][current_node.y] + 1;
            }
        }
    }
    if(dist[ex][ey] == -1)cout << "imposible to reach the exit";
    else cout << "the minimum time for reaching the exit: " << dist[ex][ey];
    return 0;
}

The code shown above should look very familiar, it's the very classic implementation for a BFS on an implicit Graph, shown in numerous examples in my: BFS beginners overview.

Node representation for both brothers

So how might we modify this single-character set up to accommodate two characters? Our initial question is: "What would a node comprising two characters look like?" Here's a possible idea:

// Before (Only one character)
struct node{int x, int y};

// After (Mario and Luigi)
struct character{int x, int y};
struct Node{
    character Mario;
    character Luigi;
};

This structure appears plausible. However, referring to the x and y coordinates of Mario and Luigi in the later parts of our code using currentNode.Mario.x and currentNode.Luigi.x might be a tad cumbersome. Let's streamline this with a simpler approach:

struct Node{int Mx, My, Lx, Ly};

In this structure, we're tracking Mario with the first pair of integers and Luigi with the second pair. This approach leads to more straightforward and cleaner code.

Adapting the Distance Matrix for Our New Node

To begin, let's accommodate the new node in the dist matrix which keeps track of the minimum distance to a node and also indicates if it hasn't been visited yet.

int dist[60][60] // before, mario only {x, y}

int dist[60][60][60][60] // after, both brothers {Mx, My, Lx, Ly}

this is a very simple change that often confuses many programmers at the beginning (me included) because you get used to seeing the distance the same way you see the map, which for this example is 2D. however, remember that in reality dist is made specifically for whatever the node is, and must be adjusted. on a side note, you are not obligated to use a matrix like I'm doing here, you can also use an unordered map for example, and give an "id" to the nodes. However, this matrix approach simplifies matters for this case. It's important to note that this solution is feasible because N is at most 50. The required space for this matrix is 60^4, which is suitable for this problem but may pose issues for larger constraints.

Earlier, we initialized the 'dist' matrix at the same time as taking our input, but given the change, don't forget to initialize the matrix separately like so:

void initDist(){
    for(int i=0; i<60; i++){
        for(int j=0; j<60; j++){
            for(int k=0; k<60; k++){
                for(int l=0; l<60; l++)dist[i][j][k][l] = -1;
            }
        }
    }
}

Adjusting BFS for Our New Node

Before we revise the actual BFS, let's update the input-receiving part to consider Luigi:

int mx, my, lx, ly, ex, ey; // mario {x, y}, Luigi {x, y}, and exit {x, y}
cin >> n;
// --------- getting input --------- //
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        cin >> MAP[i][j];
        if(MAP[i][j] == 'S'){ex = i, ey = j;} // exit found
        if(MAP[i][j] == 'M'){mx = i, my = j;} // Mario found
        if(MAP[i][j] == 'L'){lx = i, ly = j;} // Luigi found
    }
}

Next, we can rectify the initial part of the BFS algorithm that involves adding the starting node to the queue and setting its distance to 0:

initDist();
queue<node> BFS;
BFS.push({mx, my, lx, ly}); // starting BFS
dist[mx][my][lx][ly] = 0; // starting node distance set to 0

Let's then refine the part of the algorithm that handles visiting all nodes adjacent to the current one:

// Before:
node current_node = BFS.front();
BFS.pop();
// visiting all 4 adjacent coords
for (int d = 0; d<4; d++){
    int newX = current_node.x + X[d];
    int newY = current_node.y + Y[d];
    if(valid(newX, newY)){
        BFS.push({newX, newY});
        dist[newX][newY] = dist[current_node.x][current_node.y] + 1;
    }
}

// After
node current_node = BFS.front();
BFS.pop();
// visiting all 4 adjacent coordinates for Mario only
for (int d = 0; d<4; d++){
    int newMX = current_node.Mx + X[d];
    int newMY = current_node.My + Y[d];
    int newLX = current_node.Lx;
    int newLY = current_node.Ly;
    if(valid(newMX, newMY, newLX, newLY)){
        BFS.push({newMX, newMY, newLX, newLY});
        dist[newMX][newMY][newLX][newLY] = dist[current_node.Mx][current_node.My][current_node.Lx][current_node.Ly] + 1;
    }
}
// visiting all 4 adjacent coordinates for Luigi only
for (int d = 0; d<4; d++){
    int newMX = current_node.Mx;
    int newMY = current_node.My;
    int newLX = current_node.Lx + X[d];
    int newLY = current_node.Ly + Y[d];
    if(valid(newMX, newMY, newLX, newLY)){
        BFS.push({newMX, newMY, newLX, newLY});
        dist[newMX][newMY][newLX][newLY] = dist[current_node.Mx][current_node.My][current_node.Lx][current_node.Ly] + 1;
    }
}

Where we once checked the 4 adjacent coordinates to the current one and pushed the BFS if it was valid, now however, we must do that independently for Mario but considering that Luigi is part of the node, and his "new" position, is the same, and once the 4 possible changes for Mario have been made, we repeat the process but for Luigi.

Adjusting Valid() for Our New Node and Buttons

We're nearly done! The last adjustment we need is to modify the 'valid' function to consider coordinates for both brothers. This entails checking that both coordinates are within the map and legal. Given the exact coordinates for both Mario and Luigi, we can easily add the condition for the scenario in which one of them is standing on a button, thereby allowing passage through fire. Here is my implementation:

bool valid(int Mx, int My, int Lx, int Ly){
    // checks if both coordinates are within the map and the node has not been visited.
    if(Mx >= 0 && My >= 0 && Mx < n && My < n && dist[Mx][My][Lx][Ly] == -1){
        if(MAP[Mx][My] == '#' || MAP[Lx][Ly] == '#')return false; // Rock Wall always illegal for either one
        if(MAP[Mx][My] == '*' && MAP[Lx][Ly] == 'B')return true; // If Mario on fire and Luigi on button
        if(MAP[Lx][Ly] == '*' && MAP[Mx][My] == 'B')return true; // if Luigi on fire and Mario on button
        // if the code didn't enter the previous conditions, it means that no buttons are pressed
        if(MAP[Mx][My] == '*' || MAP[Lx][Ly] == '*')return false; // fire illegal
        // else it means that this node is valid :D
        return true;
    }
    return false;
}

Accessing the Solution

To retrieve the actual answer, we must access the desired final node. For a single character, this would be implemented as follows:

if(dist[ex][ey] == -1)cout << "imposible to reach the exit";
else cout << "the minimum time for reaching the exit: " << dist[ex][ey];

However, we now need to revise this to work with the new 4D node distance matrix. This can be perplexing, given that we only have a single exit represented with two numbers: ex, ey, and we require 4 values for accessing the 4D matrix. But don't panic, the solution is quite straightforward:

if(dist[ex][ey][ex][ey] == -1)cout << "imposible to reach the exit";
else cout << "the minimum time for reaching the exit: " << dist[ex][ey][ex][ey];

Remember, the first pair of values represents Mario's position, and the second pair signifies Luigi's location. We are interested in the distance for the node where both characters reach the same exit.

Time and space Complexity

Let's examine the time and space complexity for this algorithm:

Time Complexity: The main factor affecting time complexity in this algorithm is the breadth-first search (BFS) which in the worst case, visits all nodes in the graph. As the graph in this case is essentially a 4-dimensional grid of size 60 (considering both Mario and Luigi's x, y positions), the time complexity can be considered as O(N^4) where N is the size of the graph (here, N = 60). This is because BFS in the worst case explores all possible combinations of Mario and Luigi's positions.
Space Complexity: The space complexity is largely driven by the 4-dimensional distance matrix of size 60, 'dist'. As each element of the matrix can be occupied, the space complexity is O(N^4), the same as the time complexity. This is because we need to store the distance for each possible combination of positions for Mario and Luigi.

It's important to note that this solution takes advantage of the fact that N is small (60), as both the time and space complexity are polynomial, making the algorithm impractical for larger inputs.

Optimizing Solution

The first time I submitted this implemented solution, I got a 90% TLE verdict, which forced me to think of a way of optimizing this solution, This compelled me to consider optimizing the solution. Initially, my focus was on streamlining the code while maintaining the underlying logic. Unfortunately, this approach didn't yield the desired improvement. Then I stumbled upon a realization. Consider two nodes, one with coordinates {Mx = 5, My = 5, Lx = 1, Ly = 4} and the other with {Mx = 1, My = 4, Lx = 5, Ly = 5}. Interestingly, the minimum distance from either of these nodes to the exit would be identical. Refer to the image below for a clearer understanding.

This observation led me to understand that these nodes are effectively identical for our purpose, yet the current code treats them as separate entities. If the code has marked the first node as visited, upon encountering the second node, it erroneously treats it as unvisited. To fix this, we can simply add one additional check to our valid function like so:

if(Mx >= 0 && My >= 0 && Mx < n && My < n && dist[Mx][My][Lx][Ly] == -1 && dist[Lx][Ly][Mx][My] == -1)

The remedy for this issue is a simple augmentation to our 'valid' function, adding an extra check for the node where Mario and Luigi have swapped positions. By making this minor adjustment, we effectively halve the number of possibilities, significantly improving the solution's efficiency.

Full Code

#include<iostream>
#include<queue>
using namespace std;
int X[4] = {1,0,-1,0}; // helper directions for X (right, up, left, down)
int Y[4] = {0,1,0,-1}; // helper directions for Y (right, up, left, down)
int dist[60][60][60][60], n;
char MAP[60][60];

struct node{int Mx, My, Lx, Ly;}; // node represented by coordinates

bool valid(int Mx, int My, int Lx, int Ly){
    // checks if both coordinates are within the map and the node has not been visited.
    if(Mx >= 0 && My >= 0 && Mx < n && My < n && dist[Mx][My][Lx][Ly] == -1 && dist[Lx][Ly][Mx][My] == -1){
        if(MAP[Mx][My] == '#' || MAP[Lx][Ly] == '#')return false; // Rock Wall always illegal for either one
        if(MAP[Mx][My] == '*' && MAP[Lx][Ly] == 'B')return true; // If Mario on fire and Luigi on button
        if(MAP[Lx][Ly] == '*' && MAP[Mx][My] == 'B')return true; // if Luigi on fire and Mario on button
        // if the code didn't enter the previous conditions, it means that no buttons are pressed
        if(MAP[Mx][My] == '*' || MAP[Lx][Ly] == '*')return false; // fire illegal
        // else it means that you are ok :D
        return true;
    }
    return false;
}

void initDist(){ // Initialized the Dist matrix to -1
    for(int i=0; i<60; i++){
        for(int j=0; j<60; j++){
            for(int k=0; k<60; k++){
                for(int l=0; l<60; l++)dist[i][j][k][l] = -1;
            }
        }
    }
}

int main(){
    int mx, my, lx, ly, ex, ey; // mario {x, y}, Luigi {x, y}, and exit {x, y}
    cin >> n;
    // --------- getting input --------- //
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> MAP[i][j];
            if(MAP[i][j] == 'S'){ex = i, ey = j;} // exit found
            if(MAP[i][j] == 'M'){mx = i, my = j;} // Mario found
            if(MAP[i][j] == 'L'){lx = i, ly = j;} // Lario found
        }
    }
    initDist();
    queue<node> BFS;
    BFS.push({mx, my, lx, ly}); // starting BFS
    dist[mx][my][lx][ly] = 0; // starting node distance set to 0

    while (BFS.size()){
        node current_node = BFS.front();
        BFS.pop();
        // visiting all 4 adjacent coordinates for Mario only
        for (int d = 0; d<4; d++){
            int newMX = current_node.Mx + X[d];
            int newMY = current_node.My + Y[d];
            int newLX = current_node.Lx;
            int newLY = current_node.Ly;
            if(valid(newMX, newMY, newLX, newLY)){
                BFS.push({newMX, newMY, newLX, newLY});
                dist[newMX][newMY][newLX][newLY] = dist[current_node.Mx][current_node.My][current_node.Lx][current_node.Ly] + 1;
            }
        }
        // visiting all 4 adjacent coordinates for Luigi only
        for (int d = 0; d<4; d++){
            int newMX = current_node.Mx;
            int newMY = current_node.My;
            int newLX = current_node.Lx + X[d];
            int newLY = current_node.Ly + Y[d];
            if(valid(newMX, newMY, newLX, newLY)){
                BFS.push({newMX, newMY, newLX, newLY});
                dist[newMX][newMY][newLX][newLY] = dist[current_node.Mx][current_node.My][current_node.Lx][current_node.Ly] + 1;
            }
        }
    }
    if(dist[ex][ey][ex][ey] == -1)cout << "imposible to reach the exit";
    else cout << "the minimum time for reaching the exit: " << dist[ex][ey][ex][ey];
    return 0;
}

Conclusion - Farewell

In wrapping up, we've navigated through the intricate details of a 4D Breadth-First Search algorithm for a captivating problem. We've traveled from understanding the problem, implementing the solution, encountering setbacks, and eventually triumphing by innovating an optimized solution.

Before I sign off, I would like to remind you that the process of learning and improving is an iterative one. If your first solution doesn't work or isn't efficient enough, don't be disheartened. Every attempt, every setback, and every small victory serves as a stepping stone toward becoming a better problem solver.

I trust this walkthrough has offered you valuable insights and has further sharpened your skills in tackling complex algorithmic problems. I hope to see you take these lessons forward into your next challenge.

Stay tuned for more competitive programming problem breakdowns and insights. Happy coding!

Decoding the 'Mario and Luigi' Challenge: An In-depth Guide to Applying BFS (Breadth-First Search)

Comments

More from this blog

Tarjan Algorithm Beginner Overview

The Greedy Guide: Essential Problems and Solutions for Competitive Programming

Optimal Play: A Dynamic Programming Approach to an Array-based Turn Game"

2D Prefix Array And 2D Segment Tree Overview

Unveiling Dynamic Programming Solutions for 'Roads' and 'Organizing Tiles' Problems.

The Mario & Luigi Problem

Inputs

Examples:

Constraints

Output

Problem-Solving as a Human

Solution Implementation

BFS Implementation for Mario only

Node representation for both brothers

Adapting the Distance Matrix for Our New Node

Adjusting BFS for Our New Node

Adjusting Valid() for Our New Node and Buttons

Accessing the Solution

Time and space Complexity

Optimizing Solution

Full Code

Conclusion - Farewell

Command Palette

Comments

More from this blog

The Mario & Luigi Problem

Inputs

Examples:

Constraints

Output

Problem-Solving as a Human

Solution Implementation

BFS Implementation for Mario only

Node representation for both brothers

Adapting the Distance Matrix for Our New Node

Adjusting BFS for Our New Node

Adjusting Valid() for Our New Node and Buttons

Accessing the Solution

Time and space Complexity

Optimizing Solution

Full Code

Conclusion - Farewell