結果

問題 No.367 ナイトの転身
コンテスト
ユーザー Twizz
提出日時 2017-06-01 20:56:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 1,964 bytes
コンパイル時間 1,430 ms
コンパイル使用メモリ 167,652 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-09-21 21:42:09
合計ジャッジ時間 2,997 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"

//#include<bits/stdc++.h>
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
typedef long long ll;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
typedef vector<int> VE;
const ll mod = 100000000;

int h, w;
string s[502];
int dp[502][502][2] = {};
int kx[8] = { -2,-2,-1,-1,1,1,2,2 };
int ky[8] = { 1,-1,2,-2,2,-2,1,-1 };
int bx[4] = { -1,-1,1,1 };
int by[4] = { 1,-1,1,-1 };

int main() {
	cin >> h >> w;
	REP(i, h)cin >> s[i];
	memset(dp, -1, sizeof(dp));
	int sx = -1, sy = -1, gx = -1, gy = -1;
	REP(i, h)REP(j, w){
		if (s[i][j] == 'S') { sy = i; sx = j; } 
		if (s[i][j] == 'G') { gy = i; gx = j; }
	}
	dp[sy][sx][0] = 0;
	priority_queue<pair<int, pair<int, PI>>, vector<pair<int, pair<int, PI>>>, greater<pair<int, pair<int, PI>>>>que;
	auto st = make_pair(0,make_pair(sx, sy));
	que.push(make_pair(0,st));
	while (!que.empty()) {
		auto now = que.top();
		que.pop();
		int count = now.first;
		auto p = now.second;
		int type = p.first;
		auto v = p.second;
		int x = v.first;
		int y = v.second;
		count++;
		if (type== 0) {
			REP(i, 8) {
				if (y + ky[i] < 0 || x + kx[i] < 0 || x + kx[i] >= w || y + ky[i] >= h|| dp[y + ky[i]][x + kx[i]][0]>=0)continue;
				dp[y + ky[i]][x + kx[i]][0] = count;
				if (s[y + ky[i]][x + kx[i]] == 'R')type = 1;
				que.push(make_pair(count, make_pair(type,make_pair(x+kx[i],y+ky[i]))));
				type = 0;
			}
		}
		else if (type == 1) {
			REP(i, 4) {
				if (y + by[i] < 0 || x + bx[i] < 0 || x + bx[i] >= w || y + by[i] >= h|| dp[y + by[i]][x + bx[i]][1] >= 0)continue;
				dp[y + by[i]][x + bx[i]][1] = count;
				if (s[y + by[i]][x + bx[i]] == 'R')type = 0;
				que.push(make_pair(count, make_pair(type, make_pair(x + bx[i], y + by[i]))));
				type = 1;
			}
		}
		if (dp[gy][gx][0] >= 0|| dp[gy][gx][1] >= 0)break;
	}
	int ans = dp[gy][gx][0] == 0 ? dp[gy][gx][1] : dp[gy][gx][0];
	print(ans);
	return 0;
}
0