백준 1697 숨바꼭질

1006 단어 algorithm백준BFSBFS

백준 1697

#include <bits/stdc++.h>
using namespace std;
int n, k;
int dist[100001];
int dx[2] = { -1,1 };
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	queue<int>q;
	cin >> n >> k;
	fill(dist, dist + 100001, -1);
	dist[n] = 0;
	q.push(n);

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (cur == k) break;
		for (int i = 0; i < 3; i++) {
			if (i == 2) {
				int nx = cur * 2;
				if (nx < 0 || nx>100000) continue;
				if (dist[nx] < 0) {
					q.push(nx);
					dist[nx] = dist[cur]+1;
				}
			}
			else {
				int nx = cur + dx[i];
				if (nx < 0 || nx>100000) continue;
				if (dist[nx] < 0) {
					q.push(nx);
					dist[nx] = dist[cur]+1;
				}
			}
		}
	}
	cout << dist[k];
}

좋은 웹페이지 즐겨찾기