记0为空格，1为红色，2为蓝色，则每种局面都可以用一个16位的三进制表示，分别用方法f和g将局面编码和解码，使用编码后的数记录以节省空间。
广度优先搜索所有可能的移动状态，用两个字典d和v分别记录从起点到给定状态的最短序列长度和所有最短序列校验和的总和。
每次搜索到的状态若是新状态（不存在于字典中），则当前序列必定是最短序列之一，将其添加到字典和搜索队列中并更新校验和的总和。
显然，若当前序列为最短序列之一，则到达该序列中每一个状态的子列也都是对应状态的最短序列之一，因此若搜索到的状态不是新状态，则只需要比较其与上一个状态的字典值是否只差1就可以判断其是否是最短序列之一，以及是否需要更新校验和的总和。
最终结果是$96356848$。
A=[[0,1,2,2],[1,1,2,2],[1,1,2,2],[1,1,2,2]]
B=[[0,2,1,2],[2,1,2,1],[1,2,1,2],[2,1,2,1]]
dx,dy,code=[0, 0, -1, 1],[-1, 1, 0, 0],[82,76,68,85]
m=100000007
f=lambda a:sum(a[i/4][i%4]*(3**i) for i in range(16))
def g(t):
b=[]
while t:
b.append(t%3)
t/=3
b+=[0]*(16-len(b))
return [b[:4],b[4:8],b[8:12],b[12:]]
q=[f(A)]
d={q[0]:0}
v={q[0]:0}
k=0
while k < len(q):
board=g(q[k])
x,y=[(i,j) for i in range(4) for j in range(4) if board[i][j]==0][0]
for j in range(4):
x1,y1=x+dx[j],y+dy[j]
if 0 <= x1 < 4 and 0 <= y1 < 4:
newBoard=[row[:] for row in board]
newBoard[x1][y1],newBoard[x][y]=newBoard[x][y],newBoard[x1][y1]
newKey=f(newBoard)
if newKey not in d:
d[newKey]=d[q[k]]+1
v[newKey]=0
q.append(newKey)
if d[newKey]==d[q[k]]+1:
v[newKey]=(v[newKey]+v[q[k]]*243+code[j])%m
k+=1
print(v[f(B)])
|
