[C++]白準17391号:無限加速

11327 ワード
白駿 幅優先ナビゲーション テキストリンク

質問リンク


17391号：無限加速

問題の概要


地図上の各グリッドにはアシストが存在し、各グリッドが止まるとアシストが得られます.各セクションでブースターを取得した後、所有するブースターの数まで右または下に移動できます.しかし、一方の方向に移動すると、他方の方向は選択できず、ブースターを使用して停止すると、元のブースターは消えてしまいます.
(N,M)号車に到達するためには、ブースター使用回数の最高値を求める必要がある.

方法


これは簡単なBFS問題である.
下と右に移動するBFSを実施するだけです.
1から現在のブースターの数まで、for文を回転させて増やし、方向を指す変数に現在の位置を乗算し、再アクセスまたは範囲を確認してキューに入れます.
これは簡単な問題で、状態が悪すぎて問題をよく読んでいないし、右と下だけ移動する条件を見ていないので、一度間違えました.定期的に問題を慎重に読むことを意識すると思います.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

const int MAX = 301;
int n, m, mp[MAX][MAX], dir[2][2] = { {0, 1}, {1, 0} };
bool visited[MAX][MAX];

struct Data {
	int r, c, d;
};

int	main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> mp[i][j];

	queue<Data> q;
	q.push({ 1, 1, 0 });

	while (!q.empty()) {
		auto now = q.front();
		q.pop();

		if (now.r == n && now.c == m) {
			cout << now.d << '\n';
			return 0;
		}

		int booster = mp[now.r][now.c];

		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= booster; j++) {
				int nr = now.r + dir[i][0] * j;
				int nc = now.c + dir[i][1] * j;
				
				if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && !visited[nr][nc]) {
					visited[nr][nc] = true;
					q.push({ nr, nc, now.d + 1 });
				}
			}
		}
	}
}
JAva学習ノート-クラスMyInputStreamを実現(28)
[JS]構成部品(symbol)の役割は何ですか?