#include using namespace std; struct Rect{ int r1,c1,r2,c2; }; struct Seg{ int d,len; }; int H,W,N; vector A; vector vis; vector> runn; vector ps; int dr[4]={-1,0,1,0}; int dc[4]={0,1,0,-1}; char DCH[4]={'U','R','D','L'}; int id(int r,int c){ return r*W+c; } bool in(int r,int c,Rect q){ return q.r1<=r&&r<=q.r2&&q.c1<=c&&c<=q.c2; } int dir(int a,int b){ int r=a/W,c=a%W; int x=b/W,y=b%W; for(int d=0;d<4;d++){ if(r+dr[d]==x&&c+dc[d]==y) return d; } return -1; } void add(vector& v,int d,int len){ if(len==0) return; if(!v.empty()&&v.back().d==d){ v.back().len+=len; }else{ v.push_back({d,len}); } } int endpoint(int s,const vector& v){ int r=s/W,c=s%W; for(auto [d,len]:v){ r+=dr[d]*len; c+=dc[d]*len; } return id(r,c); } void add_rev(vector& ans,const vector& v){ for(int i=(int)v.size()-1;i>=0;i--){ add(ans,(v[i].d+2)%4,v[i].len); } } bool output(int st,vector v){ vector s; for(auto x:v){ add(s,x.d,x.len); } long long moves=0; for(auto x:s){ moves+=x.len; } if(moves!=N-1||s.empty()) return false; for(int i=1;i<(int)s.size();i++){ if(s[i].d!=(s[i-1].d+1)%4){ return false; } } string x; x.reserve(N-1); x.append(s[0].len,'F'); for(int i=1;i<(int)s.size();i++){ x.push_back('R'); x.append(s[i].len-1,'F'); } cout<& v){ v.clear(); int r=s/W,c=s%W; int cnt=0; auto can=[&](int x,int y){ return in(x,y,q) &&A[x][y]=='.' &&!vis[id(x,y)]; }; while(true){ int x=r+dr[d]; int y=c+dc[d]; if(!can(x,y)){ d=(d+turn+4)%4; x=r+dr[d]; y=c+dc[d]; if(!can(x,y)){ break; } } r=x; c=y; vis[id(r,c)]=1; add(v,d,1); cnt++; } return cnt; } // 長方形内の床マス数 int rect_sum(Rect q){ if(q.r1>q.r2||q.c1>q.c2){ return 0; } int S=W+1; return ps[(q.r2+1)*S+q.c2+1] -ps[q.r1*S+q.c2+1] -ps[(q.r2+1)*S+q.c1] +ps[q.r1*S+q.c1]; } // 満点用の高速な渦巻き。 // 1マスずつではなく1直線ずつ進む。 int fast_grow(int s,int d,int turn,Rect q,vector& v){ v.clear(); int r=s/W,c=s%W; int cnt=0; while(true){ int x=r+dr[d]; int y=c+dc[d]; if(!in(x,y,q)||A[x][y]=='#'){ break; } int lim; if(d==0) lim=x-q.r1+1; else if(d==1) lim=q.c2-y+1; else if(d==2) lim=q.r2-x+1; else lim=y-q.c1+1; int len=min(runn[id(x,y)][d],lim); add(v,d,len); cnt+=len; r+=dr[d]*len; c+=dc[d]*len; int nd=(d+turn+4)%4; // 今通った直線を今後の領域から除外する。 if(nd==0) q.r2=r-1; else if(nd==1) q.c1=c+1; else if(nd==2) q.r1=r+1; else q.c2=c-1; d=nd; } return cnt; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>H>>W; A.resize(H); for(auto& s:A){ cin>>s; } int U=H,D=-1,L=W,R=-1; for(int r=0;r P; for(int c=L;c<=R;c++){ P.push_back(id(U,c)); } for(int r=U+1;r<=D;r++){ P.push_back(id(r,R)); } for(int c=R-1;c>=L;c--){ P.push_back(id(D,c)); } for(int r=D-1;r>U;r--){ P.push_back(id(r,L)); } int m=P.size(); bool full=true; for(int v:P){ full&=(A[v/W][v%W]=='.'); } Rect whole={U,L,D,R}; Rect inner={U+1,L+1,D-1,R-1}; // ========================================================= // 外周に壁がある // ========================================================= if(!full){ int st=-1; int runs=0; for(int i=0;i O; for( int i=st; A[P[i]/W][P[i]%W]=='.'; i=(i+1)%m ){ O.push_back(P[i]); } int s=O.front(); int t=O.back(); int fd=dir(O[0],O[1]); int ld=dir( O[(int)O.size()-2], O.back() ); vis.assign(H*W,0); vector l,r,ans; // どちらの渦巻きを先に伸ばすかの2通り for(int z=0;z<2;z++){ fill(vis.begin(),vis.end(),0); for(int v:O){ vis[v]=1; } int cl,cr; if(z==0){ cl=slow_grow( s, (fd+2)%4, -1, whole, l ); cr=slow_grow( t, ld, 1, whole, r ); }else{ cr=slow_grow( t, ld, 1, whole, r ); cl=slow_grow( s, (fd+2)%4, -1, whole, l ); } if((int)O.size()+cl+cr!=N){ continue; } ans.clear(); add_rev(ans,l); for(int i=1;i<(int)O.size();i++){ add( ans, dir(O[i-1],O[i]), 1 ); } for(auto x:r){ add(ans,x.d,x.len); } if(output(endpoint(s,l),ans)){ return 0; } } cout<<-1<<"\n"; return 0; } // ========================================================= // ここから外周が全て床 // ========================================================= // 各マスから4方向に連続する床マス数 runn.assign(H*W,{}); // U, L for(int r=0;r=0;r--){ for(int c=W-1;c>=0;c--){ if(A[r][c]=='#'){ continue; } int v=id(r,c); runn[v][2] =1+(r+1 l,r,ans; l.reserve(min(H,W)+5); r.reserve(min(H,W)+5); ans.reserve(2*min(H,W)+10); // 使わない外周辺 t -> s を全探索 for(int i=0;i ... -> t for(int j=0;j