結果

問題 No.367 ナイトの転身
コンテスト
ユーザー nona_cat_puyo
提出日時 2016-05-31 11:53:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 2,288 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 838 ms
コンパイル使用メモリ 72,064 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-10-07 20:12:26
合計ジャッジ時間 2,060 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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