結果

問題 No.367 ナイトの転身
コンテスト
ユーザー めうめう🎒
提出日時 2016-04-29 23:13:32
言語 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
結果
AC  
実行時間 55 ms / 2,000 ms
コード長 1,881 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 570 ms
コンパイル使用メモリ 106,428 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-20 12:38:40
合計ジャッジ時間 1,714 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:51:23: warning: 'gx' may be used uninitialized [-Wmaybe-uninitialized]
   51 |                 if(nx == gx && ny == gy){
      |                    ~~~^~~~~
main.cpp:24:23: note: 'gx' was declared here
   24 |         int h,w,sx,sy,gx,gy;
      |                       ^~
main.cpp:51:35: warning: 'gy' may be used uninitialized [-Wmaybe-uninitialized]
   51 |                 if(nx == gx && ny == gy){
      |                                ~~~^~~~~
main.cpp:24:26: note: 'gy' was declared here
   24 |         int h,w,sx,sy,gx,gy;
      |                          ^~
main.cpp:24:17: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
   24 |         int h,w,sx,sy,gx,gy;
      |                 ^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_algobase.h:64,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/algorithm:62,
                 from main.cpp:1:
In constructor 'constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U1 = int; _U2 = std::pair<int, std::pair<int, int> >; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = true; _T1 = bool; _T2 = std::pair<int, std::pair<int, int> >]',
    inlined from 'int main()' at main.cpp:44:20:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_pair.h:924:11: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
  924 |           second(std::forward<_U2>(__p.second))
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function 'int main()':
main.cpp:24:20: note: 'sy' was declared here
   24 |         int h,w,sx,sy,gx,gy;
      |                    ^~

ソースコード

diff #
raw source code 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

const int DIRX1[8] = {1,2,2,1,-1,-2,-2,-1};
const int DIRY1[8] = {2,1,-1,-2,-2,-1,1,2};
const int DIRX2[4] = {1,1,-1,-1};
const int DIRY2[4] = {-1,1,-1,1};

int main() {
	int h,w,sx,sy,gx,gy;
	char hyo[510][510];
	cin >> h >> w;
	for(int i = 0;i < h;i++){
		for(int j = 0;j < w;j++){
			cin >> hyo[j][i];
			if(hyo[j][i] == 'S'){
				sx = j;
				sy = i;
			}else if(hyo[j][i] == 'G'){
				gx = j;
				gy = i;
			}
		}
	}
	//0はナイト
	int ans = INF;
	bool flag = true;
	bool used[510][510][2] = {};
	queue<pair<bool,pair<int,pair<int,int> > > > que;
	que.push(make_pair(0,make_pair(0,make_pair(sx,sy))));
	while(que.size()){
		bool type = que.front().first;
		int how = que.front().second.first,nx = que.front().second.second.first,ny = que.front().second.second.second;
		que.pop();
		if(used[nx][ny][type]) continue;
		used[nx][ny][type] = true;
		if(nx == gx && ny == gy){
			cout << how << endl;
			flag = false;
			break;
		}
		if(type){
			for(int i = 0;i < 4;i++){
				int tx = nx + DIRX2[i],ty = ny + DIRY2[i];
				if(tx < 0 || tx >= w || ty < 0 || ty >= h) continue;
				if(hyo[tx][ty] == 'R') que.push(make_pair(0,make_pair(how + 1,make_pair(tx,ty))));
				else que.push(make_pair(1,make_pair(how + 1,make_pair(tx,ty))));
			}
		}else{
			for(int i = 0;i < 8;i++){
				int tx = nx + DIRX1[i],ty = ny + DIRY1[i];
				if(tx < 0 || tx >= w || ty < 0 || ty >= h) continue;
				if(hyo[tx][ty] == 'R') que.push(make_pair(1,make_pair(how + 1,make_pair(tx,ty))));
				else que.push(make_pair(0,make_pair(how + 1,make_pair(tx,ty))));
			}
		}
	}
	if(flag) cout << -1 << endl;
	return 0;
}
0