UVA – 10067 – Playing with Wheels

  • Problem Statement : UVA – 10067 – Playing With Wheels
  • Notes to Take
    • The input can give you the start combination equal to the end combination to take care of your implementation to handle this and return 0.
    • when there is no path return -1

[sorcecode language=”cpp” wraplines=”false”]

#include <iostream>
#include <queue>
#include <string.h>
#include <fstream>
using namespace std;
struct Combination{
	int w, d[4];
	Combination(){ w=0; cin >> d[3] >> d[2] >> d[1] >> d[0]; }
	Combination(int a[4], int W) { w=W; for(int i=0; i<4; i++) d[i]=a[i]; }

	Combination turn(int index, int dir){
		int*a = new int[4];
		for(int i=0; i<4; i++)	a[i] = i==index ? (d[i] + 1 + 8*dir)%10 : d[i];
		return Combination(a, w+1);
	}
	int value(){
		int v=0;
		for(int i=0; i<4; i++)
			v = 10*v + d[i];
		return v;
	}

	bool equals(Combination &o){
		bool res = (d[3]==o.d[3]) && (d[2]==o.d[2]) && d[1]==o.d[1] && d[0]==o.d[0];
		if(res) o.w = w;
		return res;
	}
};
int main() {
	int T, F;

	cin>> T;
	while(T--){

		bool forbidden[10001];
		memset(forbidden, 0, sizeof forbidden);
		queue<Combination> que;
		Combination start, end;
		que.push(start);
		cin >> F;

		while(F--){ Combination f;	forbidden[f.value()]=true; }

		while(que.size()){
			Combination c = que.front(); que.pop();
			if(c.equals(end))	break;

			if(forbidden[c.value()]) continue;
			forbidden[c.value()]=true;

			for(int i=0; i<4; i++){
				que.push(c.turn(i, 0));
				que.push(c.turn(i, 1));
			}
		}
		cout <<  (end.w || end.equals(start) ? end.w : -1) << endl;
	}
	return 0;
}

[/sourcecode]

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: