题解

UVa 457 - Linear Cellular Automata 解题报告

题目链接：http://uva.onlinejudge.org/external/4/457.html

题目分析

题目的背景是细胞增殖，这种增殖受到 DNA 的控制。题目给出了 dish 中的细胞的增殖规则，要求程序读入 DNA，输出第 1 - 50 天中每个 dish 的细胞数。

关键的地方在于：某 dish 该天的细胞数 = DNA[K]，K = 该 dish 昨天的细胞数 + 左右 dish 昨天的细胞数
还要处理两处特殊情况：最左（右） dish 的左（右）侧没有 dish

这道题可以通过一天天地计算出每个 dish 中的细胞数来求解。要注意的是，某 dish 该天的细胞数是参考昨天的情况计算出来的。由于程序是逐个 dish 计算，因此要先拷贝昨天的情况，否则如果仅使用一个数组来记录并直接更改，那么同一天中后更新的 dish 会受到已更新的 dish 的影响。

为了方便，我在设计 dish 的时候，在左右两侧增加了两个 dish，分别是 dish[0] 和 dish[41]，令它们的细胞数一直为 0（在每天更新细胞数时不更新它们），这样就不必显示地对最左（右）的 dish 进行特殊处理了。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <string.h>

int DNA[10], dish[42], old_dish[42];	/* dish的左右端用0做边界 */

void output(int out_dish[]);

int main(void)
{
	int n, i, j;

	scanf("%d", &n);
	while (n--) {
		memset(DNA, 0, sizeof(DNA));
		memset(dish, 0, sizeof(dish));
		memset(old_dish, 0, sizeof(old_dish));

		for (i = 0; i < 10; i++)
			scanf("%d", &DNA[i]);

		old_dish[20] = 1;
		output(old_dish);		/* 第1天 */

		for (i = 2; i <= 50; i++) {     /* 第2天至第50天 */
			for (j = 1; j <= 40; j++)   /* 更新每个dish */
				dish[j] = DNA[old_dish[j] + old_dish[j-1] + old_dish[j+1]];
			output(dish);
			memcpy(old_dish, dish, sizeof(old_dish)); /* 今天成为明天的昨天 */
		}
		if (n != 0) putchar('\n');
	}

	return 0;
}

/* 输出 */
void output(int out_dish[])
{
	int i;
	for (i = 1; i <= 40; i++)
		switch (out_dish[i]) {
			case 1: putchar('.'); break;
			case 2: putchar('x'); break;
			case 3: putchar('W'); break;
			default: putchar(' ');
		}
	putchar('\n');
}