2075 / Математика / Графи / Пошук шляху в лабіринті
Пошук оптимального шляху
C#
const int ROW = 4; const int COL = 5; // Stores the coordinates // of the matrix cell class Point { public int x, y; public Point(int x, int y) { this.x = x; this.y = y; } }; // Stores coordinates of // a cell and its distance class Node { public Point pt; public int dist; }; static bool isValid(int row, int col) { return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL); } static int[] dRow = { -1, 0, 0, 1 }; static int[] dCol = { 0, -1, 1, 0 }; static void pathMoves(bool[,] mat, Point src, Point dest) { // Stores the distance for each // cell from the source cell int[,] d = new int[ROW,COL]; for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { d[i, j] = -1; } } // Distance of source cell is 0 d[src.x,src.y] = 0; // Initialize a visited array bool[,] visited = new bool[ROW,COL]; for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { visited[i, j] = false; } } // Mark source cell as visited visited[src.x,src.y] = true; // Create a queue for BFS Queue<Node> q = new Queue<Node>(); // Distance of source cell is 0 Node s = new Node(); s.pt = src; s.dist = 0; // Enqueue source cell q.Enqueue(s); // Keeps track of whether // destination is reached or not bool ok = false; // Iterate until queue is not empty while (q.Any()) { // Deque front of the queue Node curr = q.Peek(); Point pt = curr.pt; // If the destination cell is // reached, then find the path if (pt.x == dest.x && pt.y == dest.y) { int xx = pt.x, yy = pt.y; int dist = curr.dist; // Assign the distance of // destination to the // distance matrix d[pt.x,pt.y] = dist; // Stores the smallest path string pathmoves = ""; // Iterate until source is reached while (xx != src.x || yy != src.y) { // Append D if (xx > 0 && d[xx - 1,yy] == dist - 1) { pathmoves += 'D'; xx--; } // Append U if (xx < ROW - 1 && d[xx + 1,yy] == dist - 1) { pathmoves += 'U'; xx++; } // Append R if (yy > 0 && d[xx,yy - 1] == dist - 1) { pathmoves += 'R'; yy--; } // Append L if (yy < COL - 1 && d[xx,yy + 1] == dist - 1) { pathmoves += 'L'; yy++; } dist--; } // Reverse the backtracked path char[] charArray = pathmoves.ToCharArray(); Array.Reverse(charArray); pathmoves = new string(charArray); Console.WriteLine(pathmoves); ok = true; break; } // Pop the start of queue q.Dequeue(); // Explore all adjacent directions for (int i = 0; i < 4; i++) { int row = pt.x + dRow[i]; int col = pt.y + dCol[i]; // If the current cell is valid // cell and can be traversed if (isValid(row, col) && (mat[row,col] == false) && !visited[row,col]) { // Mark the adjacent cells as visited visited[row,col] = true; // Enque the adjacent cells Node adjCell = new Node(); Point p = new Point(row, col); adjCell.pt = p; adjCell.dist = curr.dist + 1; q.Enqueue(adjCell); // Update the distance // of the adjacent cells d[row,col] = curr.dist + 1; } } } // If the destination // is not reachable if (!ok) Console.WriteLine(-1); } static void Main(string[] args) { bool[,] mat = { { false, false, false, true, false}, { false, true , false, true, false}, { false, true , false, true, false}, { false, true, false, false, false} }; Point src = new Point(3, 0); Point dest = new Point(3, 3); pathMoves(mat, src, dest); Console.ReadKey(); }
UUURRDDDR
C++
#include <iostream> #include <queue> using namespace std; #define ROW 4 #define COL 5 // Stores the coordinates // of the matrix cell struct Point { int x, y; }; // Stores coordinates of // a cell and its distance struct Node { Point pt; int dist; }; // Check if the given cell is valid or not bool isValid(int row, int col) { return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL); } // Stores the moves of the directions of adjacent cells int dRow[] = { -1, 0, 0, 1 }; int dCol[] = { 0, -1, 1, 0 }; // Function to find the shortest path from the // source to destination in the given matrix void pathMoves(char mat[][COL], Point src, Point dest) { // Stores the distance for each // cell from the source cell int d[ROW][COL]; memset(d, -1, sizeof d); // Distance of source cell is 0 d[src.x][src.y] = 0; // Initialize a visited array bool visited[ROW][COL]; memset(visited, false, sizeof visited); // Mark source cell as visited visited[src.x][src.y] = true; // Create a queue for BFS queue<Node> q; // Distance of source cell is 0 Node s = { src, 0 }; // Enqueue source cell q.push(s); // Keeps track of whether // destination is reached or not bool ok = false; // Iterate until queue is not empty while (!q.empty()) { // Deque front of the queue Node curr = q.front(); Point pt = curr.pt; // If the destination cell is // reached, then find the path if (pt.x == dest.x && pt.y == dest.y) { int xx = pt.x, yy = pt.y; int dist = curr.dist; // Assign the distance of // destination to the // distance matrix d[pt.x][pt.y] = dist; // Stores the smallest path string pathmoves = ""; // Iterate until source is reached while (xx != src.x || yy != src.y) { // Append D if (xx > 0 && d[xx - 1][yy] == dist - 1) { pathmoves += 'D'; xx--; } // Append U if (xx < ROW - 1 && d[xx + 1][yy] == dist - 1) { pathmoves += 'U'; xx++; } // Append R if (yy > 0 && d[xx][yy - 1] == dist - 1) { pathmoves += 'R'; yy--; } // Append L if (yy < COL - 1 && d[xx][yy + 1] == dist - 1) { pathmoves += 'L'; yy++; } dist--; } // Reverse the backtracked path reverse(pathmoves.begin(), pathmoves.end()); cout << pathmoves; ok = true; break; } // Pop the start of queue q.pop(); // Explore all adjacent directions for (int i = 0; i < 4; i++) { int row = pt.x + dRow[i]; int col = pt.y + dCol[i]; // If the current cell is valid // cell and can be traversed if (isValid(row, col) && (mat[row][col] == '1' || mat[row][col] == 's' || mat[row][col] == 'd') && !visited[row][col]) { // Mark the adjacent cells as visited visited[row][col] = true; // Enque the adjacent cells Node adjCell = { { row, col }, curr.dist + 1 }; q.push(adjCell); // Update the distance // of the adjacent cells d[row][col] = curr.dist + 1; } } } // If the destination // is not reachable if (!ok) cout << -1; } int main() { char mat[ROW][COL] = { { '1', '0', '0', '1', '1'}, { '1', '1', '1', '0', '1'}, { '0', '1', '0', '0', '1'}, { '1', '1', '1', '1', '1'} }; Point src = { 0, 0 }; Point dest = { 3, 0 }; pathMoves(mat, src, dest); return 0; }
DRDDL