#1187915 (C++23) No.3738 Right Hamiltonian

• 問題: No.3738 Right Hamiltonian
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 07:39:49
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 5,280 bytes
• コンパイル時間: 2,438 ms
• コンパイル使用メモリ: 349,960 KB
• 実行使用メモリ: 67,076 KB
• 最終ジャッジ日時: 2026-09-19 13:30:11
• 合計ジャッジ時間: 13,828 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

サブタスク	配点	結果
部分点	80 %	AC * 38
満点	20 %	AC * 56 TLE * 1 -- * 3
合計	4 * 80% = 320 点

ソースコード

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

struct Rect{ int r1,c1,r2,c2; };

int H,W,T;
vector<string> A;
vector<int> 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<int> grow(int s,int d,int turn,Rect q){
    vector<int> p={s};
    int r=s/W,c=s%W;

    auto can=[&](int x,int y){
        return 0<=x&&x<H&&0<=y&&y<W
            &&inside(x,y,q)
            &&A[x][y]=='.'
            &&vis[id(x,y)]!=T;
    };

    while(1){
        int x=r+dr[d],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)]=T;
        p.push_back(id(r,c));
    }

    return p;
}

vector<int> merge_path(vector<int> L,const vector<int>& O,const vector<int>& 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<int>& p){
    int n=p.size();
    int r=p[0]/W,c=p[0]%W;

    if(n==1){
        cout<<r+1<<" "<<c+1<<" U\n0\n\n";
        return;
    }

    int d=dir(p[0],p[1]),pre=d;
    string s="F";

    for(int i=2;i<n;i++){
        int nd=dir(p[i-1],p[i]);
        assert(nd==pre || nd==(pre+1)%4);
        s+=(nd==pre?'F':'R');
        pre=nd;
    }

    cout<<r+1<<" "<<c+1<<" "<<DCH[d]<<"\n";
    cout<<s.size()<<"\n"<<s<<"\n";
}

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,N=0;

    for(int r=0;r<H;r++) for(int c=0;c<W;c++){
        if(A[r][c]=='.'){
            U=min(U,r); D=max(D,r);
            L=min(L,c); R=max(R,c);
            N++;
        }
    }

    vis.assign(H*W,0);

    if(N==1){
        for(int r=0;r<H;r++) for(int c=0;c<W;c++)
            if(A[r][c]=='.') output({id(r,c)});
        return 0;
    }

    // B が1行
    if(U==D){
        vector<int> 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<int> 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<int> 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<m;i++){
            int a=P[(i+m-1)%m];
            int b=P[i];

            if(A[a/W][a%W]=='#' &&
               A[b/W][b%W]=='.'){
                runs++;
                st=i;
            }
        }

        if(runs!=1){
            cout<<-1<<"\n";
            return 0;
        }

        vector<int> 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<int> 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<m;i++){
        int t=P[i];
        int s=P[(i+1)%m];

        int od=dir(t,s);
        int fd=dir(s,P[(i+2)%m]);
        int ld=dir(P[(i+m-1)%m],t);

        Rect a=inner,b=inner;

        int sr=s/W,sc=s%W;
        int tr=t/W,tc=t%W;

        if(od==1) a.c1=sc,b.c2=tc;
        if(od==3) a.c2=sc,b.c1=tc;
        if(od==2) a.r1=sr,b.r2=tr;
        if(od==0) a.r2=sr,b.r1=tr;

        ++T;
        for(int v:P) vis[v]=T;

        auto l=grow(s,(fd+2)%4,-1,a);
        auto r=grow(t,ld,1,b);

        if(m+(int)l.size()+(int)r.size()-2!=N)
            continue;

        vector<int> 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";
}