[伯俊]13549号かくれんぼをする

2341 ワード
BFS 白駿 ps テキストリンク

[伯俊]13549号给我


1.質問


秀斌は弟と隠れん坊をしている.秀彬は現在点N(0≦N≦100000)、弟は点K(0≦K≦100000)にいる.スビンは歩いたり瞬時に移動したりすることができます秀彬の位置がXであれば、1秒後にX-1またはX+1に移動します.瞬間移動であれば、0秒後には2*Xの位置に移動します.
もし秀彬と弟の位置があれば、秀彬が弟を探す最も速い時間は数秒後であることを求めるプログラムを書きます.

2.入力


一行目はスビンのポジションNと弟のポジションKNとKは整数です.

3.出力


秀彬が弟を探している一番速い時間を印刷します.

4.解答

  • 2[伯俊]1697号かくれんぼをする題に似ています.
  • しかなく、違いは瞬間移動で時間を消費しないことです.
  • の瞬間移動は最短時間なので、常に最初に瞬間移動を行います.
    • 残りのコード
  • は1697번. 숨바꼭질コードを使用している.
    • しかし、
  • を解く際には、1697번配列を別途作成するのではなく、配列の値が0であるか否かを判断していたが、今回は時間が0の場合があったので、visited配列を別途作成した.

    • 5.最初のコードと異なる点

  • 2visitedまで並び、visitedおよびnx2には適用されません.nx3

    • 6.コード

    #include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int arr[100001] = { 0, };
bool visited[100001];

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int start, target;
	cin >> start >> target;

	queue<int> q;
	if (start != target) q.push(start);

	while (!q.empty()) {
		int x = q.front();
		if (x == target) break;
		q.front();
		q.pop();
		int nx1 = x * 2;
		int nx2 = x - 1;
		int nx3 = x + 1;
		if (nx1 <= 100000 && !visited[nx1]) {
			q.push(nx1);
			visited[nx1] = true;
			arr[nx1] = arr[x];
		}
		if (nx2 >= 0 && !visited[nx2]) {
			q.push(nx2);
			visited[nx2] = true;
			arr[nx2] = arr[x] + 1;
		}
		if (nx3 <= 100000 && !visited[nx3]) {
			q.push(nx3);
			visited[nx3] = true;
			arr[nx3] = arr[x] + 1;
		}
	}
	cout << arr[target];

}
    [伯俊]11047硬貨0
    【資料整理】scribeインストール構成