ZOJProblem Set - 1011 Python

题目挺简单的，使用递归 + 深度优先搜索来做，直接上代码吧。

#encoding=utf8

import sys

 
# table用于存储读取的发射表

table = []

n = m = k = 0

 
def dfs(tree, index, input_signal):

    """tree是用数组表示的二叉树，index为当前开始执行的位置，input表示输入"""

    
    if tree[index] == '*':

        return True

    signals = table[int(input_signal)][ord(tree[index]) - ord('a')]

    # 该结点是叶子结点

    if (index * 2 + 1) >= len(tree) or tree[index * 2 + 1] == '*':

        for s in signals:

            # 如果产生的信号合法

            if int(s[0]) >= n - m and int(s[1]) >= n - m:

                return True

        return False

    # 该结点不是叶子结点，考虑左右两棵子树的合法性

    for s in signals:

        if dfs(tree, index * 2 + 1, s[0]) and dfs(tree, index * 2 + 2, s[1]):

            return True

    return False

if __name__ == '__main__':

    # 标记是否是新的测试例开始

    is_new_test = True

    is_new_tree = False

    is_first_test = True

    test_no = 1

#    file = open('a.txt')

#    sys.stdin = file

    for line in sys.stdin:

        # 开始一个新的测试例

        if is_new_test:

            # i, j用于标志table当前读取的位置

            i, j = 0, 0

            (n, m, k) = line.split()

            n, m, k = int(n), int(m), int(k)

            table = []

            # 测试用例结束

            if n == 0 and m == 0 and k == 0:

                break

            if is_first_test:

                print 'NTA%d:' % test_no

                is_first_test = False

            else:

                print '\nNTA%d:' % test_no

            test_no += 1

            is_new_test = False

            continue

        
        # 开始读取NTA发射表数据

        if i < n:

            t = []

            line = line.split()

            for z in range(0, len(line), 2):

                t.append((line[z], line[z + 1]))

            if j == 0:

                table.append([])

            table[-1].append(t)

            j += 1

            if j == k:

                i += 1

                j = 0

            # 读完了表格数据

            if i == n:

                table_begin = False

                is_new_tree = True

            continue

        # 读取树的高度

        if is_new_tree:

            tree_height = int(line)

            if tree_height == -1:

                is_new_test = True

                continue

            # 用一个数组来表示完全二叉树

            tree = []

            is_new_tree = False

            continue

        
        if tree_height >= 0:

            tree.extend(line.split())

            tree_height -= 1

            if tree_height == -1:

                # 已读取到一棵完整的树，调用一次

                if dfs(tree, 0, 0):

                    print 'Valid'

                else:

                    print  'Invalid'

                is_new_tree = True

            continue