|
You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.
The first input line has two integers n and m: the height and width of the map. Then there are lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.
Examples:
Input: n = 5, m = 8, labyrinth = {“########”, “#.A#…#”, “#.##.#B#”, “#……#”, “########” }
Output:
YES
9
LDDRRRRRU
Explanation: The shortest path has 9 moves: Left, Down, Down, Right, Right, Right, Right, Right, Up.
Input: n = 10, m = 10, labyrinth = {“##.A######”, “#.##.##.##”, “#####..###”, “.#########”, “.########.”, “###.###.##”, “#########.”, “######.#.#”, “###..###.#”, “###.B#####”}
Output: NO
Approach:
To find the path from the start to end in the labyrinth we can use a breadth-first search (BFS) algorithm. We start BFS from the starting point (‘A’) and explore all possible directions (left, right, up, down) until we reach the end point (‘B’). We keep track of the shortest path length and path itself during BFS traversal. Also, keep a track of the direction from which we have visited the current cell. For example: if we have visited the current cell by moving down from the cell above, then we store ‘D’ in steps[][].
Step-by-step algorithm:
- Read the dimensions of the grid and initialize the grid with the static input.
- Find the starting and ending positions in the grid.
- Implement a BFS (Breadth-First Search) algorithm to the find the shortest path from the starting point to the ending point.
- If the ending point is reachable reconstruct the path using a parent array to the store the direction of the movement at each cell.
- Output “YES” followed by the minimum number of the steps required to reach the ending point and sequence of movements to the reach there. If the ending point is not reachable output “NO”.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
vector<string> graph(1000);
vector<vector<char> > steps(1000, vector<char>(1000));
bool visited[1000][1000];
pair<ll, ll> start, dest;
stack<char> ans;
ll n, m;
// function to check whether the current cell is unvisited,
// unblocked and inside the grid
bool is_valid(ll x, ll y)
{
return (x >= 0 && x < n && y >= 0 && y < m
&& graph[x][y] != '#'
&& visited[x][y] == false);
}
// Function to backtrack and extract the path from B to A
void backtrack(ll x, ll y)
{
if (steps[x][y] != 'X') {
char ch = steps[x][y];
ans.push(ch);
// Move one cell up
if (ch == 'U')
backtrack(x + 1, y);
// Move one cell down
else if (ch == 'D')
backtrack(x - 1, y);
// Move one cell left
else if (ch == 'L')
backtrack(x, y + 1);
// Move one cell right
else if (ch == 'R')
backtrack(x, y - 1);
}
}
// function to run bfs and find the shortest path from A to
// B
bool bfs(ll x, ll y)
{
steps[x][y] = 'X';
bool flag = false;
// queue to run bfs across the grid
queue<pair<ll, ll> > q;
q.push({ x, y });
while (!q.empty()) {
pair<ll, ll> ele = q.front();
x = ele.first;
y = ele.second;
q.pop();
// If we have reached the destination
if (graph[x][y] == 'B') {
flag = true;
break;
}
visited[x][y] = true;
// Move Up
if (is_valid(x - 1, y)) {
visited[x - 1][y] = true;
steps[x - 1][y] = 'U';
q.push({ x - 1, y });
}
// Move Right
if (is_valid(x, y + 1)) {
visited[x][y + 1] = true;
steps[x][y + 1] = 'R';
q.push({ x, y + 1 });
}
// Move Down
if (is_valid(x + 1, y)) {
visited[x + 1][y] = true;
steps[x + 1][y] = 'D';
q.push({ x + 1, y });
}
// Move Left
if (is_valid(x, y - 1)) {
visited[x][y - 1] = true;
steps[x][y - 1] = 'L';
q.push({ x, y - 1 });
}
}
// If there is a path from A to B, print the path
if (flag) {
backtrack(x, y);
return true;
}
else
return false;
}
int main()
{
// Sample Input
n = 5, m = 8;
graph = { "########", "#.A#...#", "#.##.#B#",
"#......#", "########" };
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph[i][j] == 'A')
start = { i, j };
else if (graph[i][j] == 'B')
dest = { i, j };
}
}
// Check if there is a path from A to B
if (bfs(start.first, start.second)) {
cout << "YES" << endl << ans.size() << endl;
while (!ans.empty()) {
cout << ans.top();
ans.pop();
}
}
else
cout << "NO" << endl;
}
import java.util.*;
public class Main {
static char[][] graph;
static char[][] steps;
static boolean[][] visited;
static Stack<Character> ans;
static Pair<Integer, Integer> start, dest;
static int n, m;
// A Pair class to store coordinates
static class Pair<X, Y> {
X first;
Y second;
Pair(X first, Y second)
{
this.first = first;
this.second = second;
}
}
// Function to check whether the current cell is
// unvisited, unblocked and inside the grid
static boolean isValid(int x, int y)
{
return (x >= 0 && x < n && y >= 0 && y < m
&& graph[x][y] != '#' && !visited[x][y]);
}
// Function to backtrack and extract the path from B to
// A
static void backtrack(int x, int y)
{
if (steps[x][y] != 'X') {
char ch = steps[x][y];
ans.push(ch);
// Move one cell up
if (ch == 'U')
backtrack(x + 1, y);
// Move one cell down
else if (ch == 'D')
backtrack(x - 1, y);
// Move one cell left
else if (ch == 'L')
backtrack(x, y + 1);
// Move one cell right
else if (ch == 'R')
backtrack(x, y - 1);
}
}
// Function to run BFS and find the shortest path from A
// to B
static boolean bfs(int x, int y)
{
steps[x][y] = 'X';
boolean flag = false;
// Queue to run BFS across the grid
Queue<Pair<Integer, Integer> > q
= new LinkedList<>();
q.add(new Pair<>(x, y));
while (!q.isEmpty()) {
Pair<Integer, Integer> ele = q.poll();
x = ele.first;
y = ele.second;
// If we have reached the destination
if (graph[x][y] == 'B') {
flag = true;
break;
}
visited[x][y] = true;
// Move Up
if (isValid(x - 1, y)) {
visited[x - 1][y] = true;
steps[x - 1][y] = 'U';
q.add(new Pair<>(x - 1, y));
}
// Move Right
if (isValid(x, y + 1)) {
visited[x][y + 1] = true;
steps[x][y + 1] = 'R';
q.add(new Pair<>(x, y + 1));
}
// Move Down
if (isValid(x + 1, y)) {
visited[x + 1][y] = true;
steps[x + 1][y] = 'D';
q.add(new Pair<>(x + 1, y));
}
// Move Left
if (isValid(x, y - 1)) {
visited[x][y - 1] = true;
steps[x][y - 1] = 'L';
q.add(new Pair<>(x, y - 1));
}
}
// If there is a path from A to B, print the path
if (flag) {
backtrack(x, y);
return true;
}
else
return false;
}
public static void main(String[] args)
{
// Sample Input
n = 5;
m = 8;
graph = new char[][] { "########".toCharArray(),
"#.A#...#".toCharArray(),
"#.##.#B#".toCharArray(),
"#......#".toCharArray(),
"########".toCharArray() };
visited = new boolean[n][m];
steps = new char[n][m];
ans = new Stack<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph[i][j] == 'A')
start = new Pair<>(i, j);
else if (graph[i][j] == 'B')
dest = new Pair<>(i, j);
}
}
// Check if there is a path from A to B
if (bfs(start.first, start.second)) {
System.out.println("YES");
System.out.println(ans.size());
while (!ans.isEmpty()) {
System.out.print(ans.pop());
}
}
else
System.out.println("NO");
}
}
from collections import deque
def is_valid(x, y):
return (0 <= x < n and 0 <= y < m
and graph[x][y] != '#' and not visited[x][y])
# Function to backtrack and extract the path from the B to A
def backtrack(x, y):
if steps[x][y] != 'X':
ch = steps[x][y]
ans.append(ch)
# Move one cell up
if ch == 'U':
backtrack(x + 1, y)
# Move one cell down
elif ch == 'D':
backtrack(x - 1, y)
# Move one cell left
elif ch == 'L':
backtrack(x, y + 1)
elif ch == 'R':
backtrack(x, y - 1)
# Function to run BFS and find the shortest path from the A to B
def bfs(x, y):
steps[x][y] = 'X'
flag = False
# Queue to run BFS across the grid
q = deque([(x, y)])
while q:
x, y = q.popleft()
# If we have reached the destination
if graph[x][y] == 'B':
flag = True
break
visited[x][y] = True
# Move Up
if is_valid(x - 1, y):
visited[x - 1][y] = True
steps[x - 1][y] = 'U'
q.append((x - 1, y))
# Move Right
if is_valid(x, y + 1):
visited[x][y + 1] = True
steps[x][y + 1] = 'R'
q.append((x, y + 1))
# Move Down
if is_valid(x + 1, y):
visited[x + 1][y] = True
steps[x + 1][y] = 'D'
q.append((x + 1, y))
# Move Left
if is_valid(x, y - 1):
visited[x][y - 1] = True
steps[x][y - 1] = 'L'
q.append((x, y - 1))
# If there is a path from the A to B
# print the path
if flag:
backtrack(x, y)
return True
else:
return False
# Sample Input
n = 5
m = 8
graph = ["########",
"#.A#...#",
"#.##.#B#",
"#......#",
"########"]
visited = [[False] * m for _ in range(n)]
steps = [[''] * m for _ in range(n)]
ans = []
for i in range(n):
for j in range(m):
if graph[i][j] == 'A':
start = (i, j)
elif graph[i][j] == 'B':
dest = (i, j)
# Check if there is a path from A to B
if bfs(start[0], start[1]):
print("YES")
print(len(ans))
while ans:
print(ans.pop(), end="")
else:
print("NO")
let n = 5, m = 8;
// Dimensions of the grid
let graph = [
"########",
"#.A#...#",
"#.##.#B#",
"#......#",
"########"
]; // Input grid
let start, dest;
// Start and destination points
let steps = Array.from({ length: n }, () => Array(m).fill(''));
let visited = Array.from({ length: n }, () => Array(m).fill(false));
let ans = [];
// Function to check if the current cell is valid
const isValid = (x, y) => {
return x >= 0 && x < n && y >= 0 && y < m && graph[x][y] !== '#' && !visited[x][y];
};
// Function to backtrack and extract the path from the B to A
const backtrack = (x, y) => {
if (steps[x][y] !== 'X') {
let ch = steps[x][y];
ans.push(ch);
if (ch === 'U') backtrack(x + 1, y);
else if (ch === 'D') backtrack(x - 1, y);
else if (ch === 'L') backtrack(x, y + 1);
else if (ch === 'R') backtrack(x, y - 1);
}
};
// Function to run BFS and find the shortest path from the A to B
const bfs = (x, y) => {
steps[x][y] = 'X';
let flag = false;
let queue = [[x, y]];
while (queue.length) {
[x, y] = queue.shift();
if (graph[x][y] === 'B') {
flag = true;
// Destination reached
break;
}
visited[x][y] = true;
if (isValid(x - 1, y)) {
visited[x - 1][y] = true;
steps[x - 1][y] = 'U';
queue.push([x - 1, y]);
}
// Move Right
if (isValid(x, y + 1)) {
visited[x][y + 1] = true;
steps[x][y + 1] = 'R';
queue.push([x, y + 1]);
}
// Move Down
if (isValid(x + 1, y)) {
visited[x + 1][y] = true;
steps[x + 1][y] = 'D';
queue.push([x + 1, y]);
}
// Move Left
if (isValid(x, y - 1)) {
visited[x][y - 1] = true;
steps[x][y - 1] = 'L';
queue.push([x, y - 1]);
}
}
if (flag) {
backtrack(x, y);
// Backtrack to the extract the path
return true;
}
else return false;
};
// Find start and destination points
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (graph[i][j] === 'A') start = [i, j];
else if (graph[i][j] === 'B') dest = [i, j];
}
}
// Check if there is a path from the A to B
if (bfs(start[0], start[1])) {
console.log("YES");
console.log(ans.length);
console.log(ans.reverse().join(''));
// Reverse and join the path
} else {
console.log("NO");
}
Time Complexity: O(n*m)
Auxiliary Space: O(n*m)
|
