以下では、上から \(i\) 番目かつ左から \(j\) 番目のマスをマス \((i,j)\) で表します。また、\(S_{i,j}=\)S である唯一のマスをマス \((X_S,Y_S)\)、\(S_{i,j}=\)G である唯一のマスをマス \((X_G,Y_G)\) とします。

移動中の高橋君が次に移動できるマスは、高橋君の「現在いるマス」および「直前の移動においてどの方向に移動したか」が分かれば、（ぞれ以前の移動経路等によらず）一意に定ります。
そこで、高橋君が「現在いるマス」および「直前の移動においてどの方向に移動したか」の組を高橋君の状態として管理することを考えます。
このとき、ある状態から遷移できる次の状態は一意に定まります。

例えば、高橋君がマス \((i,j)\) におり、直前に右方向に移動していたとき、 \(S_{i,j}=\) ., S, G ならば次の状態としては

• マス \((i-1,j)\) におり、直前に上方向に移動した状態
• マス \((i+1,j)\) におり、直前に下方向に移動した状態
• マス \((i,j-1)\) におり、直前に左方向に移動した状態
• マス \((i,j+1)\) におり、直前に右方向に移動した状態

が考えられます。ただし、移動先のマスが存在しない、あるいは # マスの場合は、上記のうち一部の状態はあり得ないことに注意してください。

また、\(S_{i,j}=\) o ならば、同様の状態からは

• マス \((i,j+1)\) におり、直前に右方向に移動した状態

のみが許されます。（上記と同様に、マス \((i,j+1)\) が存在しない、あるいは # マスの場合はその状態から遷移できる状態は無いということになります。）

同様に、\(S_{i,j}=\) x の場合についても遷移を定義でき、\(S_{i,j}=\) # のときは元の状態があり得ないため、遷移を考える必要はありません。

よって、高橋君の状態を頂点とし、あり得る状態の遷移を有向辺としたグラフを考えることができます。このとき元の問題は、高橋君がマス \((X_S,Y_S)\) にいる状態（直前の移動方向は何でも良い）に対応する頂点のいずれかから、マス \((X_G,Y_G)\) にいる状態（直前の移動方向は何でも良い）のいずれかへ到達可能かという問題に言い換えることができます。
これは枝刈り付きの深さ優先探索(DFS)や幅優先探索(BFS)などで解くことができます。サイクル（閉路）が存在する可能性があるため、すでに一度探索した頂点は二度と調べないようにする必要があることに注意してください。

また、工夫として、超頂点 \(V_1\), \(V_2\) を考え、\(V_1\) から高橋君がマス \((X_S,Y_S)\) にいる状態に対応する頂点それぞれに有向辺を張り、高橋君がマス \((X_G,Y_G)\) にいる状態に対応する頂点それぞれから \(V_2\) へ有向辺を張ることで、この問題を単に \(V_1\) から \(V_2\) へ到達可能かという問題に帰着することができます。

さらに、可能なときのマス目上の移動方法の例については、帰着したグラフにおける経路が分かれば、その状態遷移の履歴から復元することができます。そして、グラフにおける経路復元は、それぞれの頂点において、\(V_1\) から始めて探索を行った際、初めてその頂点に到達した時のその直前の頂点を記録しておき、それを \(V_2\) から逆順に辿ることで求めることができます。このとき、探索時に同じ頂点を \(2\) 回以上探索しないようにしていれば、グラフにおける経路の長さは \(4HW+1\) 以下であり、グラフにおける辺に沿った移動（超頂点を端点とするものを除く）とマス目における移動は対応していることから、マス目における移動回数は高々 \(4HW-1\) 、特に \(5\times 10^6\) 以下となり、条件をみたしています。

時間計算量は \(O(HW)\) であり、定数倍は多少重いですが、十分高速です。
よって、この問題を解くことができました。

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;
}