結果

問題 No.367 ナイトの転身
ユーザー めうめう🎒めうめう🎒
提出日時 2016-04-29 23:13:32
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 1,881 bytes
コンパイル時間 788 ms
コンパイル使用メモリ 81,296 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-04 18:49:43
合計ジャッジ時間 1,988 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:51:35: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |                 if(nx == gx && ny == gy){
      |                                ~~~^~~~~
main.cpp:51:23: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |                 if(nx == gx && ny == gy){
      |                    ~~~^~~~~

ソースコード

diff # 

#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