結果

問題 No.367 ナイトの転身
コンテスト
ユーザー nanophoto12
提出日時 2016-05-07 23:45:47
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,181 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 641 ms
コンパイル使用メモリ 91,468 KB
最終ジャッジ日時 2026-04-20 23:35:44
合計ジャッジ時間 1,959 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:48:12: error: 'make_tuple' was not declared in this scope
   48 |     q.push(make_tuple(0, start.first, start.second, 0));
      |            ^~~~~~~~~~
main.cpp:10:1: note: 'std::make_tuple' is defined in header '<tuple>'; this is probably fixable by adding '#include <tuple>'
    9 | #include <iomanip>
  +++ |+#include <tuple>
   10 | using namespace std;
main.cpp:53:9: error: 'tie' was not declared in this scope
   53 |         tie(count, x, y, board) = q.top();
      |         ^~~
main.cpp:53:9: note: 'std::tie' is defined in header '<tuple>'; this is probably fixable by adding '#include <tuple>'
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/vector:68,
                 from main.cpp:3:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<int, int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int, int> >]':
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_vector.h:561:7:   required from 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue() [with _Seq = std::vector<std::tuple<int, int, int, int> >; _Requires = void; _Tp = std::tuple<int, int, int, int>; _Sequence = std::vector<std::tuple<int, int, int, int> >; _Compare = std::greater<std::tuple<int, int, int, int> >]'
  561 |       vector() = default;
      |       ^~~~~~
main.cpp:47:52:   required from here
   47 |     priority_queue<ti4, vector<ti4>, greater<ti4>> q;
      |                                                    ^
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_vector.h:376:49: error: invalid use of incomplete type 'class std::tuple<int, int, int, int>'
  376 |                       _M_impl._M_end_of_storage - _M_impl._M_start);
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /home/linux

ソースコード

diff #
raw source code 

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
using namespace std;

#define ll long long int
#define ti4 tuple<int,int,int,int>
#define pii pair<int,int>

int B[2][500][500];
int red[500][500];

int main()
{
    int H, W;
    cin >> H >> W;
    fill(&red[0][0], &red[0][0] + 500 * 500, 0);
    fill(&B[0][0][0], &B[0][0][0] + 2 * 500 * 500, 1e6);
    pii start;
    pii end;
    for(int i = 0;i < H;i++)
    {
        string s;
        cin >> s;
        for(int j = 0;j < W;j++)
        {
            if(s[j] == 'S')
            {
                start = make_pair(j, i);
            }
            else if(s[j] == 'G')
            {
                end = make_pair(j, i);
            }
            else if(s[j] == 'R')
            {
                red[i][j] = 1;
            }
        }
    }
    priority_queue<ti4, vector<ti4>, greater<ti4>> q;
    q.push(make_tuple(0, start.first, start.second, 0));
    B[0][start.second][start.first] = 0;
    while(!q.empty())
    {
        int count, x, y, board;
        tie(count, x, y, board) = q.top();
        //cout << count << "," << x << "," << y << "," << board << endl;
        q.pop();
        if(x == end.first && y == end.second)
        {
            cout << count << endl;
            return 0;
        }
        int nc = count + 1;
        if(board == 0)
        {
            pii shift[] = {make_pair(-1,-2),make_pair(-2,-1),make_pair(1,-2),make_pair(2,-1),
                make_pair(-1,2),make_pair(-2,1),make_pair(1,2),make_pair(2,1)};
            for(int i = 0;i < 8;i++)
            {
                int nx = x + shift[i].first;
                int ny = y + shift[i].second;
                if(nx >= 0 && nx < W && ny >= 0 && ny < H)
                {
                    if(B[board][ny][nx] <= nc)
                    {
                        continue;
                    }
                    B[board][ny][nx] = nc;
                    if(red[ny][nx])
                    {
                        q.push(make_tuple(nc, nx, ny, 1));
                    }
                    else
                    {
                        q.push(make_tuple(nc, nx, ny, 0));
                    }
                }
            }
        }
        else
        {
            pii shift[] = {make_pair(-1,-1),make_pair(1,-1),make_pair(-1,1),make_pair(1,1)};
            for(int i = 0;i < 4;i++)
            {
                int nx = x + shift[i].first;
                int ny = y + shift[i].second;
                if(nx >= 0 && nx < W && ny >= 0 && ny < H)
                {
                    if(B[board][ny][nx] <= nc)
                    {
                        continue;
                    }
                    B[board][ny][nx] = nc;
                    if(red[ny][nx])
                    {
                        q.push(make_tuple(nc, nx, ny, 0));
                    }
                    else
                    {
                        q.push(make_tuple(nc, nx, ny, 1));
                    }
                }
            }
            
        }
    }
    cout << -1 << endl;
    return 0;
}
0