結果

問題 No.367 ナイトの転身
コンテスト
ユーザー t98slider
提出日時 2023-03-23 15:55:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 1,372 bytes
コンパイル時間 1,908 ms
コンパイル使用メモリ 188,024 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-09-18 15:29:40
合計ジャッジ時間 3,072 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/functional:54,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:71,
                 from main.cpp:1:
In constructor 'constexpr std::_Head_base<_Idx, _Head, false>::_Head_base(_UHead&&) [with _UHead = int&; long unsigned int _Idx = 1; _Head = int]',
    inlined from 'constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(_UHead&&, _UTail&& ...) [with _UHead = int&; _UTail = {int}; <template-parameter-2-3> = void; long unsigned int _Idx = 1; _Head = int; _Tail = {int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:292:38,
    inlined from 'constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(_UHead&&, _UTail&& ...) [with _UHead = int&; _UTail = {int&, int}; <template-parameter-2-3> = void; long unsigned int _Idx = 0; _Head = int; _Tail = {int, int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:292:38,
    inlined from 'constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int&, int}; bool _Valid = true; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = true; _Elements = {int, int, int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:744:54,
    inlined from 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::tuple<int, int, int>; _Args = {int&, int&, int}; _Tp = std::tuple<int, int, int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/new_allocator.h:175:4,
    inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::tuple<int, int, int>; _Args = {int&, int&, int}; _Tp = std::tuple<int, int, int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/alloc_trait

ソースコード

diff # 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w, sy, sx, gy, gx;
    cin >> h >> w;
    vector<string> A(h);
    for(int y = 0; y < h; y++){
        cin >> A[y];
        for(int x = 0; x < w; x++){
            if(A[y][x] == 'S') sy = y, sx = x;
            if(A[y][x] == 'G') gy = y, gx = x;
        }
    }
    vector<vector<pair<int,int>>> dir = {
        {{-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, 1}, {2, -1}, {-2, -1}, {-2, 1}},
        {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
    };
    queue<tuple<int,int,int>> nxt;
    vector<vector<array<int,2>>> dp(h, vector<array<int,2>>(w, array<int,2>({1 << 30, 1 << 30})));
    dp[sy][sx][0] = 0;
    nxt.emplace(sy, sx, 0);
    while(!nxt.empty()){
        int y, x, s, dy, dx, ny, nx, ns;
        tie(y, x, s) = nxt.front();
        nxt.pop();
        for(auto &&p : dir[s]){
            tie(dy, dx) = p;
            ny = y + dy;
            nx = x + dx;
            if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            ns = s ^ (A[ny][nx] == 'R');
            if(dp[y][x][s] + 1 >= dp[ny][nx][ns]) continue;
            dp[ny][nx][ns] = dp[y][x][s] + 1;
            nxt.emplace(ny, nx, ns);
        }
    }
    int ans = min(dp[gy][gx][0], dp[gy][gx][1]);
    if(ans == (1 << 30)) ans = -1;
    cout << ans << '\n';
}
0