結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Kurao
提出日時 2026-04-21 21:32:44
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,927 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,987 ms
コンパイル使用メモリ 201,080 KB
実行使用メモリ 73,884 KB
最終ジャッジ日時 2026-04-21 21:34:01
合計ジャッジ時間 62,226 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 84 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

#include<iostream>
#include<vector>
#include<array>
#include<queue>

using namespace std;
#define overload4(_1,_2,_3,_4,name,...) name

#define rep1(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep3(i,m,n,k) for (int i = (m); i < (n); i += (k))

#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

vector<pair<int,int>> dij = {{0,1}, {1,0}, {0,-1}, {-1,0}};

int main()
{
    int h,w;
    cin>>h>>w;
    string s[h];
    rep (i,h){
        cin>>s[i];
    }
    int hh,ww;
    hh=2*h-1;
    ww=2*w-1;
    array<int,2> ss,gg;
    rep(i,h){
        rep(j,w){
            if (s[i][j]=='S'){
                ss[0]=2*i;
                ss[1]=2*j;
                s[i][j]='.';
            } else if (s[i][j]=='G'){
                gg[0]=2*i;
                gg[1]=2*j;
                s[i][j]='.';
            }
        }
    }
    int d[hh][ww];
    rep (i,hh){
        rep (j,ww){
            d[i][j]=-1;
        }
    }
    d[ss[0]][ss[1]]=0;
    queue<array<int,2>> task;
    task.push(ss);
    while (task.size()>0){
        array<int,2> place=task.front();
        task.pop();
        int ii=place[0];
        int jj=place[1];
        vector<array<int,2>> rin={};
        for (auto [di,dj]:dij){
            if (0<=ii+di and ii+di<hh and 0<=jj+dj and jj+dj<ww and ((ii+di)%2==1 or (jj+dj)%2==1 or s[(ii+di)/2][(jj+dj)/2]=='.')){
                array<int,2> new_place={ii+di,jj+dj};
                rin.push_back(new_place);
            }
        }
        if (ii%2==0 and jj%2==0){
            for (auto [di,dj]:dij){
                di*=2;
                dj*=2;
                //cout<<(ii+di)/2<<" "<<jj+dj<<endl;
                if (0<=ii+di and ii+di<hh and 0<=jj+dj and jj+dj<ww and s[(ii+di)/2][(jj+dj)/2]=='.'){
                    array<int,2> new_place={ii+di,jj+dj};
                    rin.push_back(new_place);
                }
            }
        }
        if (ii%2==0 and jj%2==1){
            for (int di:{2,-2}){
                if (0<=ii+di and ii+di<hh){
                    array<int,2> new_place={ii+di,jj};
                    rin.push_back(new_place);
                }
            }
        }
        if (ii%2==1 and jj%2==0){
            for (int dj:{2,-2}){
                if (0<=jj+dj and jj+dj<ww){
                    array<int,2> new_place={ii,jj+dj};
                    rin.push_back(new_place);
                }
            }
        }
        for (auto i:rin){
            //cout<<rin.size()<<endl;
            if (d[i[0]][i[1]]==-1){
                //cout<<i[0]<<" "<<i[1]<<endl;
                d[i[0]][i[1]]=d[place[0]][place[1]]+1;
                if (i==gg){
                    cout<<d[gg[0]][gg[1]]<<endl;
                    return 0;
                }
                task.push(i);
            }
        }
    }
}
0