鱼C论坛

 找回密码
 立即注册
查看: 299|回复: 6

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

[复制链接]
发表于 2024-7-23 22:36:29 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
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()
PixPin_2024-07-23_22-35-58.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-23 22:46:13 | 显示全部楼层
题目发出来啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-24 01:02:20 | 显示全部楼层

你啥时候回归的??
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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], [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()
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-25 14:20:54 | 显示全部楼层

遥远的几天前。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-25 20:54:05 | 显示全部楼层
sfqxx 发表于 2024-7-25 14:20
遥远的几天前。

应该是c艹,不是c艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-26 12:22:42 | 显示全部楼层
歌者文明清理员 发表于 2024-7-25 20:54
应该是c艹,不是c艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹

收到
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-10-5 15:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表