Monsters

You and some monsters are in a labyrinth. When taking a step in some direction in the labyrinth, each monster may simultaneously take one as well. Your goal is to reach one of the boundary squares without ever sharing a square with a monster.

Your task is to find out if your goal is possible, and if it is, print a path that you can follow. Your plan has to work in any situation; even if the monsters know your path beforehand.

Example:

Input: n = 5, m = 8, grid = {"########", "#M..A..#", "#.#.M#.#", "#M#..#...", "#.######"}

Output:

YES
5
RRDDR

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

//all four directions
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};

//direction up,down,right,left
char dir[] = {'U', 'D', 'R', 'L'};
int dp[1005][1005];

bool isValid(vector<string> &grid, int n, int m, int x, int y)
{
    if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != '.')
        return false;
    return true;
}
void monsters(int n, int m, vector<string> &grid)
{

    queue<pair<int, int>> q;
    int x, y;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (grid[i][j] == 'M')
                q.push({i, j});
            else if (grid[i][j] == 'A')
            {
                x = i;
                y = j;
            }
        }
    }
    q.push({x, y});
    dp[x][y] = -1;
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        x = p.first;
        y = p.second;
        q.pop();
        if (grid[x][y] == 'A' && (x == 0 || x == n - 1 ||
             y == 0 || y == m - 1))
        {
            cout << "YES\n";
            string ans;
            int d = dp[x][y];
            while (d != -1)
            {
                ans += dir[d];
                x -= dx[d];
                y -= dy[d];
                d = dp[x][y];
            }
            reverse(ans.begin(), ans.end());
            cout << ans.size() << "\n";
            cout << ans;
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            int newX = x + dx[i];
            int newY = y + dy[i];
            if (!isValid(grid, n, m, newX, newY))
                continue;
            else
            {
                grid[newX][newY] = grid[x][y];
                if (grid[newX][newY] == 'A')
                    dp[newX][newY] = i;
                q.push({newX, newY});
            }
        }
    }
    cout << "NO\n";
}
int main()
{
    int n = 5, m = 8;

    vector<string> grid = {"########",
                           "#M..A..#",
                           "#.#.M#.#",
                           "#M#..#...",
                           "#.######"};

    monsters(n, m, grid);

    return 0;
}