Posted in BFS, Kuangbin

POJ 3278/ kuangbin 1C

10/13/2017
Problem: http://poj.org/problem?id=3278
Solution: For every element x in the queue, add in x-1. x+1, x*2.


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

bool v[100005];

bool inrange(int x) {
	return (x >= 0) && (x <= 100000); 
}

struct node{
	int t;
	int x;
	node(int tt, int xx) {
		t = tt;
		x = xx;
	}
};

int main() {
	int n, k;
	cin >> n >> k;
	queue<node> q;
	q.push(node(0, n));
	v[n] = true;
	while(!q.empty()) {
		node curr = q.front();
		q.pop();
		if (curr.x == k) {
			cout << curr.t;
			return 0;
		}
		if (inrange(curr.x - 1) && !v[curr.x - 1]) {
			q.push(node(curr.t + 1, curr.x - 1));
			v[curr.x - 1] = true;
		} 
		if (inrange(curr.x + 1) && !v[curr.x + 1]) {
			q.push(node(curr.t + 1, curr.x + 1));
			v[curr.x + 1] = true;
		}
		if (inrange(curr.x * 2) && !v[curr.x * 2]) {
			q.push(node(curr.t + 1, curr.x * 2));
			v[curr.x * 2] = true;
		}
	}
	return 0;
} 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s