769C - Cycle In Maze - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int maxn = 1e3+5;
int n, m, k;
pii st;
char a[maxn][maxn];
int l[maxn][maxn], d[maxn][maxn];
int moveX[]={1,0,0,-1};
int moveY[]={0,-1,1,0};
string dr="DLRU", ans;
signed main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m >> k;
    if (k%2==1)
    {
    	cout<<"IMPOSSIBLE";
    	return 0;
    }
    for (int i=1; i<=n; i++)
    {
    	for (int j=1; j<=m; j++)
    	{
    		cin >> a[i][j];
    		if (a[i][j]=='X') 
    			{
    				st={i,j};
    				a[i][j]='.';
    			}
    	}
    }
    l[st.first][st.second]=1;
    d[st.first][st.second]=1;
	queue<pii>q;
	q.push({st.first,st.second});
	while (!q.empty())
	{
		int s=q.front().first;
		int e=q.front().second;
		q.pop();
		for (int i=0; i<4; i++)
		{
			int u=s+moveX[i];
			int v=e+moveY[i];
			if (u<1||u>n||v<1||v>m) continue;
			if (d[u][v]==0&&a[u][v]=='.')
				{
					l[u][v]=l[s][e]+1;
					d[u][v]=1;
					q.push({u,v});
				}
		}
	}
    while (k)
    {
    	int tx, ty;
    	bool flag=true;
    	for (int i=0; i<4; i++)
    	{
    		tx=st.first+moveX[i];
    		ty=st.second+moveY[i];
    		if (a[tx][ty]=='.'&&l[tx][ty]<=k)
    		{
    			ans+=dr[i];
    			st.first=tx;
    			st.second=ty;
    			flag=false;
    			break;
    		}
    	}
    	if (flag) {
    		cout<<"IMPOSSIBLE";
    		return 0;
    	}
    	k--;
    }
    cout<<ans;
}