多联骨牌
* * * *
拉格朗日计划
* * * *
多联骨牌

n阶多联骨牌是由n个单位方格粘接而成(比如俄罗斯方块中的每个形状都是一种多联骨牌)。

输出不超过6阶的所有多联骨牌,不同骨牌间以一个空格分隔,骨牌可以任意顺序输出。

1到6阶的骨牌分别有1、2、6、19、63、216种。

本题难度:



解答

本题看似很复杂(一般情形也确实如此),但由于数据量非常小,所以只需暴力枚举且在枚举过程中无需剪枝。

想象这些多联骨牌位于一个$11\times 11$的方格内,以方格的中心$(5,5)$为起点,用深度优先搜索的方式枚举即可。

每个骨牌用一个列表表示,列表内的元素就是其每个单位方格的坐标。

初始时栈内只有一个一阶骨牌,每次搜索时枚举当前骨牌的边界(也就是每个单位方格的上下左右中的合法位置)并尝试添加一个新方格后压入栈。

输出时找出当前骨牌的上下左右边界并将其转化为字符串,该字符串也用于骨牌间的去重。

最终代码行只有四行。

代码长度:291字节 vs. 全站第一:144字节。

f=lambda x,y:'\n'.join(''.join(' #'[(i,j)in p]for j in range(min(y),max(y)+1))for i in range(min(x),max(x)+1))+'\n'
d,q=set(),[[(5,5)]]
while q:p=q.pop();d.add(f(*list(zip(*p))));q+=[p+[(x,y)]for a,b in p for x,y in[(a-1,b),(a+1,b),(a,b-1),(a,b+1)]if len(p)<6and(x,y)not in p]
*map(print,d),