带主教的骑士的最小步数

Question

题目是在n*n的棋盘上，马从A点到B点的最少步数（马可以水平走两步，垂直走一步，或者垂直走两步，水平走一步）。棋盘上有一个象斜行，除非象已死或该位置为B点，否则马不能移动到受到象威胁的位置。马可以选择杀死象（如果它处于可以威胁的位置）它可以移动到) 并释放所有以前受到威胁的位置。

我在参加的在线评估中得到了这个问题，但在 15 个测试用例中只答对了 10 个。我想我可能需要在队列中的元组中添加一个布尔值，以判断主教在最近一步是否还活着，但为时已晚。

我该如何修改？

from collections import deque
import math

n = 5
startRow = 0
startCol = 0
endRow = 4
endCol = 3
bishopRow = 3
bishopCol = 0
from collections import deque
import math
#
# Complete the 'moves' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER startRow
#  3. INTEGER startCol
#  4. INTEGER endRow
#  5. INTEGER endCol
#  6. INTEGER bishopRow
#  7. INTEGER bishopCol
#
def isBishopAlive(n, bishopRow, bishopCol):
    if bishopRow < n and bishopCol < n:
        return True
    else:
        return False
def moves(n, startRow, startCol, endRow, endCol, bishopRow, bishopCol):
    # Write your code here
    x, y = abs(endRow), abs(endCol)
    res = 0
    moves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))
    visited = []
    queue = deque()
    queue.append((startRow, startCol, 0))
    while queue:
        i, j, steps = queue.popleft()
        if i == x and j == y:
            return res + steps
        for di, dj in moves:
            cr = i + di
            cc = j + dj
            if isBishopAlive(n, bishopRow, bishopCol) == True:
                if abs(cr-bishopRow) == abs(cc-bishopCol):
                    if cc != y and cr != x:
                        continue
                if (cr == bishopRow) and (cc == bishopCol):
                    bishopRow, bishopCol = math.inf, math.inf
            if abs(cr) > n-1 or abs(cc) > n-1:
                continue
            if (cr, cc) in visited:
                continue
            if isBishopAlive(n, bishopRow, bishopCol) == True:
                bishop = True
            else:
                bishop = False
            if ((x-i) * di) > 0 or ((y-j) * dj) > 0:
                queue.append([cr, cc, steps+1])
                visited.append((cr, cc))
    return -1

Answer 1

您的代码中存在以下问题：

永远不会捕获主教，因为当 cr 和 cc 到达那个方格时，首先会评估 if abs(cr-bishopRow) == abs(cc-bishopCol) 条件 --并找到 true -- 后跟 continue.
当主教被捕获时，您的代码在查看其他未捕获主教的路径时永远不会将其放回原处。相反，队列中的项目应该包括是否通过捕获主教来实现该状态。
visited 列表中的项目没有表明访问是否发生在主教还活着的时候。但这很重要，因为如果您首先在主教还活着的情况下访问了一个广场，然后在主教被俘后再次访问它，那么第二次访问可能会带来更好的解决方案。因此，在将方块标记为已访问时，将存活状态包含在元组中。
该代码允许将 cr 或 cc 的负坐标推送到队列中。应该避免这种情况。

这种排除远离目标的动作太乐观了：

if ((x-i) * di) > 0 or ((y-j) * dj) > 0

以这个棋盘为例，其中“N”是马，“B”是象，“e”是末格：

┌───┬───┬───┬───┬───┐
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │ B │
├───┼───┼───┼───┼───┤
│   │   │ N │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │ e │
└───┴───┴───┴───┴───┘

象必须先走，然后马必须移到顶行以获得最佳解决方案。

我建议只删除此条件，否则请确保它不是太严格并且永远不会排除最佳路径。

没问题，但是：

res 从未被赋值为 0：不需要此变量
bishop 只是 set，但永远不会 read：这个变量（和 if...else 块它）不需要
visited 最好是集合而不是列表，这样时间复杂度会更好。
endRow和endCol永远不会是负数，所以在x和y中复制它们的绝对值是没有用的。只需使用原始参数变量即可。
当您在将方块放入队列时将它们标记为已访问时，您也应该在进入循环之前对起始方块执行相同的操作。
有一个嵌套的 if 导致 continue。这些 if 条件可以使用 and

if

同级别的两个 if 条件都导致 continue 可以使用 or

if

(cr == bishopRow) 两边的括号不是必需的。
您可以通过在执行移动时检查是否达到目标来节省一些执行时间，而不是等到该移动从队列中弹出。这只是意味着您必须进行初步检查以查看起始位置是否等于结束位置，但这是值得的。

这是更正后的版本：

def moves(n, startRow, startCol, endRow, endCol, bishopRow, bishopCol):
    if startRow == endRow and startCol == endCol:  # Deal with trivial case
        return 0
    moves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))
    queue = deque()
    queue.append((startRow, startCol, True, 0))  # Include that bishop is alive
    # Let visited be a set. Mark start as visited and include alive-status
    visited = set([(startRow, startCol, True)])
    while queue:
        i, j, alive, steps = queue.popleft()
        for di, dj in moves:
            cr = i + di
            cc = j + dj
            if cr == endRow and cc == endCol:  # When found, don't bother about queuing it
                return steps + 1 # No need for a res variable 
            # Update alive-state, just for current path
            stillalive = alive and (cr != bishopRow or cc != bishopCol)
            # Neither cr/cc should be negative
            if 0 <= cr < n and 0 <= cc < n and (cr, cc, stillalive) not in visited and (
                    not stillalive or abs(cr - bishopRow) != abs(cc - bishopCol)):
                queue.append((cr, cc, stillalive, steps + 1))  # Append alive-status too
                visited.add((cr, cc, stillalive))  # Visited should depend on alive
    return -1

带主教的骑士的最小步数

Minimum moves of a knight with bishop

python

queue

depth-first-search