Uva1103 Ancient Messages

Uva1103 Ancient Messages

题意：识别图中的象形文字。但是，图形可以任意的拉伸，但不能拉断。 分析：这种题如果图形没有特征是不可做类型的题，不过观察图形可以发现每个图形中的洞的数量是一定的，我们只需要数出每一个封闭图形的洞数就能知道这是哪个图形.       虽然知道了原理，但是并不是特别好做，首先我们需要一次dfs将所有图形旁边的点全都变为“不可访问”，然后从每个黑点开始枚举，向四周扩展，遇到白色的块就用第一次的dfs函数覆盖，否则继续第二次dfs,两次dfs交错使用，思路比较巧妙. #include #include #include #include using namespace std; //0表示空白位置,-1表示不能访问了. const int maxn = 510; int n, m,kase,a[maxn][maxn],flag[maxn][maxn],cnt,num[maxn]; char s16[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' }; char fuhao[6] = { 'A', 'D', 'J', 'K', 'S', 'W' }; int s2[16][4] = { { 0, 0, 0, 0 }, { 0, 0, 0, 1 }, { 0, 0, 1, 0 }, { 0, 0, 1, 1 }, { 0, 1, 0, 0 }, { 0, 1, 0, 1 }, { 0, 1, 1, 0 }, { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 1, 0, 0, 1 }, { 1, 0, 1, 0 }, { 1, 0, 1, 1 }, { 1, 1, 0, 0 }, { 1, 1, 0, 1 }, { 1, 1, 1, 0 }, { 1, 1, 1, 1 } }; void dfs1(int x,int y) { if (x < 0 || x > n + 1 || y < 0 || y > m + 1 || a[x][y] != 0) return; a[x][y] = -1; dfs1(x - 1, y); dfs1(x + 1, y); dfs1(x, y - 1); dfs1(x, y + 1); } void dfs2(int x, int y) { if (x < 0 || x > n + 1 || y < 0 || y > m + 1 || a[x][y] == -1) return; if (a[x][y] == 0) { cnt++; dfs1(x, y); return; } a[x][y] = -1; dfs2(x - 1, y); dfs2(x + 1, y); dfs2(x, y - 1); dfs2(x, y + 1); } int main() { while (scanf("%d%d", &n, &m) == 2 && (n || m)) { memset(a, 0, sizeof(a)); memset(num, 0, sizeof(num)); for (int i = 1; i <= n; i++) { getchar(); char ch; int tot = 0; for (int j = 1; j <= m; j++) { scanf("%c", &ch); for (int k = 0; k < 16; k++) { if (ch == s16[k]) { for (int l = 0; l < 4; l++) a[i][++tot] = s2[k][l]; break; } } } } m *= 4; dfs1(0, 0); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (a[i][j] == 1) { cnt = 0; dfs2(i, j); if (cnt == 0) num[5]++; if (cnt == 1) num[0]++; if (cnt == 2) num[3]++; if (cnt == 3) num[2]++; if (cnt == 4) num[4]++; if (cnt == 5) num[1]++; } printf("Case %d: ", ++kase); for (int i = 0; i <= 5; i++) { while (num[i]--) printf("%c", fuhao[i]); } printf("\n"); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。