ZOJ 1011 NTA

原题目链接

1011 NTA

NTA（非确定性树自动机）是一种树形结构装置，该装置内置有一套运行规则，通过这些规则，装置可以产生若干个信号，这些信号组成一个信号系统，在这样的系统中，一个信号为起始信号，若干个信号为可接受信号，其余信号为辅助信号。如果一对信号中的两个信号都是可接受的，则称该对信号为可接受对。

这里讨论的树都是二叉树，每个非叶子节点都有两个后继。在任何一棵有限树中，每个节点都有一个信号传递元素。当信号到达一个节点时，信号遇到信号传递物质，引发信号反应，产生多对信号。然后设备非确定性地选择一对信号发送给它的后继。信号对中的第一个信号发送给左边的后继节点，第二个信号发送给右边的后继节点。

NTA 的整个操作如下：

该装置首先向根节点发出起始信号，根据根节点的信号传输物质，非确定性地选择一对信号，将第一对信号发送给左子树，将第二对信号发送给右子树，然后两对信号分别在相应的节点遇到信号传输物质，产生另外两对信号，如此循环往复，直至到达叶子节点。

如果信号到达一个叶子，并且该叶子能够产生一对可接受的信号，我们就说该叶子是“可摇动的”。如果所有叶子都是“可摇动的”，则从根到叶子的信号传输被认为是有效的。如果存在这样的有效传输，则具有信号传输物质的树结构是有效的。如果所有传输都是无效的，则树是无效的。

为简单起见，我们用连续的小写字母“a”、“b”、“c”等表示信号传输元件。NTA 的信号是连续的数字 0、1、2、… 等等。第一个信号 0 始终是起始信号。因此，4 信号 NTA 的信号为“0”、“1”、“2”和“3”。接受信号排列在数字序列的末尾，因此，如果 4 信号 NTA 有两个接受信号，则接受信号为“2”和“3”。信号的转换规则基于转换表。例如，下表描述了具有四个信号“0”、“1”、“2”、“3”和三个信号传输元件“a”、“b”和“c”的转换表。

T	a	b	c
0	(1,2)	(2,1)	(1,0)
1	(2,2)	(0,2),(1,0)	(3,2)
2	(2,2)	(2,3)	(1,2)
3	(1,2)	(2,1)	(3,2)

在这个转换表中，信号对某些信号传输元件的反应是确定性的，而其他反应则是非确定性的。在上面的例子中，如果信号“1”到达具有传输元件“b”的节点，则反应是非确定性的。

现在你的任务是编写一个程序来判断含有某种信号传递物质的树结构是否有效。

输入

输入文件包含几个案例。每个案例都描述了一系列 NTA 描述和一些初始树配置。每个案例的第一行由三个整数 n、m 和 k 组成。整数 n 表示信号的数量，m 表示接受信号的数量，k 表示信号传输元件的数量。接下来的 nk 行按行主序描述转换表。信号到信号传输元件的每个转换都在单独的一行中给出。在这样的行上，每两个数字代表一个可能的转换。

接下来是树结构的描述。对于每个树结构，在单独的一行中给出一个数字 L，以指示树的级别。接下来的 L+1 行包含字母序列，描述树结构。每行描述一个级别。两个连续字母之间存在一个空格。第 0 级首先开始。在树结构中，空节点用“*”标记。L=-1 的树结构终止该 NTA 的树结构配置，不应判断此结构。

输入以 n=0、m=0 和 k=0 开头的描述结束。不应处理此描述。

注意：在每种情况下，NTA 最多有 l5 个信号和 10 个字符。每棵树的级别不超过 10。

输出

对于每个 NTA 描述，打印 NTA 编号（NTA1、NTA2 等），后跟冒号。然后对于 NTA 的每个初始树配置，打印单词“有效”或“无效”。

在 NTA 案例之间打印空白行。

示例输入

4 2 3
1 2
2 1
1 0
2 2
0 2 1 0
3 2
2 2
2 3
1 2
1 2
2 1
3 2
3
a
b c
a b c b
b a b a c a * *
2
b
a b
b c * *
-1
0 0 0

样本输入的输出

NTA1:
Valid
Invalid

c++代码

#include<bits/stdc++.h>using namespace std;class tree{
public:char val;int code;tree* left;tree* right;tree(char val){this->val = val;this->code = -1;this->left = NULL;this->right = NULL;}
};bool dfs(tree* root, vector<vector<vector<int>>>& trans, int* left, int* right){vector<int> middle = trans[root->code][root->val - 'a'];if (root->left == NULL && root->right == NULL){for (int i = 0; i < middle.size(); i += 2){if (middle[i] >= * left && middle[i] <= *right&& middle[i + 1] >= * left && middle[i + 1] <= * right) return true;}return false;}for (int i = 0; i < middle.size(); i += 2){root->left->code = middle[i];root->right->code = middle[i + 1];bool key1 = false, key2 = false;key1 = dfs(root->left, trans, left, right);if (key1) key2 = dfs(root->right, trans, left, right);if (key1 && key2) return true;}return false;
}int main(){int n, m, k, L, count = 0;while(cin >> n >> m >> k){getchar();count++;if (n == 0 && m == 0 && k == 0) break;vector<vector<vector<int>>> trans(n, vector<vector<int>>(k));for (int i = 0; i < n; i++){for (int j = 0; j < k; j++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;trans[i][j].push_back(a - '0');}}}if (count != 1) cout << endl;cout << "NTA" << count << ":" << endl;while(cin >> L){getchar();if (L == -1) break;vector<vector<tree*>> roots(L + 1);for (int i = 0; i < L + 1; i++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;if (a == '*') roots[i].push_back(NULL);else roots[i].push_back(new tree(a));}}for (int i = 0; i < L + 1; i++){int z = roots[i].size();for (int j = 0; j < z; j++){if (i != L && roots[i][j] != NULL){roots[i][j]->left = roots[i + 1][2 * j];roots[i][j]->right = roots[i + 1][2 * j + 1];}}}roots[0][0]->code = 0;int right = n - 1;int left = n - m;if (dfs(roots[0][0], trans, &left , &right)) cout << "Valid" << endl;else cout << "Invalid" << endl;}}return 0;
}//by wqs

题目解析

题目涉及一个名为 NTA（非确定性树自动机）的设备，该设备基于一组转换规则将信号传递下去，最终判断树结构是否有效。具体来说，设备根据信号传递规则，向二叉树的各个节点传递信号，信号传递的有效性取决于每个叶子节点是否能够接受一对“有效的信号对”。

树是一个二叉树，每个非叶子节点有两个子节点。信号传递过程中，从根节点开始传递信号，根节点通过转换规则将信号分发到两个子节点。这个过程会一直递归到叶子节点。

转移规则可以是确定性的（一个信号只能产生一个新的信号对），也可以是非确定性的（一个信号可以产生多个不同的信号对）。

当信号到达叶子节点时，该节点被认为是“可摇动”的，只有当该节点能产生一个有效的信号对（两个信号都为接受信号时），才认为该叶子节点是可摇动的。

如果从根节点到所有叶子节点的信号传递都能满足每个叶子节点的可摇动条件（即每个叶子节点的信号对都为接受信号对），则该树结构是有效的。

否则该树结构为无效。

样例理解

ZOJ 1011 NTA第一个样例解释

ZOJ 1011 NTA 第二个样例解释

实现思路

1、获得转移表

vector<vector<vector<int>>> trans(n, vector<vector<int>>(k));//转移表初始化for (int i = 0; i < n; i++){for (int j = 0; j < k; j++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;trans[i][j].push_back(a - '0');//获得转移表}}
}

2、创建层序遍历树形数组

输入是按层输入的，根据这个特点可以得出层序遍历树形数组

vector<vector<tree*>> roots(L + 1); //初始化，roots[0]表示第一层结点,roots[1]表示第二层结点，以此类推for (int i = 0; i < L + 1; i++){while(true){char a = (char)getchar();if (a == '\n') break;if (a == ' ') continue;if (a == '*') roots[i].push_back(NULL);else roots[i].push_back(new tree(a));}
}

3、根据层序遍历树形数组创建树形结构

for (int i = 0; i < L + 1; i++){int z = roots[i].size();for (int j = 0; j < z; j++){if (i != L && roots[i][j] != NULL){roots[i][j]->left = roots[i + 1][2 * j];roots[i][j]->right = roots[i + 1][2 * j + 1];}}
}//roots[i][j]的左孩子是roots[i + 1][2 * j]，右孩子是roots[i + 1][2 * j + 1]
//这样roots[0][0]就是我们的根节点，已经创建好了

4、深度优先搜索

bool dfs(tree* root, vector<vector<vector<int>>>& trans, int* left, int* right){//root当前根节点,trans转换表,left,right有效信号的区间范围vector<int> middle = trans[root->code][root->val - 'a'];if (root->left == NULL && root->right == NULL){//叶子结点for (int i = 0; i < middle.size(); i += 2){if (middle[i] >= * left && middle[i] <= *right&& middle[i + 1] >= * left && middle[i + 1] <= * right) return true;//只要有一对有效的就是可摇动}return false;//没有一对有效的信号，足以说明此条路，树是无效的}for (int i = 0; i < middle.size(); i += 2){root->left->code = middle[i];root->right->code = middle[i + 1];bool key1 = false, key2 = false;key1 = dfs(root->left, trans, left, right);//判断左子树是否有效if (key1) key2 = dfs(root->right, trans, left, right);//判断右子树是否有效if (key1 && key2) return true;//左子树有效并且右子树有效则这棵树有效}return false;//所有的路这棵树都无效，可以得出这棵树无效
}