卡玛网第127题，骑士的攻击，求帮忙找出我的代码的问题

1365156784

import heapq

# Directions a knight can move on a chessboard
dirs = [[-2, -1], [-2, 1], [-1, 2], [-1, -2], [1, 2], [1, -2], [2, 1], [2, -1]]
grid = [[0] * 1001 for _ in range(1001)]

class Point:
    def __init__(self, x, y, dist1, dist2, dist_all):
        self.x = x
        self.y = y
        self.dist1 = dist1
        self.dist2 = dist2
        self.dist_all = dist_all
   
    def __lt__(self, other):
        return self.dist_all < other.dist_all

def astar(start):
    global end_x, end_y
    queue = []
    heapq.heappush(queue, start)
   
    while queue:
        cur = heapq.heappop(queue)
        if cur.x == end_x and cur.y == end_y:
            return grid[cur.x][cur.y]
        
        for dx, dy in dirs:
            next_x = cur.x + dx
            next_y = cur.y + dy
            if next_x < 1 or next_x > 1000 or next_y < 1 or next_y > 1000:
                continue
            if not grid[next_x][next_y]:
                grid[next_x][next_y] = grid[cur.x][cur.y] + 1
                next_dist1 = cur.dist1 + 5
                next_dist2 = find_dist(next_x, next_y)
                next_dist_all = next_dist1 + next_dist2
                next_point = Point(next_x, next_y, next_dist1, next_dist2, next_dist_all)
                heapq.heappush(queue, next_point)
    return -1  # In case no path is found

def find_dist(x, y):
    return (x - end_x) ** 2 + (y - end_y) ** 2

def main():
    global end_x, end_y
   
    n = int(input())
    problems = [tuple(map(int, input().split())) for _ in range(n)]
   
    for start_x, start_y, end_x, end_y in problems:
        # Reset the grid for each test case
        for i in range(1, 1001):
            for j in range(1, 1001):
                grid[i][j] = 0
        
        start = Point(start_x, start_y, 0, find_dist(start_x, start_y), find_dist(start_x, start_y))
        grid[start_x][start_y] = 0  # Starting point as 0 moves
        print(astar(start))

if __name__ == "__main__":
    main()

sfqxx

题目发出来啊

歌者文明清理员

sfqxx 发表于 2024-7-23 22:46
题目发出来啊

你啥时候回归的？？

小甲鱼的二师兄

import heapq

# Directions a knight can move on a chessboard
dirs = [[-2, -1], [-2, 1], [-1, 2], [-1, -2], [1, 2], [1, -2], [2, 1], [2, -1]]
grid = [[0] * 1001 for _ in range(1001)]

class Point:
    def __init__(self, x, y, dist1, dist2, dist_all):
        self.x = x
        self.y = y
        self.dist1 = dist1
        self.dist2 = dist2
        self.dist_all = dist_all
   
    def __lt__(self, other):
        return self.dist_all < other.dist_all

def astar(start):
    global end_x, end_y
    queue = []
    heapq.heappush(queue, start)
   
    while queue:
        cur = heapq.heappop(queue)
        if cur.x == end_x and cur.y == end_y:
            return grid[cur.x][cur.y]
        
        for dx, dy in dirs:
            next_x = cur.x + dx
            next_y = cur.y + dy
            if next_x < 0 or next_x >= 1001 or next_y < 0 or next_y >= 1001:
                continue
            if not grid[next_x][next_y]:
                grid[next_x][next_y] = grid[cur.x][cur.y] + 1
                next_dist1 = cur.dist1 + 5
                next_dist2 = find_dist(next_x, next_y)
                next_dist_all = next_dist1 + next_dist2
                next_point = Point(next_x, next_y, next_dist1, next_dist2, next_dist_all)
                heapq.heappush(queue, next_point)
    return -1  # In case no path is found

def find_dist(x, y):
    return (x - end_x) ** 2 + (y - end_y) ** 2

def main():
    global end_x, end_y
   
    n = int(input())
    problems = [tuple(map(int, input().split())) for _ in range(n)]
   
    for start_x, start_y, end_x, end_y in problems:
        # Reset the grid for each test case
        for i in range(1001):
            for j in range(1001):
                grid[i][j] = 0
        
        start = Point(start_x, start_y, 0, find_dist(start_x, start_y), find_dist(start_x, start_y))
        grid[start_x][start_y] = 0  # Starting point as 0 moves
        print(astar(start))

if __name__ == "__main__":
    main()

sfqxx

歌者文明清理员 发表于 2024-7-24 01:02
你啥时候回归的？？

遥远的几天前。

歌者文明清理员

sfqxx 发表于 2024-7-25 14:20
遥远的几天前。

应该是c艹，不是c艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹

sfqxx

歌者文明清理员 发表于 2024-7-25 20:54
应该是c艹，不是c艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹

收到