试题 算法训练 跳马 BFS

Question

试题 算法训练 跳马

这个BFS哪里有问题啊？我自己编了几个测试用例都能过啊，为什么过不了蓝桥杯的测试？

试题链接

问题描述： 一个8×8的棋盘上有一个马初始位置为(a,b)，他想跳到(c,d)，问是否可以？如果可以，最少要跳几步？
输入格式：一行四个数字a,b,c,d。
输出：最少步数，如果跳不到，输出-1

```python
from collections import deque

def IsValid(x, y):
    return 0 <= x < 8 and 0 <= y < 8

def bfs(now, ne):
    direction = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]
    queue = deque([(now, 0)])
    visited = {now}

    while queue:
        (x, y), step = queue.popleft()

        if (x, y) == ne:
            return step

        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if IsValid(nx, ny) and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append(((nx, ny), step + 1))

    return -1  # 如果无法到达目标，则返回-1


origin_x, origin_y, next_x, next_y = map(int, input().strip().split())
origin_dic = (origin_x, origin_y)
next_dic = (next_x, next_y)

ans = bfs(origin_dic, next_dic)
print(ans)

```

Answer 1

from collections import deque 
def IsValid(x, y):return 0 <
= x <
= 8 and 0 <
= y <
= 8 
def bfs(now, ne):direction = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]queue = deque([(now, 0)])visited = {now}while queue:(x, y), step = queue.popleft()if (x, y) == ne:return stepfor dx, dy in direction:nx, ny = x + dx, y + dyif IsValid(nx, ny) and (nx, ny) not in visited:visited.add((nx, ny))queue.append(((nx, ny), step + 1))return -1 
origin_x, origin_y, next_x, next_y = map(int, input().strip().split())origin_dic = (origin_x, origin_y)next_dic = (next_x, next_y) 
ans = bfs(origin_dic, next_dic)print(ans)

在这段代码中，主要问题可能是在函数IsValid中，判断条件应该是0 <
= x <
8 and 0 <
= y <
8而不是0 <
= x <
= 8 and 0 <
= y <
= 8。这个地方可能会导致有些测试用例无法通过。另外，还需要注意输入输出格式是否符合问题描述的要求。希望对您有帮助。

有问题你别着急，评论留言都可以，看到马上就回复，尽量及时补充齐