UVa - 457 - Linear Cellular Automata 題解

本題大概題意：

給出一個數組DNA，包含10個數值，如：DNA[10] = {0,1,2,3,,1,2,3,0,1,2}所有數值應該不大於3.

給出一行40個字符的字符串： 空格代表0， '.'代表1，'x'代表2，'W'代表3。 相鄰三個數值（或兩個數值）相加得到的數作為DNA的下標，然後取DNA數組改下標的數值為新的值。產生新的字符串。

好難說清楚，看原文吧，的確是很難理解的題目：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=398

下列程序僅供參考，帶比較復雜的輸入輸出處理，也許不太適合初學者。達到0.015s速度，沒能上排名。網站排名的都有0.000s的，不過是很久的數據了, 大概更新了。

class LinearCellularAutomata
{
	const static int MAX_B = 5120;
	const static int FLASH_P = MAX_B - 45;
	int ist, ost, len;
	char inBuf[MAX_B];
	char outBuf[MAX_B];
	const static int DISHES = 40;
	int DNA[10];

	char getFromBuf()
	{
		if (ist >= len)
		{
			len = fread(inBuf, sizeof(char), MAX_B, stdin);
			ist = 0;
		}
		return inBuf[ist++];
	}

	int intFromBuf()
	{
		char c = getFromBuf();
		while (c < '0' || '9' < c)
		{
			c = getFromBuf();
		}
		int num = 0;
		while ('0' <= c && c <= '9' && len)
		{
			num = (num<<1) + (num<<3) + (c - '0');
			c = getFromBuf();
		}
		return num;
	}

	void wrToBuf(const char *p)
	{
		if (ost > FLASH_P)
		{
			fwrite(outBuf, sizeof(char), ost, stdout);
			ost = 0;
		}
		while (*p)
		{
			outBuf[ost++] = *p;
			p++;
		}
	}

	inline void flashLeft()
	{
		if (ost) fwrite(outBuf, sizeof(char), ost, stdout);
	}

	int cToInt(char a)
	{
		if (' ' == a) return 0;
		if ('.' == a) return 1;
		if ('x' == a) return 2;
		return 3;
	}
	char iToChar(int i)
	{
		if (0 == i) return ' ';
		if (1 == i) return '.';
		if (2 == i) return 'x';
		return 'W';
	}

	void bacterialColonies(char *dishes)
	{
		for (int r = 1; r < 50; r++)
		{
			int last = 0;
			for (int i = 0; i < DISHES; i++)
			{
				int k = cToInt(dishes[i]);
				int cur = k;

				if (0 == i)
					k += cToInt(dishes[i+1]);
				else if (i+1 == DISHES)
					k += last;
				else 
					k += last + cToInt(dishes[i+1]);

				last = DNA[k];
				dishes[i] = iToChar(last);
				last = cur;
			}
			wrToBuf(dishes);
		}		
	}
public:
	LinearCellularAutomata():ist(0), ost(0), len(0)
	{
		int testCases = 0;		

		testCases = intFromBuf();
		while (testCases--)
		{
			for (int i = 0; i < 10; i++)
			{
				DNA[i] = intFromBuf();
			}

			//初始化
			char firLine[DISHES+2];
			for (int i = 0; i < DISHES; i++)
			{
				firLine[i] = ' ';
			}
			firLine[19] = '.';
			firLine[40] = '\n';
			firLine[41] = '\0';

			wrToBuf(firLine);
			char *dishes = firLine;//這裡dishes和firLine都是操作同一份數據
			bacterialColonies(dishes);
			if (testCases) wrToBuf("\n\0");
		}
		flashLeft();
	}
};