UVa 620 Cellular Structure

題意：給定O為一條細胞序列

• 若O僅僅為'A'，那麼是simple
• 若O為'OAB'的型態，則OAB的O需要符合O的3種型態的其中一種，如果符合則為Fully-Grown，否則為Mutant。
• 若O為'BOA'的型態，則BOA的O需要符合O的3種型態的其中一種，如果符合則為Mutagenic，否則為Mutant。

想法：

　　用遞迴式parsing來分析O為哪種型態，如果為第2種和第3種，則要繼續呼叫遞迴分析O的型態，只要分析過程中只要O不符合3種的其中一種，則不用再分析，直接回傳Mutant。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	char APU[1000];
	int parsing (int front, int back)
	{
	// 0:Mutant
	// 1:Simple
	// 2:Fully-Grown
	// 3:Mutagenic
	if (front==back && APU[front]=='A') return 1;
	if (APU[back]=='B' && APU[back-1]=='A'){ // 判斷是否為Fully Grown
	if (front == back-1) return 0; // 如果為"AB"，那麼是Mutant
	else if (parsing (front,back-2) != 0) return 2;
	}
	if (APU[front]=='B' && APU[back]=='A'){ // 判斷是否為Mutagenic
	if (front+1 == back) return 0; // 如果為"BA"，那麼是Mutant
	else if (parsing (front+1,back-1) != 0) return 3;
	}
	return 0; // O不符合上面3種任一種型態，回傳0
	}
	int main()
	{
	int Case;
	scanf("%d",&Case);
	while (Case--){
	scanf("%s",APU);
	int t = parsing (0,strlen(APU)-1);
	switch (t){
	case 0: printf("MUTANT\n"); break;
	case 1: printf("SIMPLE\n"); break;
	case 2: printf("FULLY-GROWN\n"); break;
	case 3: printf("MUTAGENIC\n"); break;
	}
	}
	return 0;
	}

view raw [UVa] 620 Cellular Structure.cpp hosted with ❤ by GitHub