1754. 骑士精神

描述 在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士,
且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为1,纵坐标相差为2或者横坐标相差为2,纵坐标相差为1的格子)移动到空位上。
给定一个初始的棋盘,怎样才能经过移动变成如下目标棋盘: 为了体现出骑士精神,他们必须以最少的步数完成任务,若果步数大于15,返回-1。
目标棋盘是 “11111” “01111” “00*11” “00001” “00000”

解法:

    问题等价于从最终状态经过15步是否能达到起始状态。
    状态用数字表示。
    BFS搜索
    在最后步数过高的情况下,能到达的状态是指数级增加的。但是,如果状态和起始状态相差位数比剩余步数大太多就可以排除。
class Solution:
"""
@param a: the Initial state
@return: the fewest steps to complete the task
"""
def getSteps(self, a):
# Write your code here

Goal = [
[1,1,1,1,1],
[0,1,1,1,1],
[0,0,2,1,1],
[0,0,0,0,1],
[0,0,0,0,0]
]
x, y = -1, -1
P = [1] * 25
for i in range(1, 25): P[i] = 10 * P[i-1]
A = [[0] * 5 for _ in range(5)]
for i in range(5):
for j in range(5):
if a[i][j] == '*':
A[i][j] = 2
x, y = i, j
if a[i][j] == '1':
A[i][j] = 1
if a[i][j] == '0':
A[i][j] = 0

def trans(A):
ret = 0
for i in range(5):
for j in range(5):
ret += P[i*5+j] * A[i][j]
return ret

def swap(Q, rem):
nQ = []
for state,x, y in Q:
for dx, dy in [[1,2],[1,-2], [-1,2],[-1, -2], [2, 1], [2,-1], [-2, 1],[-2, -1]]:
nx, ny = x + dx, y + dy
if 0 <= nx < 5 and 0 <= ny < 5:
digit = state // P[5*nx+ny] % 10
nstate = state - 2 * P[5*x + y] + 2 * P[5*nx + ny] + digit * P[5*x + y] - digit * P[5*nx + ny]
if nstate not in vis and diff_bit(target, nstate) - 1 <= rem:
vis.add(nstate)
nQ.append((nstate,nx, ny))
return nQ
def diff_bit(s1, s2):
ret = 0
for _ in range(25):
if s1 % 10 != s2 % 10:
ret += 1
s1 //= 10
s2 //= 10
return ret

target = trans(Goal)
if target == trans(A):
return 0
vis = {trans(A)}
Q = [(trans(A), x, y)]
for i in range(1, 16):
nQ = swap(Q, 15 - i)
vis |= set(nQ)
if target in vis:
return i
Q = nQ

return -1

if __name__ == "__main__":
G = ["10110","01*11","10111","01001","00000"]
print(Solution().getSteps(G))

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

1754. 骑士精神

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 1754. 骑士精神
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏