#include using namespace std; struct Rect{ int r1,c1,r2,c2; }; int H,W,T; vector A; vector vis; int dr[4]={-1,0,1,0}, dc[4]={0,1,0,-1}; char DCH[4]={'U','R','D','L'}; int id(int r,int c){ return r*W+c; } int dir(int a,int b){ int r=a/W,c=a%W, 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; } bool inside(int r,int c,Rect q){ return q.r1<=r&&r<=q.r2&&q.c1<=c&&c<=q.c2; } // s は既に訪問済み // turn=1:右折, turn=-1:左折 vector grow(int s,int d,int turn,Rect q){ vector p={s}; int r=s/W,c=s%W; auto can=[&](int x,int y){ return 0<=x&&x merge_path(vector L,const vector& O,const vector& R){ reverse(L.begin(),L.end()); for(int i=1;i<(int)O.size();i++) L.push_back(O[i]); for(int i=1;i<(int)R.size();i++) L.push_back(R[i]); return L; } void output(const vector& p){ int n=p.size(); int r=p[0]/W,c=p[0]%W; if(n==1){ cout<>H>>W; A.resize(H); for(auto& s:A) cin>>s; int U=H,D=-1,L=W,R=-1,N=0; for(int r=0;r p; for(int c=L;c<=R;c++){ if(A[U][c]=='#'){ cout<<-1<<"\n"; return 0; } p.push_back(id(U,c)); } output(p); return 0; } // B が1列 if(L==R){ vector p; for(int r=U;r<=D;r++){ if(A[r][L]=='#'){ cout<<-1<<"\n"; return 0; } p.push_back(id(r,L)); } output(p); return 0; } // B の外周を時計回り vector 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,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[O.size()-2],O.back()); // どちらの渦巻きを先に伸ばすか for(int z=0;z<2;z++){ ++T; for(int v:O) vis[v]=T; vector l,r; if(z==0){ l=grow(s,(fd+2)%4,-1,whole); r=grow(t,ld,1,whole); }else{ r=grow(t,ld,1,whole); l=grow(s,(fd+2)%4,-1,whole); } if((int)O.size()+l.size()+r.size()-2==N){ output(merge_path(l,O,r)); return 0; } } cout<<-1<<"\n"; return 0; } // 外周が全て床 // 使わない外周辺を全探索 for(int i=0;i O; for(int j=(i+1)%m;;j=(j+1)%m){ O.push_back(P[j]); if(j==i) break; } output(merge_path(l,O,r)); return 0; } cout<<-1<<"\n"; }