結果

問題 No.367 ナイトの転身
コンテスト
ユーザー face4
提出日時 2018-11-02 11:26:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 1,534 bytes
コンパイル時間 1,056 ms
コンパイル使用メモリ 75,708 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-20 12:25:54
合計ジャッジ時間 2,590 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:46:22: warning: 'gj' may be used uninitialized [-Wmaybe-uninitialized]
   46 |         if(d.i == gi && d.j == gj){
      |            ~~~~~~~~~~^~~~~~~~~~~~
main.cpp:22:21: note: 'gj' was declared here
   22 |     int si, sj, gi, gj;
      |                     ^~
main.cpp:46:9: warning: 'gi' may be used uninitialized [-Wmaybe-uninitialized]
   46 |         if(d.i == gi && d.j == gj){
      |         ^~
main.cpp:22:17: note: 'gi' was declared here
   22 |     int si, sj, gi, gj;
      |                 ^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/allocator.h:46,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
                 from main.cpp:1:
In member function 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = data; _Args = {data}; _Tp = data]',
    inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = data; _Args = {data}; _Tp = data]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/alloc_traits.h:516:17,
    inlined from 'void std::deque<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {data}; _Tp = data; _Alloc = std::allocator<data>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@

ソースコード

diff # 

#include<iostream>
#include<queue>
using namespace std;

#define inRange(x,a,b) (a <= x && x < b)

struct data{
    // pos-i, pos-j, type(0-knight, 1-bishop), cost
    int i, j, t, c;
};

int dx[2][8] = { {1,1,-1,-1,2,2,-2,-2}, {1,1,-1,-1,0,0,0,0} };
int dy[2][8] = { {2,-2,2,-2,1,-1,1,-1}, {1,-1,1,-1,0,0,0,0} };

int main(){
    int h, w;
    cin >> h >> w;

    char mat[h][w];
    int dp[h][w][2]; // 0-knight, 1-bishop
    int INF = 300000;
    int si, sj, gi, gj;

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> mat[i][j];
            if(mat[i][j] == 'S')    si = i, sj = j;
            if(mat[i][j] == 'G')    gi = i, gj = j;
            dp[i][j][0] = dp[i][j][1] = INF;
        }
    }

    queue<data> s;
    s.push(data({si, sj, 0, 0}));

    while(!s.empty()){
        data d = s.front();   s.pop();

        // discard
        if(d.c >= dp[d.i][d.j][d.t])    continue;

        // apply
        dp[d.i][d.j][d.t] = d.c;

        // goal
        if(d.i == gi && d.j == gj){
            cout << d.c << endl;
            return 0;
        }

        // metamorphosis
        if(mat[d.i][d.j] == 'R')    d.t = 1 - d.t;

        // move
        for(int k = 0; k < 8; k++){
            int ni = d.i + dx[d.t][k];
            int nj = d.j + dy[d.t][k];

            if(!inRange(ni, 0, h) || !inRange(nj, 0, w))    continue;

            if(d.c + 1 < dp[ni][nj][d.t]){
                s.push(data({ni,nj,d.t,d.c+1}));
            }
        }

    }

    cout << -1 << endl;

    return 0;
}
0