本文主要是介绍UVA 297 Quadtrees 好像不是很难。又好像不是很简单,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
UVA 297 Quadtrees
题目的意思挺好理解的,输入两颗四叉树,按照p为不空不满,f为满,e为空,按照先序输入, 把两颗四叉树合并起来,计算出新树的值。。
思路:首先把2个字符串处理,变成2个二维数组存放,然后在通过二维数组,就能查找到每个位置的结点相加之后的结果,要注意,如果四叉树4个分叉都为f,那么处理为结点为f,结点之后全部删除。
代码
#include <stdio.h>
#include <string.h>
#include <math.h>int t;
char a[1366];
char b[1366];
int num;
int lena, lenb, lenc;
int l;
int la, lc;
char aa[6][1111];
char bb[6][1111];
char cc[6][1111];void tra(char *a, char aa[][1111], int len, int x, int n, int m)
{if (la == len){return;}if (n % 4 == 0 && a[la - 1] != 'p' && la != 0){tra(a, aa, len, x - 1, n / 4, m / 4);}if (a[la] == 'p'){aa[x][n] = a[la];la ++;tra(a, aa, len, x + 1, n * 4, m * 4);}if (a[la] == 'f'){aa[x][n] = a[la];la ++;tra(a, aa, len, x, n + 1 , m + 1);}if (a[la] == 'e'){aa[x][n] = a[la];la ++;tra(a, aa, len, x, n + 1, m + 1);}
}int main()
{scanf("%d", &t);getchar();while (t --){l = 0;num = 0;memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));memset(cc, 0, sizeof(cc));memset(aa, 0, sizeof(aa));memset(bb, 0, sizeof(bb));gets(a);gets(b);lena = strlen(a);lenb = strlen(b);la = 0;tra(a, aa, lena, 0, 0, 0);la = 0;tra(b, bb, lenb, 0, 0, 0);for (int i = 5; i >= 0; i --)for (int j = 0; j < pow(4, i); j ++){if (i != 5){if (cc[i + 1][j * 4] == 'f' && cc[i + 1][j * 4 + 1] == 'f' && cc[i + 1][j * 4 + 2] == 'f' && cc[i + 1][j * 4+ 3] == 'f'){cc[i][j] = 'f';cc[i + 1][j * 4] = cc[i + 1][j * 4 + 1] = cc[i + 1][j * 4 + 2] = cc[i + 1][j * 4 + 3] = '\0';continue;}}if (aa[i][j] == 'f' || bb[i][j] == 'f'){cc[i][j] = 'f';cc[i + 1][j * 4] = cc[i + 1][j * 4 + 1] = cc[i + 1][j * 4 + 2] = cc[i + 1][j * 4 + 3] = '\0';continue;}if (aa[i][j] == 'e'){cc[i][j] = bb[i][j];continue;}if (bb[i][j] == 'e'){cc[i][j] = aa[i][j];continue;}if (aa[i][j] == 'p' && bb[i][j] == 'p'){cc[i][j] = 'p';continue;}if (aa[i][j] == '\0' && bb[i][j] != '\0'){cc[i][j] = bb[i][j];continue;}if (aa[i][j] != '\0' && bb[i][j] == '\0'){cc[i][j] = aa[i][j];continue;}}for (int i = 5; i >= 0; i --)for (int j = 0; j < pow(4, i); j ++){if (cc[i][j] == 'f')num += (1024 / pow(4, i));}printf("There are %d black pixels.\n", num);}return 0;
}
这篇关于UVA 297 Quadtrees 好像不是很难。又好像不是很简单的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!