方格填数

题目描述:

在n个连续的方格内填写字母A或B，相邻两格不能同时都填B。求所有可能的填写方案数。

输入格式:

一个整数n

输出格式:

按从小到输出每行的字符串，一个字符串一行

最后一行表示总的方案数

数据范围:

n <20

样例输入:

3

样例输出:

AAA
AAB
ABA
BAA
BAB
5

提示:

n = int( input( ) )
a = [ 0 ] * n
sum = 0
for i in range( _____(1)_____ ):
    r = "";     m = i
    for j in range( n ):
      _____(2)______
      m = m//2
    flag = True
    for j in range( 1, n ):
        if _________(3)__________: flag = False
    if flag:
        for j in range( n ):
            if a[j] == 0:
                r = "A" + r
            else:
                r = "B" + r
        print( r )
        sum += 1

print( sum ) 

时间限制: 1000ms
空间限制: 256MB

---