We have a grid with $H$ horizontal rows and $W$ vertical columns. $(i, j)$ denotes the square at the $i$-th row from the top and $j$-th column from the left. You are initially at $(1,1)$. You repeat the following operation until you cannot make a move. Let $(i,j)$ be the square you are currently at. Print the square you end up at when you cannot make a move.Problem Statement
$(i,j)$ has a character $G_{i,j}$ written on it. $G_{i,j}$ is U, D, L, or R.
If $G_{i,j}$ is U and $i \neq 1$, move to $(i-1,j)$.
If $G_{i,j}$ is D and $i \neq H$, move to $(i+1,j)$.
If $G_{i,j}$ is L and $j \neq 1$, move to $(i,j-1)$.
If $G_{i,j}$ is R and $j \neq W$, move to $(i,j+1)$.
Otherwise, you cannot make a move.
If you indefinitely repeat moving, print -1 instead.Constraints
U, D, L, or R.
Input
Input is given from Standard Input in the following format:
$H$ $W$
$G_{1,1}G_{1,2}\dots G_{1,W}$
$G_{2,1}G_{2,2}\dots G_{2,W}$
$\vdots$
$G_{H,1}G_{H,2}\dots G_{H,W}$
Output
If you end up at $(i, j)$, print it in the following format:
$i$ $j$
If you indefinitely repeat moving, print -1.
Sample Input 1
2 3 RDU LRU
Sample Output 1
1 3
You will move as $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$, ending up here, so the answer is $(1, 3)$.
Sample Input 2
2 3 RRD ULL
Sample Output 2
-1
You will indefinitely repeat moving as $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots$, so -1 should be printed in this case.
Sample Input 3
9 44 RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR
#include<cstdio>
const int tx[]={-1,1,0,0},ty[]={0,0,-1,1},N=505;
int n,m,v[N][N],t[N][N],x,y,dx,dy;
char ch;
int can(int x,int y)
{
return x>0&&x<=n&&y>0&&y<=m;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&ch);
if(ch=='D')
t[i][j]=1;
else if(ch=='L')
t[i][j]=2;
else if(ch=='R')
t[i][j]=3;
}
}
x=y=v[1][1]=1;
while(1)
{
dx=x+tx[t[x][y]],dy=y+ty[t[x][y]];
if(!can(dx,dy))
{
printf("%d %d\n",x,y);
return 0;
}
x=dx,y=dy;
if(v[x][y])
{
printf("-1");
return 0;
}
v[x][y]=1;
}
}