原题链接：https://vjudge.net/problem/UVA-806 分类：四分树 备注：DFS，水题
代码如下：
#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int maxn = 64; int n, g[maxn][maxn], id, kase; char Graph[maxn][maxn]; vector<int>path, ans; bool check(int x,int y,int size) { for (int i = x; i < x + size; i++) for (int j = y; j < y + size; j++) if (g[i][j] != g[x][y])return false; return true; } int reserve(int x) { int ret = 0; while (x) { ret = ret * 10 + x % 10; x /= 10; } return ret; } void solve(int x, int y, int size, int bef) { if (check(x, y, size / 2)) { if (g[x][y]) ans.push_back(reserve(bef * 10 + 1)); } else solve(x, y, size / 2, bef * 10 + 1); if (check(x, y + size / 2, size / 2)) { if (g[x][y + size / 2]) ans.push_back(reserve(bef * 10 + 2)); } else solve(x, y + size / 2, size / 2, bef * 10 + 2); if (check(x + size / 2, y, size / 2)) { if (g[x + size / 2][y]) ans.push_back(reserve(bef * 10 + 3)); } else solve(x + size / 2, y, size / 2, bef * 10 + 3); if (check(x + size / 2, y + size / 2, size / 2)) { if (g[x + size / 2][y + size / 2]) ans.push_back(reserve(bef * 10 + 4)); } else solve(x + size / 2, y + size / 2, size / 2, bef * 10 + 4); } void solve2() { for (int i = 0; i < path.size(); i++) { int size = n, x = 0, y = 0; while (path[i]) { int dir = path[i] % 5; path[i] /= 5; size /= 2; if (dir == 2) y += size; else if (dir == 3) x += size; else if (dir == 4) x += size, y += size; } for (int i = x; i < x + size; i++) for (int j = y; j < y + size; j++) Graph[i][j] = '*'; } } int read() { char ch = getchar(); while (ch == '\n' || ch == ' ')ch = getchar(); return ch - '0'; } int main(void) { while (~scanf("%d", &n) && n) { if (kase)printf("\n"); printf("Image %d\n", ++kase); if (n > 0) { ans.clear(); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) g[i][j] = read(); if (!check(0, 0, n))solve(0, 0, n, 0); else if (g[0][0])ans.push_back(0); sort(ans.begin(), ans.end()); for (int i = 0, num = 0; i < ans.size(); i++) { int out = 0, tmp = 1; while (ans[i]) { out += ans[i] % 10 * tmp; tmp *= 5; ans[i] /= 10; } if (num)printf(" "); printf("%d", out); num++; if (num == 12) { num = 0; printf("\n"); } } if (ans.size() % 12)printf("\n"); printf("Total number of black nodes = %d\n", ans.size()); } else { n = -n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) Graph[i][j] = '.'; path.clear(); while (1) { int x; scanf("%d", &x); if (x == -1)break; path.push_back(x); } solve2(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%c", Graph[i][j]); printf("\n"); } } } return 0; }