結果

問題 No.367 ナイトの転身
ユーザー nona_cat_puyonona_cat_puyo
提出日時 2016-05-31 11:53:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 2,288 bytes
コンパイル時間 674 ms
コンパイル使用メモリ 72,272 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-04-16 19:13:40
合計ジャッジ時間 1,628 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,632 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 27 ms
5,632 KB
testcase_11 AC 34 ms
5,760 KB
testcase_12 AC 10 ms
5,376 KB
testcase_13 AC 9 ms
5,376 KB
testcase_14 AC 17 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 16 ms
5,376 KB
testcase_17 AC 4 ms
5,376 KB
testcase_18 AC 5 ms
5,376 KB
testcase_19 AC 5 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 6 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <queue>

using namespace std;

typedef pair<int, int> P;
typedef pair<P, char> state;


int kx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int ky[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int bx[4] = { 1, 1, -1, -1 };
int by[4] = { 1, -1, -1, 1 };

char s[500][501];
int dn[500][500];
int db[500][500];

int main() {

	pair<int, int> start, goal;

	int H, W;
	cin >> H >> W;

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> s[i][j];
			if (s[i][j] == 'S') {
				start = P(i, j);
				s[i][j] = '.';
			}
			if (s[i][j] == 'G') {
				goal = P(i, j);
				s[i][j] = '.';
			}
		}
	}

	queue<state> que;

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			dn[i][j] = -1;
			db[i][j] = -1;
		}
	}
	que.push(state(start, 'N'));
	dn[start.first][start.second] = 0;

	while (que.size() != 0) {
		state s1 = que.front();  que.pop();
		
		if (s1.first.first == goal.first && s1.first.second == goal.second) break;

		if (s1.second == 'N') {
			for (int i = 0; i < 8; i++) {
				int nx = s1.first.first + kx[i], ny = s1.first.second + ky[i];

				if (0 <= nx && nx < H && 0 <= ny && ny < W) {
					if (s[nx][ny] == 'R') {
						if (db[nx][ny] == -1) {
							que.push(state(P(nx, ny), 'B'));
							db[nx][ny] = dn[s1.first.first][s1.first.second] + 1;
						}
					}
					else {
						if (dn[nx][ny] == -1) {
							que.push(state(P(nx, ny), 'N'));
							dn[nx][ny] = dn[s1.first.first][s1.first.second] + 1;
						}
					}
				}
			}
		} else {
			for (int i = 0; i < 4; i++) {
				int nx = s1.first.first + bx[i], ny = s1.first.second + by[i];

				if (0 <= nx && nx < H && 0 <= ny && ny < W) {
					if (s[nx][ny] == 'R') {
						if (dn[nx][ny] == -1) {
							que.push(state(P(nx, ny), 'N'));
							dn[nx][ny] = db[s1.first.first][s1.first.second] + 1;
						}
					}
					else {
						if (db[nx][ny] == -1) {
							que.push(state(P(nx, ny), 'B'));
							db[nx][ny] = db[s1.first.first][s1.first.second] + 1;
						}
					}
				}
			}
		}
	}
	if (db[goal.first][goal.second] != -1 && dn[goal.first][goal.second] != -1) {
		cout << min(db[goal.first][goal.second], dn[goal.first][goal.second]);
	}
	else {
		cout << max(db[goal.first][goal.second], dn[goal.first][goal.second]);
	}

	getchar();
	getchar();

	return 0;
}
0