Labyrinth

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.

Example:

Input: n = 5, m = 8, board = {{"########", "#.A#...#", "#.##.#B#", "#......#", "########"}};

Output:

YES
9
LDDRRRRRU

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
int vis[1001][1001];
int dist[1001][1001];
int n, m;
char grid[1001][1001];
int dx[] = {-1, 0, 1, 0};
vector<int> parent[1001][1001];
int dy[] = {0, 1, 0, -1};
bool isValid(int x, int y)
{
    if (x < 1 || x > n || y < 1 || y > m)
        return false;
    if (vis[x][y] == 1 || grid[x][y] == '#')
        return false;
    return true;
}
void bfs(int x, int y)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    vis[x][y] = 1;
    dist[x][y] = 0;
    parent[x][y] = {-1, -1};
    while (!q.empty())
    {
        int currx = q.front().first;
        int curry = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int newx = currx + dx[i];
            int newy = curry + dy[i];
            if (isValid(newx, newy))
            {
                vis[newx][newy] = 1;
                dist[newx][newy] = dist[currx][curry] + 1;
                parent[newx][newy] = {currx, curry};
                q.push({newx, newy});
            }
        }
    }
}
int main()
{
    n = 5, m = 8;

    vector<string> board = {{"########",
                             "#.A#...#",
                             "#.##.#B#",
                             "#......#",
                             "########"}};
    int srcx = 1, srcy = 1, destx = 1, desty = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            grid[i][j] = board[i - 1][j - 1];
            if (grid[i][j] == 'A')
            {
                srcx = i;
                srcy = j;
            }
            else if (grid[i][j] == 'B')
            {
                destx = i;
                desty = j;
            }
        }
    }
    bfs(srcx, srcy);
    if (vis[destx][desty] == 0)
        cout << "NO\n";
    else
    {
        string ans = "";
        cout << "YES\n";
        int p = parent[destx][desty][0];
        int q = parent[destx][desty][1];

        cout << dist[destx][desty] << "\n";
        while (true)
        {
            if (p == -1 && q == -1)
                break;
            else
            {
                if (p == destx && q == desty + 1)
                {
                    ans += 'L';
                    desty += 1;
                    p = parent[destx][desty][0];
                    q = parent[destx][desty][1];
                }
                else if (p == destx && q == desty - 1)
                {
                    ans += 'R';
                    desty -= 1;
                    p = parent[destx][desty][0];
                    q = parent[destx][desty][1];
                }
                else if (p == destx - 1 && q == desty)
                {
                    ans += 'D';
                    destx -= 1;
                    p = parent[destx][desty][0];
                    q = parent[destx][desty][1];
                }
                else
                {
                    ans += 'U';
                    destx += 1;
                    p = parent[destx][desty][0];
                    q = parent[destx][desty][1];
                }
            }
        }
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    }
    return 0;
}