/
10051.cpp
65 lines (57 loc) · 1.63 KB
/
10051.cpp
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
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
/*
* The basic idea of this solution is to use the n^2 solution
* to the lis problem, but maintain the several different faces
* of each cube.
*/
using namespace std;
int lis[500][6], back[500][6][2], cubes[500][6], n;
string sides[6] = { "front", "back", "left", "right", "top", "bottom" };
int main() {
int tc = 1;
while (cin >> n and n != 0) {
if (tc > 1) cout << endl;
for (int i = 0; i < n; i++) {
for (int f = 0; f < 6; f++) {
cin >> cubes[i][f];
lis[i][f] = 1;
back[i][f][0] = i; back[i][f][1] = 0;
}
}
int m = 1, ei = 0, ef = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int fi = 0; fi < 6; fi++) for (int fj = 0; fj < 6; fj++) {
int op = (fj % 2) ? fj - 1 : fj + 1;
if (cubes[i][fi] == cubes[j][op] and lis[i][fi] < lis[j][fj] + 1) {
lis[i][fi] = lis[j][fj] + 1;
back[i][fi][0] = j;
back[i][fi][1] = fj;
if (lis[i][fi] > m) {
m = lis[i][fi];
ei = i; ef = fi;
}
}
}
}
}
vector<string> ans;
while (back[ei][ef][0] != ei) {
int oei = ei;
stringstream s;
s << ei+1 << ' ' << sides[ef];
ans.push_back(s.str());
ei = back[ei][ef][0], ef = back[oei][ef][1];
}
stringstream s;
s << ei+1 << ' ' << sides[ef];
ans.push_back(s.str());
cout << "Case #" << tc++ << endl << ans.size() << endl;
for(int i = ans.size()-1; i >= 0; i--)
cout << ans[i] << endl;
}
}