結果

問題 No.367 ナイトの転身
ユーザー pekempey
提出日時 2016-04-29 22:47:22
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 1,153 bytes
コンパイル時間 1,242 ms
コンパイル使用メモリ 171,892 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-10-04 18:24:24
合計ジャッジ時間 2,129 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:49:27: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |         if (dist[gy][gx][1] == -1) dist[gy][gx][1] = 1e9;
      |             ~~~~~~~~~~~~~~^
main.cpp:49:27: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized]

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

string g[500];
int dist[500][500][2];

vector<int> dy[2] = {
	{1, 2, 2, 1, -1, -2, -2, -1},
	{1, 1, -1, -1},
};

vector<int> dx[2] = {
	{2, 1, -1, -2, -2, -1, 1, 2},
	{1, -1, -1, 1},
};

int main() {
	int h, w;
	int sy, sx, gy, gx;
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		cin >> g[i];
		for (int j = 0; j < w; j++) {
			if (g[i][j] == 'S') sy = i, sx = j;
			if (g[i][j] == 'G') gy = i, gx = j;
		}
	}
	memset(dist, -1, sizeof(dist));
	dist[sy][sx][0] = 0;

	queue<tuple<int, int, int>> q;
	q.emplace(sy, sx, 0);
	while (!q.empty()) {
		int y, x, t;
		tie(y, x, t) = q.front(); q.pop();

		for (int k = 0; k < dy[t].size(); k++) {
			int ny = y + dy[t][k];
			int nx = x + dx[t][k];
			if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
			int nt = g[ny][nx] == 'R' ? !t : t;
			if (dist[ny][nx][nt] != -1) continue;
			dist[ny][nx][nt] = dist[y][x][t] + 1;
			q.emplace(ny, nx, nt);
		}
	}

	if (dist[gy][gx][0] == -1) dist[gy][gx][0] = 1e9;
	if (dist[gy][gx][1] == -1) dist[gy][gx][1] = 1e9;
	int ans = min(dist[gy][gx][0], dist[gy][gx][1]);
	if (ans == 1e9) ans = -1;
	cout << ans << endl;
}
0