Let \((i,j)\) denote the cell in the \(i\)-th row from the top and \(j\)-th column from the left. Also, let \((X_S,Y_S)\) be the cell with \(S_{i,j}=\)S, and \((X_G,Y_G)\) with \(S_{i,j}=\)G.

During Takahashi’s travel, the cells Takahashi can move to in the next step are uniquely determined by his current cell and the direction of the last move (regardless of his past path).
Therefore, let us manage his state as a pair of his “current cell” and “the direction of the last move.”
This way, given any state, the set of states that can be transitioned into is uniquely determined.

For example, if he is currently at cell \((i,j)\) and his last moving direction was to the right, and \(S_{i,j}=\) ., S, G, then the possible next states are:

• his current cell is \((i-1,j)\), and last direction was up
• his current cell is \((i+1,j)\), and last direction was down
• his current cell is \((i,j-1)\), and last direction was left
• his current cell is \((i,j+1)\), and last direction was right

Note that the cell he moves into does not exist or is #, some of the transitions above are not possible.

Also, if \(S_{i,j}=\) o, from the previous state described above,

• his current cell is \((i,j+1)\) and last direction was right

is the only next state allowed. (Again, if cell \((i,j+1)\) does not exist or is #, there is no state that can be transitioned into.)

The transitions for \(S_{i,j}=\) x can be enumerated likewise. Those for \(S_{i,j}=\) # do not need to be taken account because the previous state is impossible.

Therefore, we can define a graph with the vertices being Takahashi’s states, and the directed edges being the possible transitions. This way, the problem is reduced to determining the reachability from a state with current cell \((X_S,Y_S)\) (with any previous direction) to a state with current cell \((X_G,Y_G)\) (with any previous directed).
This can be solved with Depth-First Search (DFS) or Breadth-First Search (BFS), with pruning. Since the graph may contain a cycle (closed loop), make sure not to re-inspect an already-visited vertex.

To simplify implementation, one can define sur-vertices \(V_1\) and \(V_2\) and add edges from \(V_1\) to all vertices with current cell \((X_S,Y_S)\), and from all vertices with current cell \((X_G,Y_G)\) to \(V_2\); this way, the problem is boiled down to the reachability from \(V_1\) to \(V_2\).

In addition, when it is reachable, the path on the grid can be reconstructed from the path on the graph representation. To reconstruct the path, when you visit a vertex for the first time, record which vertex you came from; and the path can be obtained by backtracking those records from \(V_2\). If no two vertices are revisited, the length of the path on the graph is at most \(4HW+1\). Since each traversal of an edge on the graph (except for those concerning the sur-vertices) corresponds to one move on the grid, the number of moves on the grid is at most \(4HW-1\), which is at most \(5\times 10^6\), satisfying the constraint.

The time complexity is \(O(HW)\). Although the constant factor is a bit heavy, it is fast enough.
Therefore, the problem has been solved.

Sample code in C++:

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

#define rep(i, n) for(int i = 0; i < n; ++i)
#define D (int)4
#define K (int)1000
#define N (int)4e+6

int dx[D]={-1,1,0,0};
int dy[D]={0,0,-1,1};

int h,w;
string s[K];
int sx,gx,sy,gy;
vector<int>e[N+2];
int prv[N+2];

void init(void){
	rep(i,h)rep(j,w){
		rep(d,D)prv[(i*K+j)*D+d]=-1;
		if(s[i][j]=='#')continue;
		if(s[i][j]=='S'){sx=i;sy=j;}
		if(s[i][j]=='G'){gx=i;gy=j;}
		rep(d2,D){
			if((i+dx[d2]>=0)&&(i+dx[d2]<h)&&(j+dy[d2]>=0)&&(j+dy[d2]<w)&&s[i+dx[d2]][j+dy[d2]]!='#'){
				rep(d1,D){
					int idx1=(i*K+j)*D+d1;
					int idx2=((i+dx[d2])*K+(j+dy[d2]))*D+d2;
					if((d1!=d2)&&(s[i][j]!='o'))e[idx1].push_back(idx2);
					if((d1==d2)&&(s[i][j]!='x'))e[idx1].push_back(idx2);
				}
			}
		}
		
	}
	rep(sd,4)e[N].push_back((sx*K+sy)*D+sd);
	rep(gd,4)e[(gx*K+gy)*D+gd].push_back(N+1);
	prv[N]=-2; prv[N+1]=-1;
	return;
}

int main(void){
	cin>>h>>w;
	rep(i,h)cin>>s[i];
	init();

	queue<int>q;
	q.push(N);
	bool flag=false;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		int sz=e[k].size();
		rep(i,sz){
			if(prv[e[k][i]]==-1){
				prv[e[k][i]]=k;
				q.push(e[k][i]);
				if(e[k][i]==(N+1))flag=true;
			}
		}
		if(flag)break;
	}

	if(flag){
		string ans;
		int cur=prv[N+1];
		while(prv[cur]!=N){
			int x=(prv[cur]/D)/K;
			int y=(prv[cur]/D)%K;
			int x2=(cur/D)/K;
			int y2=(cur/D)%K;
			if(x2==x-1)ans+="U";
			if(x2==x+1)ans+="D";
			if(y2==y-1)ans+="L";
			if(y2==y+1)ans+="R";
			cur=prv[cur];
		}
		reverse(ans.begin(), ans.end());
		cout<<"Yes"<<endl;
		cout<<ans<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	
	return 0;
}