結果

問題 No.367 ナイトの転身
コンテスト
ユーザー yuppe19 😺
提出日時 2016-06-11 16:58:12
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 1,440 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,824 ms
コンパイル使用メモリ 195,988 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-03-08 16:06:34
合計ジャッジ時間 1,997 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /usr/include/c++/12/functional:54,
                 from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:71,
                 from <command-line>:
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 = {bool, int}; <template-parameter-2-3> = void; long unsigned int _Idx = 1; _Head = int; _Tail = {bool, int}]’ at /usr/include/c++/12/tuple:292:38,
    inlined from ‘constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(_UHead&&, _UTail&& ...) [with _UHead = int&; _UTail = {int&, bool, int}; <template-parameter-2-3> = void; long unsigned int _Idx = 0; _Head = int; _Tail = {int, bool, int}]’ at /usr/include/c++/12/tuple:292:38,
    inlined from ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int&, bool, int}; bool _Valid = true; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = true; _Elements = {int, int, bool, int}]’ at /usr/include/c++/12/tuple:744:54,
    inlined from ‘void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::tuple<int, int, bool, int>; _Args = {int&, int&, bool, int}; _Tp = std::tuple<int, int, bool, int>]’ at /usr/include/c++/12/bits/new_allocator.h:186:4,
    inlined from ‘static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::tuple<int, int, bool, int>; _Args = {int&, int&, bool, int}; _Tp = std::tuple<int, int, bool, int>]’ at /usr/include/c++/12/bits/alloc_traits.h:516:17,
    inlined from ‘void std::deque<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&, int&, bool, int}; _Tp = std::tuple<int, int, bool, int>; _Alloc = std::allocator<std::tuple<int

ソースコード

diff #
raw source code 

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

const int inf = 987654321;
int gr, gc;
int R, C;
vector<string> G;
vector<vector<vector<bool>>> seen;
const vector<vector<int>> dr = {{2, 2, 1, 1, -1, -1, -2, -2}, {1, 1, -1, -1}},
                          dc = {{1, -1, 2, -2, 2, -2, 1, -1}, {1, -1, 1, -1}};

int nya(queue<tuple<int, int, bool, int>> que) {
  while(!que.empty()) {
    int r, c, cnt; bool is_bishop; tie(r, c, is_bishop, cnt) = que.front(); que.pop();
    if(seen[is_bishop][r][c]) { continue; }
    seen[is_bishop][r][c] = true;
    if(r == gr && c == gc) { return cnt; }
    for(int i=0, n=dr[is_bishop].size(); i<n; ++i) {
      int nr = r + dr[is_bishop][i],
          nc = c + dc[is_bishop][i];
      if(nr < 0 || R <= nr || nc < 0 || C <= nc) { continue; }
      que.emplace(nr, nc, is_bishop^G[nr][nc]=='R', cnt+1);
    }
  }
  return inf;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> R >> C;
  G.assign(R, "");
  for(int r=0; r<R; ++r) { cin >> G[r]; }
  int sr, sc;
  for(int r=0; r<R; ++r) {
    for(int c=0; c<C; ++c) {
      if(G[r][c] == 'S') { sr = r; sc = c; }
      if(G[r][c] == 'G') { gr = r; gc = c; }
    }
  }
  seen.assign(2, vector<vector<bool>>(R, vector<bool>(C, false)));
  queue<tuple<int, int, bool, int>> que;
  que.emplace(sr, sc, false, 0);
  int res = nya(que);
  if(res == inf) { res = -1; }
  cout << res << '\n';
  return 0;
}
0