见证我的挑战(俄罗斯方块之谜)

Question

Introduction

在游戏中，见证者 (前面可能的破坏者)有一组谜题，涉及到用你的线条画一个俄罗斯方块，同时确保你当前画的俄罗斯方块的符号保持在你画的形状内。

对于上面的绘画作品，由于L形和倒置L形俄罗斯方块分别占据了(1,2)(2,2)(3,2)(3,3)和(1,1)(1,0)(2,0)(3,0)的位置，以及位于(3,0)和(3,3)的图标都包含在白线中。

挑战

您的目标是绘制解决方案线，使其包含所有俄罗斯方块片段以及它们各自的符号。解决方案线不可能包含比所需的更多的平方(即，您必须包含组成每个俄罗斯方块的方块数之和)。每个解决方案将从左下角开始，最后在右上角结束。最后，这是代码高尔夫，所以最短的解决方案(以字节为单位)获胜。

Representation

这些拼图中的每一个都使用一个HxW正方形网格来构建俄罗斯方块，并为您在它们之间画线提供了一些空间。最好用例子来理解表示法。对于上面的图像，表示应该是

===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

解决办法是

===========
|*********|
|*X X X X |
|*******  |
| X X X*X |
|  *** *  |
| X*X*X*X |
|  * * ***|
| X*X*X X*|
|*** *****|
===========

其中，每个正方形由一个X表示，解用*s的一条线绘制，每个拼图的行数是2*H+3，每一行的字符数是2*W+3。

输入

第一个n行将给出俄罗斯方块，然后是那个俄罗斯方块的相应符号的位置。格式如下：

(i1,j1)(i2,j2)...(ik,jk)->(p,q)

其中，(ik,jk)是俄罗斯方块的kth坐标对(左坐标随着向下移动而增大，右坐标随着右移动而增大)，(p,q)是对应符号的位置。每个俄罗斯方块的起源是左上角(即左上角是(0,0))。

示例1：

X
X
XX

将会是

(0,0)(1,0)(2,0)(2,1)

示例2：

XX
X
X

将会是

(0,0)(1,0)(2,0)(0,1)

例3：

X  X
X  X

将会是

(0,0)(1,0)(0,3)(1,3)

下一个2*H+3行将由拼图的网格组成。

输出

中绘制的解决方案线输出拼图网格。

示例

示例输入1

(0,0)(0,1)->(2,1)
(0,0)(0,1)->(0,1)
(0,0)->(0,2)
=========
|       |
| X X X |
|       |
| X X X |
|       |
| X X X |
|       |
=========

示例输出1

=========
|*******|
|*X X X |
|*******|
| X X X*|
|***** *|
|*X X*X*|
|*   ***|
=========

示例输入2

(0,0)(0,1)(0,2)(1,2)(2,2)->(0,0)
(0,0)(1,0)(0,3)(1,3)->(2,1)
(0,0)(1,0)(2,0)->(1,3)
===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

示例输出2

===========
|      ***|
| X X X*X |
|      ***|
| X X X X*|
|        *|
| X X X X*|
|*** *****|
|*X*X*X X |
|* ***    |
===========

示例输入3

(0,0)(1,0)(2,0)->(1,0)
(0,0)(1,0)(2,0)->(1,6)
(0,0)(0,1)(0,2)->(1,3)
=================
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
=================

示例输出3

=================
|***         ***|
|*X*X X X X X*X |
|* *******   *  |
|*X X X X*X X*X |
|* *******   *  |
|*X*X X X X X*X |
|* ***********  |
=================

Clarifications

• 假定对于任何给定的输入都有一个解决方案。
• 如果有多种解决方案，只需打印一个。

Answer 1

Python，992

从stdin获取输入并打印解决方案。请注意，SE已经将我的制表符转换为四个空格--任何缩进超过一个空格的字符都应该是一个选项卡。

这应该不难克服，但我想我应该张贴它，因为没有其他人发布了解决方案。

L=len
R=range
j=[(-1,0),(1,0),(0,-1),(0,1)]
P=lambda y,x,q:(y,x)==(0,w)and[q+[(y,x)]]or sum([P(y+e,x+d,q+[(y,x)])for e,d in j if not(y+e,x+d)in q and 0<=x+d<=w and 0<=y+e<=h],[])
def C(q,y,x,v):
 if(y,x)in v:return
 v.add((y,x))
 for e,d in j:
    Y,X=y+e,x+d;a,b=[(y+(e+s*d+1)/2,x+(d+s*e+1)/2)for s in[-1,1]]
    if 0<=X<w and 0<=Y<h and not(a in q and b in q and abs(q.index(a)-q.index(b))==1):C(q,Y,X,v)
def G(s,c):
 if not s:return not c
 for y,x in r:
    p=set((Y+y,X+x)for Y,X in s[0])
    if c&p==p and G(s[1:],c-p):return 1
def B(q):
 for y,x in r:
    c=set();C(q,y,x,c);s=[h for(w,h)in p if w in c]
    if s and not G(s,c):return 1
h,p,g=0,[],[]
try:
 while 1:
    s=raw_input()
    if'('in s:l,o=s.split('->');p.append(map(eval,[o,'('+l.replace(')','),')+')']))
    else:g.append(list(s))
except:h=L(g)/2-1;w=L(g[0])/2-1
r=[(x/w,x%w)for x in R(w*h)]
for s in P(h,0,[]):
 if not B(s):break
for(a,b),(c,d)in zip(s,s[1:]):g[1+2*a][1+2*b]=g[1+a+c][1+b+d]=g[1+2*c][1+2*d]='*'
print'\n'.join(''.join(r)for r in g)

简单介绍一下它是如何工作的：

P查找所有可能的路径。

C查找连接到给定方格的所有方格。

G确定一组形状是否完全适合于一组正方形。

B通过检查每个连通的正方形集并检查它们的形状是否合适来确定路径是否坏。

示例

投入：

(0,0)(0,1)->(2,1)
(0,0)(0,1)->(0,1)
(0,0)->(0,2)
=========
|       |
| X X X |
|       |
| X X X |
|       |
| X X X |
|       |
=========

输出(所有俄罗斯方块被分组到右上角)：

=========
|***   *|
|*X*X X*|
|* *   *|
|*X*X X*|
|* * ***|
|*X*X*X |
|* ***  |
=========

投入：

(0,0)(0,1)(0,2)(1,2)(2,2)->(0,0)
(0,0)(1,0)(0,3)(1,3)->(2,1)
(0,0)(1,0)(2,0)->(1,3)
===========
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
| X X X X |
|         |
===========

输出(这是唯一与示例解决方案相同的输出)：

===========
|      ***|
| X X X*X |
|      ***|
| X X X X*|
|        *|
| X X X X*|
|*** *****|
|*X*X*X X |
|* ***    |
===========

投入：

(0,0)(1,0)(2,0)->(1,0)
(0,0)(1,0)(2,0)->(1,6)
(0,0)(0,1)(0,2)->(1,3)
=================
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
| X X X X X X X |
|               |
=================

输出(最右边的2块被组合在一起)：

=================
|*** *** *******|
|*X*X*X*X*X X X |
|* * * * *******|
|*X*X*X*X X X X*|
|* * * * *******|
|*X*X*X*X*X X X |
|* *** ***      |
=================