{"id":34184,"date":"2024-11-01T09:25:15","date_gmt":"2024-11-01T09:25:15","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34184"},"modified":"2024-11-01T10:58:16","modified_gmt":"2024-11-01T10:58:16","slug":"c-coding-test-course-exploring-mazes","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34184\/","title":{"rendered":"C++ Coding Test Course, Exploring Mazes"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

\n This is a problem of exploring a given maze to find a path to the exit. The maze is given as a 2D array,
\n 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).
\n The size of the maze is n x m<\/code>, and you need to implement an algorithm to explore the maze.\n <\/p>\n

Input Format<\/h2>\n

\n The first line contains the size of the maze n<\/code> and m<\/code>. (1 \u2264 n, m \u2264 100)
\n The next n<\/code> lines will provide the information of the maze consisting of 0s and 1s.\n <\/p>\n

Output Format<\/h2>\n

\n If it is possible to reach the exit, print the length of that path; if it is impossible, print -1<\/code>.\n <\/p>\n

Example Input<\/h2>\n
\n    5 5\n    0 1 0 0 0\n    0 1 0 1 0\n    0 0 0 1 0\n    1 1 0 1 0\n    0 0 0 0 0\n    <\/pre>\n
Example Output<\/h2>\n
\n    9\n    <\/pre>\n
Problem Solving Approach<\/h2>\n
\n        This problem can be explored using BFS (Breadth-First Search) or DFS (Depth-First Search).
\n        Since the first discovered path in BFS is the shortest path, it is recommended to use BFS for grid exploration.\n    <\/p>\n
\n        If using BFS, you can explore the nodes that can be moved to from the current position using a queue,
\n        check for visit status, and then add the new position to the queue.
\n        This method allows you to find the shortest path to the exit.\n    <\/p>\n
C++ Code Implementation<\/h2>\n
Below is the C++ code to solve the maze exploration problem.<\/p>\n
\n#include <iostream>\n#include <vector>\n#include <queue>\n#include <utility>\n\nusing namespace std;\n\n\/\/ Directions: Up, Down, Left, Right\nconst int dx[] = {-1, 1, 0, 0};\nconst int dy[] = {0, 0, -1, 1};\n\nint bfs(const vector>& maze, int n, int m) {\n    queue> q; \/\/ Queue declaration\n    q.push({0, 0}); \/\/ Starting position (0, 0)\n    \n    vector> distance(n, vector(m, -1)); \/\/ Distance array\n    distance[0][0] = 1; \/\/ Initialize the distance for the starting point to 1\n\n    while (!q.empty()) {\n        auto current = q.front(); q.pop();\n        int x = current.first;\n        int y = current.second;\n\n        \/\/ If the target point is reached\n        if (x == n - 1 && y == m - 1) {\n            return distance[x][y]; \/\/ Return the path length\n        }\n\n        \/\/ Explore adjacent nodes\n        for (int i = 0; i < 4; i++) {\n            int nx = x + dx[i];\n            int ny = y + dy[i];\n\n            \/\/ Check bounds and if movement is possible\n            if (nx >= 0 && nx < n && ny >= 0 && ny < m && \n                maze[nx][ny] == 0 && distance[nx][ny] == -1) {\n                q.push({nx, ny}); \/\/ Add to queue\n                distance[nx][ny] = distance[x][y] + 1; \/\/ Update the distance\n            }\n        }\n    }\n    return -1; \/\/ If unable to reach the exit\n}\n\nint main() {\n    int n, m;\n    cin >> n >> m; \/\/ Input the size of the maze\n    vector> maze(n, vector(m));\n    \n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < m; j++) {\n            cin >> maze[i][j]; \/\/ Input the maze\n        }\n    }\n\n    cout << bfs(maze, n, m) << endl; \/\/ Output the result\n    return 0;\n}\n    <\/int><\/vector<\/int><\/vector<\/pair<\/vector<\/code><\/pre>\n
Code Explanation<\/h2>\n
\n        The code uses a 2D vector to represent the maze and calculates the distance to the exit using BFS.
\n        The main components are:\n    <\/p>\n