题意：黑白图像的路径表示法
代码：（Accepted，0.120s）
//UVa806 - Spatial Structures //Accepted 0.120s //#define _XIENAOBAN_ #include<algorithm> #include<iostream> #include<string> #include<vector> #include<cmath> 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() { #ifdef _XIENAOBAN_ #define gets(T) gets_s(T, 129) freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif 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。。。刚刚网上看了看好像思路也差不多。啊不管了，其实好久之前写的了，只是忘记发博客里了，我也有点忘了我怎么写的（记得当时写的时候有点昏昏沉沉）。 唉感觉自己越来越懒了，分析也不高兴写了。
转载于:https://www.cnblogs.com/xienaoban/p/6798067.html
相关资源：算法入门经典全篇