problem-solving/puzzleGame.cpp at master · yachShekhar/problem-solving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
template<class T> T smaller( T a, T b ){return ( a < b ? a : b );}
//Convert int to string

const bool isPrime[18] = {0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1};

map<LL,bool> vp;
const int N = 3;
bool isFound = false;

LL toNum(vector<vector<int> > vvi){
	long long ans = 0;
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			ans = ans*10 + vvi[i][j];
    return ans;
}
// vector<vector<int> > of(vector<vector<int> > &vvi){
// 	vector<vector<int> > v(3, vector<int>(3));
// 	v[0][0] = vvi[0][0]; v[0][1] = vvi[0][1]; v[0][2] = vvi[0][2];
// 	v[1][0] = vvi[1][0]; v[1][1] = vvi[1][1]; v[1][2] = vvi[1][2];
// 	v[2][0] = vvi[2][0]; v[2][1] = vvi[2][1]; v[2][2] = vvi[2][2];
// 	return v;
// }

map<LL, int> mp;

void sol(vector<vector<int> > vvii){
	queue<vector<vector<int> > > q;
	q.push(vvii);
	while(!q.empty()){
		vector<vector<int> > vvi = q.front();
		q.pop();
		LL tn = toNum(vvi);
		if(vp[tn]){
			continue;
		}else{
			vp[tn] = true;
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					if(i + 1 < N && isPrime[vvi[i][j] + vvi[i + 1][j]]){
						//vector<vector<int> > tv = of(vvi);
						// int tmp = tv[i][j];
						// tv[i][j] = tv[i + 1][j];
						// tv[i + 1][j] = tmp;
						swap(vvi[i][j], vvi[i+1][j]);
						LL tnv = toNum(vvi);
						if(mp.find(tnv) == mp.end()){
							mp[tnv] = 1 + mp[tn];
							q.push(vvi);
						}
						swap(vvi[i][j], vvi[i+1][j]);
					}
					if(j + 1 < N && isPrime[vvi[i][j] + vvi[i][j + 1]]){
						swap(vvi[i][j], vvi[i][j+1]);
						LL tnv = toNum(vvi);
						if(mp.find(tnv) == mp.end()){
							mp[tnv] = 1 + mp[tn];
							q.push(vvi);
						}
						swap(vvi[i][j], vvi[i][j+1]);
					}
				}
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	vector<vector<int> > vvi(3, vector<int>(3));
	//int start_s=clock();
	vector<vector<int> > v(3, vector<int>(3));
	int counter = 0;
	for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				v[i][j] = ++counter;
			}
	}
	sol(v);
	while(t--){
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				cin>>vvi[i][j];
			}
		}
		LL s = toNum(vvi);
		if(vp[s]){
			cout<<mp[s]<<endl;
		}else{
			cout<<-1<<endl;
		}
	}

	//int stop_s=clock();
	//cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
	return 0;
}