UVA-806 空间结构 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

一道遍历四叉树的题目，在遍历的同时还要记住路径，做一些额外的操作。题目本身并不难。但是格式要求较多，比如输出路径时12个就换行，不能出现多余的空格、换行等等。

我的方法是在通过图构建路径时，先递归到单个像素值，再一层一层的通过父级查看各个子级的颜色是否一致，不一致则子级的路径作为输出路径，一致则继续递归到上级处理。这样同一个像素只被计算一次。

这次我遇到一个非常隐蔽的问题，就是使用了一个int变量，作为一个char类型去读取：

int k;
scanf("%c", &k);

这样使用在我本地没有问题，我使用uDebug测试，所有数据都能通过，但是去OJ提交却WA。

如果把这个换成char类型，就没问题了：

char k;
scanf("%c", &k);

我在网上搜索发现了原因：int类型作为char读取时，只会将低位作为char类型的值来读取。但是高位的值并不会处理，如果之前并没有初始化int，则高位的值是任意的，因此k的值并不等于char类型的值。所以，如果我们初始化了int，这样使用就没问题了：

int k = 0;
scanf("%c", &k);

如果不是完全了解其中的细节，最好还是按照官方类型使用，否则会像这样出现一些隐藏的问题。AC代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

bool graphs[70][70];
int paths[4100];
int n, pathNum;

void inGraphs() {
	while(getchar() != '\n') ;
	int i, j, k;
	for(i = 0; i < n; ++i) {
		for(j = 0; j < n; ++j) {
			k = 0;
			scanf("%c", &k);
			if(k == '1') graphs[i][j] = true;
			if(k == '0') graphs[i][j] = false;
		}
		while(getchar() != '\n') ;
	}
}

void handleOnePath(int k) {
	int unit, begx = 0, endx = n, begy = 0, endy = n, ni = n;
	int i, j;
	while(k > 0) {
		unit = k % 5;
		k = k / 5;
		ni = ni / 2;
		switch(unit) {
			case 1:
				endx = begx + ni;
				endy = begy + ni;
				break;
			case 2:
				endx = begx + ni;
				begy = begy + ni;
				break;
			case 3:
				begx = begx + ni;
				endy = begy + ni;
				break;
			case 4:
				begx = begx + ni;
				begy = begy + ni;
				break;
		}
	}
	for(i = begx; i < endx; ++i) {
		for(j = begy; j < endy; ++j) {
			graphs[i][j] = true;
		}
	}
}

void inPaths() {
	int k, i, j;
	while(scanf("%d", &k) && k != -1) {
		if(k == 0) {
			for(i = 0; i < n; ++i) {
				for(j = 0; j < n; ++j) {
					graphs[i][j] = true;
				}
			}
		}
		handleOnePath(k);
	}
}

void outGraphs() {
	int i, j;
	for(i = 0; i < n; ++i) {
		for(j = 0; j < n; ++j) printf("%c", graphs[i][j] == true ? '*' : '.');
		putchar('\n');
	}
}

int handlePaths(int begx, int begy, int unit, int base, int basei) {
	if(unit == 1) {
		if(graphs[begx][begy] == false) return 0; 
		else return 1;
	}
	int cell[4];
	unit = unit / 2;
	cell[0] = handlePaths(begx, 		begy, 			unit, base + basei * 1, basei*5);
	cell[1] = handlePaths(begx, 		begy + unit, 	unit, base + basei * 2, basei*5);
	cell[2] = handlePaths(begx + unit, 	begy, 			unit, base + basei * 3, basei*5);
	cell[3] = handlePaths(begx + unit, 	begy + unit, 	unit, base + basei * 4, basei*5);
	if(cell[0] == 0 && cell[1] == 0 && cell[2] == 0 && cell[3] == 0) return 0;
	if(cell[0] == 1 && cell[1] == 1 && cell[2] == 1 && cell[3] == 1) return 1;
	for(int i = 0; i < 4; ++i) {
		if(cell[i] == 1) paths[pathNum++] = base + basei * (i+1); 
	}
	return 2;
}

void outPaths() {
	int i, j = 0;
	for(i = 0; i < pathNum; ++i) {
		if(j != 0 && j != 12) putchar(' ');
		if(j == 12) {
			putchar('\n');
			j = 0;
		}
		printf("%d", paths[i]);
		++j;
	}
	if(pathNum) putchar('\n');
	printf("Total number of black nodes = %d\n", pathNum);
}

int comp(const void * ltr, const void* rtr) {
	int l = *(const int *)ltr;
	int r = *(const int *)rtr;
	if(l < r) return -1;
	if(l == r) return 0;
	return 1;
}

int main() {
	int t = 0, res;
	while(scanf("%d", &n) && n != 0) {
		if(t) printf("\n");
		printf("Image %d\n", ++t); 
		memset(graphs, 0, sizeof(graphs));
		memset(paths, 0, sizeof(paths));
		pathNum = 0;
		if(n > 0) {
			inGraphs();
			res = handlePaths(0, 0, n, 0, 1);
			if(res == 1) paths[pathNum++] = 0;
			qsort(paths, pathNum, sizeof(int), comp);
			outPaths();
		} else {
			n = -n;
			inPaths();
			outGraphs();
		}
	}
	return 0;
}