[BOJ] 13549. かくれんぼをする

1851 ワード
BFS テキストリンク
かくれんぼをする
区分アルゴリズム:BFS
質問する
秀斌は弟と隠れん坊をしている.秀彬は現在点N(0≦N≦100000)、弟は点K(0≦K≦100000)にいる.スビンは歩いたり瞬時に移動したりすることができます秀彬の位置がXであれば、1秒後にX-1またはX+1に移動します.瞬間移動であれば、0秒後には2*Xの位置に移動します.
もし秀彬と弟の位置があれば、秀彬が弟を探す最も速い時間は数秒後であることを求めるプログラムを書きます.
入力
一行目はスビンのポジションNと弟のポジションKNとKは整数です.
しゅつりょく
秀彬が弟を探している一番速い時間を印刷します.
入力例1
5 17
サンプル出力1
2
問題を解く
最初はDFSに再帰的にアクセスすることを望んでいたが,明確な終了条件を設定することが困難であったため,この方式は利用できないと考えた.
そこでBFSを用いて実現していきましょう.Queueを作成した後、ある場所に到達した時間が更新可能である場合、更新を続行し、その場所をQueueにプッシュして、その場所から別の場所に移動するのに要する時間を更新することができます.
ソースコード
#include <bits/stdc++.h>

using namespace std;

int n, k;
int visited[100001];
void bfs(int start);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	
	fill(visited, visited + sizeof(visited)/sizeof(int), 987654321);
	
	bfs(n);
	
	cout << visited[k] << endl;
	
	return 0;
}

void bfs(int start) {
	int now, move, temp;
	int dir[] = {-1, 1, 2};
	queue<int> q;
	
	q.push(start);
	visited[start] = 0;
	while(!q.empty()) {
		now = q.front();
		q.pop();
		
		for(int i = 0; i < 3; i++) {
			if(i == 2) {
				move = now * dir[i];
				temp = visited[now];
			}
			else {
				move = now + dir[i];
				temp = visited[now] + 1;
			}
			
			if(0 > move || move > 100000) {
				continue;
			}
			
			if(visited[move] > temp) {
				visited[move] = temp;
				q.push(move);
			}
		}
	}
}
  • 題出所:https://www.acmicpc.net/problem/135492
  • カイドウ草が白駿で「そうだ!!」判定を受けた
    • [JAVA/1292号]クイズしやすい*
    [BOJ] 2437. 秤.