forked from oeddyo/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathclocks2.cpp
More file actions
108 lines (94 loc) · 1.87 KB
/
clocks2.cpp
File metadata and controls
108 lines (94 loc) · 1.87 KB
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
104
105
106
107
/*
ID: xieke.b1
PROG: clocks
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
ofstream fout("clocks.out");
ifstream fin ("clocks.in");
//int s[9];
vector<int> start;
vector<int> final;
const int MAXN = 1200000;
int vis[MAXN];
string dir[10]={
"",
"ABDE",
"ABC",
"BCEF",
"ADG",
"BDEFH",
"CFI",
"DEGH",
"GHI",
"EFHI"
};
int szs[10] = {
0,
4,3,4,3,5,3,4,3,4};
int compute(vector<int> &s){
int res = 0;
for(int i=0; i<9; i++){
res = res*4+s[i];
}
return res;
}
void print(vector<int> s){
for(int i=0; i<s.size(); i++){
cout<<s[i]<<" ";
}
cout<<endl;
}
typedef pair< vector<int> , string> mp;
void bfs(vector<int> s){
int tmp = compute(s);
vis[tmp] = 1;
queue<pair< vector<int> , string> > Q;
mp ns;
Q.push( mp(s, "") );
while(!Q.empty()){
ns = Q.front();
Q.pop();
if(ns.first==final){
cout<<ns.second<<endl;
for(int i=0; i<ns.second.size()-1; i++){
fout<<ns.second[i]<<" ";
}fout<<ns.second[ns.second.size()-1]<<endl;
return ;
}
for(int i=1; i<=9; i++){
int sz = szs[i];
vector<int> t= ns.first;
for(int j=0; j<sz; j++){
int pos = dir[i][j]-'A';
t[pos]+=1;
if(t[pos]==4)t[pos]=0;
}
int state = compute(t);
if( vis[state]==0){
Q.push( mp(t, ns.second+char('0'+i)) );
vis[state] = 1;
}
}
}
}
void work(){
bfs(start);
}
int main(){
for(int i=0; i<9; i++){
int t;
fin>>t;
start.push_back((t/3)%4);
final.push_back(0);
//fin>>s[i];
}
work();
return 0;
}