C++ Coding Test Course, Exploring Mazes

Problem Description

This is a problem of exploring a given maze to find a path to the exit. The maze is given as a 2D array,
where 0 represents a walkable path, and 1 represents a wall. The starting point is (0, 0) and the exit is (n-1, m-1).
The size of the maze is n x m, and you need to implement an algorithm to explore the maze.

Input Format

The first line contains the size of the maze n and m. (1 ≤ n, m ≤ 100)
The next n lines will provide the information of the maze consisting of 0s and 1s.

Output Format

If it is possible to reach the exit, print the length of that path; if it is impossible, print -1.

Example Input

Example Output

Problem Solving Approach

This problem can be explored using BFS (Breadth-First Search) or DFS (Depth-First Search).
Since the first discovered path in BFS is the shortest path, it is recommended to use BFS for grid exploration.

If using BFS, you can explore the nodes that can be moved to from the current position using a queue,
check for visit status, and then add the new position to the queue.
This method allows you to find the shortest path to the exit.

C++ Code Implementation

Below is the C++ code to solve the maze exploration problem.


#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

// Directions: Up, Down, Left, Right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int bfs(const vector>& maze, int n, int m) {
    queue> q; // Queue declaration
    q.push({0, 0}); // Starting position (0, 0)
    
    vector> distance(n, vector(m, -1)); // Distance array
    distance[0][0] = 1; // Initialize the distance for the starting point to 1

    while (!q.empty()) {
        auto current = q.front(); q.pop();
        int x = current.first;
        int y = current.second;

        // If the target point is reached
        if (x == n - 1 && y == m - 1) {
            return distance[x][y]; // Return the path length
        }

        // Explore adjacent nodes
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // Check bounds and if movement is possible
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                maze[nx][ny] == 0 && distance[nx][ny] == -1) {
                q.push({nx, ny}); // Add to queue
                distance[nx][ny] = distance[x][y] + 1; // Update the distance
            }
        }
    }
    return -1; // If unable to reach the exit
}

int main() {
    int n, m;
    cin >> n >> m; // Input the size of the maze
    vector> maze(n, vector(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j]; // Input the maze
        }
    }

    cout << bfs(maze, n, m) << endl; // Output the result
    return 0;
}

Code Explanation

The code uses a 2D vector to represent the maze and calculates the distance to the exit using BFS.
The main components are:

Queue: Used to store the currently exploring nodes to determine the next moving node.
Distance Array: Records the distance to each node to avoid revisiting already visited nodes.
Direction Arrays: The dx and dy arrays are set to enable movement in the Up, Down, Left, Right directions.

When the program runs, it performs BFS starting from the starting point, exploring all adjacent nodes.
When reaching the exit, it returns the length to that point; if it cannot be reached, it returns -1.

Time Complexity

The time complexity is O(n * m) because each node is visited once.
The space complexity is also O(n * m) due to the use of the distance array and queue.

Conclusion

In this lesson, we implemented the BFS algorithm to solve the maze exploration problem using C++.
I hope this helps you understand the basic concept of the algorithm and aids in writing actual code through practice.
Therefore, I recommend gaining experience by tackling various forms of maze exploration problems.

Creating various test cases to further improve your code is also a good learning method.