fork download
copy 
  1. from heapq import heappush, heappop
  2.  
  3. DIRS = [(-1, -1), (-1, 0), (-1, 1),
  4.         (0, -1),          (0, 1),
  5.         (1, -1),  (1, 0), (1, 1)]
  6.  
  7. def is_valid(x, y, n, m, blocked):
  8.     return 0 <= x < n and 0 <= y < m and (x, y) not in blocked
  9.  
  10. def path_finder(grid, src, dest, blocked):
  11.     n, m = len(grid), len(grid[0])
  12.     INF = 10**18
  13.     dist = [[INF] * m for _ in range(n)]
  14.     sx, sy = src
  15.     dx, dy = dest
  16.  
  17.     pq = []
  18.     heappush(pq, (0, sx, sy))
  19.     dist[sx][sy] = 0
  20.  
  21.     while pq:
  22.         cost, x, y = heappop(pq)
  23.         if (x, y) == (dx, dy):
  24.             return cost
  25.         neigh = []
  26.         for ddx, ddy in DIRS:
  27.             nx, ny = x + ddx, y + ddy
  28.             if is_valid(nx, ny, n, m, blocked):
  29.                 neigh.append(((nx, ny), grid[nx][ny]))
  30.  
  31.         if not neigh:
  32.             continue
  33.         vals = [v for (_, v) in neigh]
  34.  
  35.         for i, ((nx, ny), val_t) in enumerate(neigh):
  36.             if len(vals) == 1:
  37.                 max_other = None
  38.             else:
  39.                 max_other = max(vals[:i] + vals[i+1:])
  40.  
  41.             if max_other is None:
  42.                 required = 0
  43.             else:
  44.                 required = max(0, (max_other + 1) - val_t)
  45.  
  46.             new_cost = cost + required
  47.             if new_cost < dist[nx][ny]:
  48.                 dist[nx][ny] = new_cost
  49.                 heappush(pq, (new_cost, nx, ny))
  50.  
  51.     return -1
  52.  
  53. N, M = map(int, input().split())
  54. grid = [list(map(int, input().split())) for _ in range(N)]
  55. sx, sy = map(int, input().split())
  56. dx, dy = map(int, input().split())
  57. K = int(input())
  58. blocked = set()
  59. for _ in range(K):
  60.     bx, by = map(int, input().split())
  61.     blocked.add((bx - 1, by - 1))
  62. sx, sy, dx, dy = sx - 1, sy - 1, dx - 1, dy - 1
  63.  
  64. result = path_finder(grid, (sx, sy), (dx, dy), blocked)
  65. print(result)
Success #stdin #stdout 0.08s 14060KB
comments (?)
stdin
copy 
6 6
1 17 18 20 11 10
3 17 15 18 16 15
10 11 20 6 8 3
18 18 5 11 4 16
3 4 8 17 18 20
3 17 15 18 16 15
1 1
3 4
3
2 1
2 2
5 5
stdout
copy 
15
https://ideone.com/AWDTWx
language:
Python 3 (python  3.12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!