Link to this code:
https://cses.fi/paste/aa91e959b18b0063107ccd/
/*----------------------------------------------------*
* लेखक --> अमित सिंह
* संस्थान --> राष्ट्रीय प्रौद्योगिकी संस्थान, कुरुक्षेत्र
*-----------------------------------------------------*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define w(t) \
int t; \
cin >> t; \
while (t--)
#define fo(i, n) for (int i = 0; i < n; i++)
#define endl "\n"
#define MOD 1000000007
void Tez()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int n, m, sx, sy, ex, ey;
map<pair<int, int>, int> dist;
bool isValid(int x, int y)
{
if (x < 0 || x >= n || y < 0 || y >= m || dist[{x, y}] != -1)
return false;
return true;
}
char getDir(int x, int y)
{
if (x == 1)
return 'D';
if (x == -1)
return 'U';
if (y == 1)
return 'R';
if (y == -1)
return 'L';
return 'N';
}
string getPath(vector<vector<char>> &grid)
{
string path;
int x = ex, y = ey;
while (x != sx || y != sy)
{
path += grid[x][y];
switch (grid[x][y])
{
case 'R':
y -= 1;
break;
case 'L':
y += 1;
break;
case 'U':
x += 1;
break;
case 'D':
x -= 1;
break;
}
}
reverse(path.begin(), path.end());
return path;
}
void bfs(vector<vector<char>> &grid)
{
queue<pair<int, int>> que;
que.push({sx, sy});
dist[{sx, sy}] = 0;
while (!que.empty())
{
int x = que.front().first;
int y = que.front().second;
que.pop();
if (x == ex && y == ey)
break;
fo(i, 4)
{
if (isValid(x + dx[i], y + dy[i]) && grid[x+dx[i]][y+dy[i]]!='#')
{
int newx = x + dx[i];
int newy = y + dy[i];
dist[{newx, newy}] = dist[{x, y}] + 1;
grid[newx][newy] = getDir(dx[i], dy[i]);
que.push({newx,newy});
}
}
}
if (dist[{ex, ey}] != -1)
{
cout << "YES\n";
cout << dist[{ex, ey}] << endl;
string path = getPath(grid);
cout << path;
}
else
{
cout << "NO\n";
}
}
int main()
{
Tez();
cin >> n >> m;
vector<vector<char>> v(n, vector<char>(m));
fo(i, n)
{
fo(j, m)
{
cin >> v[i][j];
dist[{i, j}] = -1;
if (v[i][j] == 'A')
{
sx = i;
sy = j;
}
if (v[i][j] == 'B')
{
ex = i;
ey = j;
}
}
}
bfs(v);
return 0;
}