1365156784 发表于 2024-7-23 22:36:29

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

import heapq

# Directions a knight can move on a chessboard
dirs = [[-2, -1], [-2, 1], [-1, 2], [-1, -2], , , , ]
grid = [ * 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
      
      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:
                grid = grid + 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 =
   
    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 = 0
      
      start = Point(start_x, start_y, 0, find_dist(start_x, start_y), find_dist(start_x, start_y))
      grid = 0# Starting point as 0 moves
      print(astar(start))

if __name__ == "__main__":
    main()

sfqxx 发表于 2024-7-23 22:46:13

题目发出来啊

歌者文明清理员 发表于 2024-7-24 01:02:20

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

你啥时候回归的？？

小甲鱼的二师兄 发表于 2024-7-24 01:31:47

import heapq

# Directions a knight can move on a chessboard
dirs = [[-2, -1], [-2, 1], [-1, 2], [-1, -2], , , , ]
grid = [ * 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
      
      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:
                grid = grid + 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 =
   
    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 = 0
      
      start = Point(start_x, start_y, 0, find_dist(start_x, start_y), find_dist(start_x, start_y))
      grid = 0# Starting point as 0 moves
      print(astar(start))

if __name__ == "__main__":
    main()

sfqxx 发表于 2024-7-25 14:20:54

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

遥远的几天前。

歌者文明清理员 发表于 2024-7-25 20:54:05

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

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

sfqxx 发表于 2024-7-26 12:22:42

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

收到
页: [1]
查看完整版本: 卡玛网第127题，骑士的攻击，求帮忙找出我的代码的问题