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

• 問題: No.3738 Right Hamiltonian
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 07:48:01
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 519 ms / 2,000 ms
• コード長: 10,645 bytes
• コンパイル時間: 2,564 ms
• コンパイル使用メモリ: 358,800 KB
• 実行使用メモリ: 58,540 KB
• 最終ジャッジ日時: 2026-09-19 13:30:08
• 合計ジャッジ時間: 8,886 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

サブタスク	配点	結果
部分点	80 %	AC * 38
満点	20 %	AC * 60
合計	4 * 100% = 400 点

ソースコード

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

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

struct Seg{
    int d,len;
};

int H,W,N;
vector<string> A;
vector<unsigned char> vis;
vector<array<unsigned short,4>> runn;
vector<int> 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<Seg>& 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<Seg>& 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<Seg>& ans,const vector<Seg>& 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<Seg> v){
    vector<Seg> 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<<st/W+1<<" "<<st%W+1<<" "<<DCH[s[0].d]<<"\n";
    cout<<x.size()<<"\n";
    cout<<x<<"\n";

    return true;
}


// 外周に壁がある場合用。
// 候補が2通りしかないのでマス単位で処理する。
int slow_grow(int s,int d,int turn,Rect q,vector<Seg>& 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<Seg>& 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<int>(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<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++;
            }
        }
    }


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


    if(N==1){
        for(int r=0;r<H;r++){
            for(int c=0;c<W;c++){
                if(A[r][c]=='.'){
                    cout<<r+1<<" "<<c+1<<" U\n";
                    cout<<0<<"\n\n";
                }
            }
        }

        return 0;
    }


    // B が1行
    if(U==D){
        for(int c=L;c<=R;c++){
            if(A[U][c]=='#'){
                cout<<-1<<"\n";
                return 0;
            }
        }

        output(id(U,L),{{1,R-L}});

        return 0;
    }


    // B が1列
    if(L==R){
        for(int r=U;r<=D;r++){
            if(A[r][L]=='#'){
                cout<<-1<<"\n";
                return 0;
            }
        }

        output(id(U,L),{{2,D-U}});

        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;
        int 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[(int)O.size()-2],
            O.back()
        );


        vis.assign(H*W,0);

        vector<Seg> 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<H;r++){
        for(int c=0;c<W;c++){
            if(A[r][c]=='#'){
                continue;
            }

            int v=id(r,c);

            runn[v][0]
                =1+(r?runn[v-W][0]:0);

            runn[v][3]
                =1+(c?runn[v-1][3]:0);
        }
    }


    // D, R
    for(int r=H-1;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<H?runn[v+W][2]:0);

            runn[v][1]
                =1+(c+1<W?runn[v+1][1]:0);
        }
    }


    // 床=1, 壁=0 の2次元累積和
    int S=W+1;

    ps.assign((H+1)*S,0);

    for(int r=0;r<H;r++){
        int row=0;

        for(int c=0;c<W;c++){
            row+=(A[r][c]=='.');

            ps[(r+1)*S+c+1]
                =ps[r*S+c+1]+row;
        }
    }


    vector<Seg> 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<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;
        Rect 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;
        }
        else if(od==3){
            a.c2=sc;
            b.c1=tc;
        }
        else if(od==2){
            a.r1=sr;
            b.r2=tr;
        }
        else{
            a.r2=sr;
            b.r1=tr;
        }


        // s 側は逆向き左回り
        int cl=fast_grow(
            s,
            (fd+1)%4,
            -1,
            a,
            l
        );

        if(cl!=rect_sum(a)){
            continue;
        }


        // t 側は順向き右回り
        int cr=fast_grow(
            t,
            (ld+1)%4,
            1,
            b,
            r
        );

        if(cr!=rect_sum(b)){
            continue;
        }


        ans.clear();


        // s 側を逆転
        add_rev(ans,l);


        // 外周 s -> ... -> t
        for(int j=0;j<m-1;j++){
            int x=P[(i+1+j)%m];
            int y=P[(i+2+j)%m];

            add(
                ans,
                dir(x,y),
                1
            );
        }


        // t 側
        for(auto x:r){
            add(ans,x.d,x.len);
        }


        if(output(endpoint(s,l),ans)){
            return 0;
        }
    }


    cout<<-1<<"\n";
}