UVa 10067 - Playing with Wheels

// UVa 10067 - Playing with Wheels

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

struct config {
	int a, b, c, d;
	int m;
};

int sol;
queue<config> q;
config t;
bool T[10][10][10][10];

bool operator ==(config x, config y) {
	return x.a == y.a && x.b == y.b && x.c == y.c && x.d == y.d;
}

bool move(int a, int b, int c, int d, int m) {
	if (!T[(a + 1) % 10][b][c][d]) {
		config conf = { (a + 1) % 10, b, c, d, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	if (!T[a][(b + 1) % 10][c][d]) {
		config conf = { a, (b + 1) % 10, c, d, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	if (!T[a][b][(c + 1) % 10][d]) {
		config conf = { a, b, (c + 1) % 10, d, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	if (!T[a][b][c][(d + 1) % 10]) {
		config conf = { a, b, c, (d + 1) % 10, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	if (!T[(a + 9) % 10][b][c][d]) {
		config conf = { (a + 9) % 10, b, c, d, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	if (!T[a][(b + 9) % 10][c][d]) {
		config conf = { a, (b + 9) % 10, c, d, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	if (!T[a][b][(c + 9) % 10][d]) {
		config conf = { a, b, (c + 9) % 10, d, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	if (!T[a][b][c][(d + 9) % 10]) {
		config conf = { a, b, c, (d + 9) % 10, m + 1 };
		q.push(conf);
		T[conf.a][conf.b][conf.c][conf.d] = true;
		if (conf == t) {
			sol = conf.m;
			return true;
		}
	}
	return false;
}

int main() {
	int tt;
	for (cin >> tt; tt; tt--) {
		config s;
		cin >> s.a >> s.b >> s.c >> s.d;
		cin >> t.a >> t.b >> t.c >> t.d;
		int n;
		memset(T, false, sizeof(T));
		cin >> n;
		for (int i = 0; i < n; i++) {
			config f;
			cin >> f.a >> f.b >> f.c >> f.d;
			T[f.a][f.b][f.c][f.d] = true;
		}
		if (s == t)
			cout << 0 << endl;
		else {
			sol = -1;
			while (!q.empty())
				q.pop();
			s.m = 0;
			q.push(s);
			T[s.a][s.b][s.c][s.d] = true;
			while (!q.empty()) {
				config now = q.front();
				q.pop();
				if (move(now.a, now.b, now.c, now.d, now.m))
					break;
			}
			cout << sol << endl;
		}
	}
	return 0;
}