|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> #include <vector> #include <queue> using namespace std; const int ROW = 5; const int COL = 5; // Function to check if a cell is within bounds and not yet visited bool isValid(int row, int col, vector<vector<int>>& maze, vector<vector<bool>>& visited) { return (row >= 0 && row < ROW && col >= 0 && col < COL && maze[row][col] == 0 && !visited[row][col]); } // Function to print the solution path void printPath(const vector<vector<int>>& path) { for (const auto& row : path) { for (int cell : row) { cout << (cell ? '*' : ' ') << ' '; } cout << endl; } } // Function to solve the maze using BFS bool solveMaze(vector<vector<int>>& maze) { // Directions for moving in the maze (right, down, left, up) vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; vector<vector<bool>> visited(ROW, vector<bool>(COL, false)); vector<vector<int>> path(ROW, vector<int>(COL, 0)); queue<pair<int, int>> q; q.push({0, 0}); visited[0][0] = true; path[0][0] = 1; while (!q.empty()) { auto [currentRow, currentCol] = q.front(); q.pop(); if (currentRow == ROW - 1 && currentCol == COL - 1) { printPath(path); return true; } for (const auto& dir : directions) { int newRow = currentRow + dir.first; int newCol = currentCol + dir.second; if (isValid(newRow, newCol, maze, visited)) { q.push({newRow, newCol}); visited[newRow][newCol] = true; path[newRow][newCol] = 1; } } } return false; } int main() { // Define a maze where 0 represents a free cell and 1 represents a blocked cell vector<vector<int>> maze = { {0, 1, 0, 0, 0}, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0 }; cout << "Maze Path:" << endl; if (!solveMaze(maze)) { cout << "No path found!" << endl; } return 0; } |
Explanation
- Maze Representation:
0represents a free cell.1represents a blocked cell.
isValidFunction:- Checks if a cell is within maze bounds, not blocked, and not yet visited.
printPathFunction:- Prints the solution path where
1represents the path and0represents non-path cells.
- Prints the solution path where
solveMazeFunction:- Uses Breadth-First Search (BFS) to find the shortest path from the top-left corner to the bottom-right corner.
- Initializes a queue with the starting point
(0, 0), marks it as visited, and adds it to the path. - Expands nodes by exploring all possible directions (right, down, left, up).
- Adds valid and unvisited cells to the queue and marks them as visited.
- If the bottom-right corner is reached, prints the path and returns
true. - If no path is found after exploring all possibilities, returns
false.
mainFunction:- Defines a maze with blocked and free cells.
- Calls
solveMazeto find and print the path from start to finish.