結果

問題 No.367 ナイトの転身
ユーザー TwizzTwizz
提出日時 2017-06-01 20:56:50
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 82 ms / 2,000 ms
コード長 1,964 bytes
コンパイル時間 1,808 ms
コンパイル使用メモリ 169,256 KB
実行使用メモリ 6,240 KB
最終ジャッジ日時 2023-10-21 20:17:05
合計ジャッジ時間 3,035 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,644 KB
testcase_01 AC 3 ms
5,640 KB
testcase_02 AC 3 ms
5,640 KB
testcase_03 AC 3 ms
5,644 KB
testcase_04 AC 3 ms
5,644 KB
testcase_05 AC 3 ms
5,640 KB
testcase_06 AC 3 ms
5,640 KB
testcase_07 AC 3 ms
5,640 KB
testcase_08 AC 3 ms
5,640 KB
testcase_09 AC 3 ms
5,640 KB
testcase_10 AC 47 ms
6,188 KB
testcase_11 AC 82 ms
6,240 KB
testcase_12 AC 10 ms
5,864 KB
testcase_13 AC 12 ms
5,860 KB
testcase_14 AC 26 ms
5,872 KB
testcase_15 AC 4 ms
5,656 KB
testcase_16 AC 27 ms
5,800 KB
testcase_17 AC 6 ms
5,696 KB
testcase_18 AC 8 ms
5,700 KB
testcase_19 AC 7 ms
5,740 KB
testcase_20 AC 3 ms
5,696 KB
testcase_21 AC 8 ms
5,720 KB
testcase_22 AC 3 ms
5,660 KB
testcase_23 AC 3 ms
5,664 KB
testcase_24 AC 3 ms
5,664 KB
testcase_25 AC 4 ms
5,664 KB
testcase_26 AC 3 ms
5,660 KB
権限があれば一括ダウンロードができます

ソースコード

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