結果

問題 No.367 ナイトの転身
ユーザー face4face4
提出日時 2018-11-02 11:26:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 1,534 bytes
コンパイル時間 811 ms
コンパイル使用メモリ 75,332 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-30 16:04:57
合計ジャッジ時間 2,230 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 30 ms
6,940 KB
testcase_11 AC 51 ms
6,944 KB
testcase_12 AC 11 ms
6,940 KB
testcase_13 AC 11 ms
6,940 KB
testcase_14 AC 18 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 18 ms
6,940 KB
testcase_17 AC 4 ms
6,940 KB
testcase_18 AC 5 ms
6,944 KB
testcase_19 AC 5 ms
6,940 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 6 ms
6,940 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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