题意：黑白图像的路径表示法
代码：（Accepted，0.120s） 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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147//UVa806 - Spatial Structures
//Accepted 0.120s
//#define _XIENAOBAN_
using namespace std;
int N, T(0);
bool Img[66][66];
vector<string> Sqns;
const unsigned C5_10(const string& five) {//五进制转十进制
unsigned ans(0), i(1);
for (auto p(five.rbegin());p != five.rend();++p, i *= 5)
ans += (*p - 48) * i;
return ans;
}
const string C10_5(unsigned ten) {//十进制转五进制(倒序)
string ans;
do ans += char(ten % 5 + 48);
while (ten /= 5);
return ans;
}
bool DFS(int x, int y, string f) {
int len = N / (int)pow(2, f.length()) / 2;
if (!len) {
if (Img[x][y]) {
Sqns.push_back(f);
//cerr << "Debug: Sqns(" << x << ", " << y << ") " << f << endl;//Debug
}
return Img[x][y];
}
bool NW(DFS(x, y, '1' + f));
bool NE(DFS(x, y + len, '2' + f));
bool SW(DFS(x + len, y, '3' + f));
bool SE(DFS(x + len, y + len, '4' + f));
bool flag(NW&&NE&&SW&&SE);
if (flag) {
Sqns.pop_back(), Sqns.pop_back(), Sqns.pop_back(), Sqns.pop_back();
Sqns.push_back(f);
}
return flag;
}
void Initialize() {
Sqns.clear();
for (int i(0);i < N;++i) for (int j(0);j <= N;++j)
Img[i][j] = false;
}
void SolvePlus() {
Initialize();
//Input
char n;
for (int i(0);i < N;++i) for (int j(0);j < N;++j)
cin >> n, Img[i][j] = n - 48;
//Solve
DFS(0, 0, "");
//Output
if (Sqns.size()) {
sort(Sqns.begin(), Sqns.end(), [](string& a, string& b)->bool {
if (a.length() != b.length()) return a.length() < b.length();
return a < b;
});
auto p(Sqns.begin());
int cnt(0);
while (p != Sqns.end()) {
if (cnt == 12) cnt = 0, cout << '\n';
if (cnt++) cout << ' ' << C5_10(*p);
else cout << C5_10(*p);
++p;
}
cout << '\n';
}
cout << "Total number of black nodes = " << Sqns.size() << '\n';
}
void SolveMinus() {
N = -N;
Initialize();
//Input
unsigned n;
while (cin >> n && n != -1)
Sqns.push_back(C10_5(n));
//Solve
if (Sqns.empty());
else if (Sqns[0] == "0") {
for (int i(0);i < N;++i) for (int j(0);j < N;++j)
Img[i][j] = true;
}
else {
for (const auto& t : Sqns) {
//cerr <<"Debug1: "<< t << endl;//
int x(0), y(0), len(N);
for (const auto& c : t) {
len /= 2;
switch (c)
{
case '1': break;
case '2': y += len;break;
case '3': x += len;break;
case '4': x += len;y += len;break;
default:break;
}
}
//cerr << "Debug2: ("<<x << ", " << y <<") "<<len<< endl;//
for (int i(0);i < len;++i)
for (int j(0);j < len;++j)
Img[x + i][y + j] = true;
}
}
//Output
for (int i(0);i < N;++i) {
for (int j(0);j < N;++j)
cout << (Img[i][j] ? '*' : '.');
cout << '\n';
}
}
int main()
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
std::ios::sync_with_stdio(false);
while (cin >> N && N) {
if (T) cout << '\n';
cout << "Image " << ++T << '\n';
if (N > 0) SolvePlus();
else SolveMinus();
}
return 0;
}
分析：用的DFS来递归来着，题目倒是不难，直接跟着题意霸王硬上弓就行。但是大神们用10、20ms，我用了120ms。。。刚刚网上看了看好像思路也差不多。啊不管了，其实好久之前写的了，只是忘记发博客里了，我也有点忘了我怎么写的（记得当时写的时候有点昏昏沉沉）。 唉感觉自己越来越懒了，分析也不高兴写了。