全部评论 7

  • 这不就是Dijkstra吗

    3天前 来自 浙江

    1
  • "zhe tai nan le"

    2天前 来自 浙江

    0
  • 
    import heapq
    from typing import List
    
    class State:
        def __init__(self, time: int, i: int, j: int):
            self.time = time
            self.i = i
            self.j = j
        
        def __lt__(self, other):
            return self.time < other.time
    
    def can_escape(n: int, m: int, A_power: int, H_power: int, 
                  fire: str, p: int, o: int, grid: List[str]) -> str:
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        heap = []
        dist = [[float('inf')] * m for _ in range(n)]
        path_len = [[0] * m for _ in range(n)]
        
        heapq.heappush(heap, State(0, 0, 0))
        dist[0][0] = 0
        path_len[0][0] = 1
        
        while heap:
            curr = heapq.heappop(heap)
            
            if curr.i == n-1 and curr.j == m-1:
                hunter_time = curr.time - 1
                hunter_steps = hunter_time // o
                return "Yes" if path_len[curr.i][curr.j] > hunter_steps else "No"
            
            if curr.time > dist[curr.i][curr.j]:
                continue
                
            for di, dj in dirs:
                ni, nj = curr.i + di, curr.j + dj
                if 0 <= ni < n and 0 <= nj < m:
                    cell = grid[ni][nj]
                    added_time = 0
                    can_pass = True
                    
                    if cell == '#':
                        can_pass = False
                    elif cell == '!':
                        added_time = 5
                    elif cell == '\\':
                        if A_power >= H_power:
                            added_time = 10
                        else:
                            can_pass = False
                    elif cell == '%':
                        if fire == '^':
                            can_pass = False
                    elif cell == '*':
                        added_time = 3
                    elif cell == '$':
                        added_time = 1
                    
                    if can_pass:
                        new_time = curr.time + added_time
                        if new_time < dist[ni][nj]:
                            dist[ni][nj] = new_time
                        
    

    3天前 来自 上海

    0
  • "不难"

    3天前 来自 浙江

    0
  • d

    3天前 来自 浙江

    0
  • d

    3天前 来自 浙江

    0
  • d

    3天前 来自 浙江

    0

热门讨论