fork download
copy 
  1. def findIndex(c, m2d):
  2.     return [(x,y) for x,v in enumerate(m2d) for y,n in enumerate(v)
  3.             if n == c][0]
  4.  
  5. def neighbourhood(x,y,m2d):
  6.     return ((x+i,y+j) for i,j in [(0,1),(0,-1),(1,0),(-1,0)]
  7.             if m2d[x+i][y+j] != '#')
  8.  
  9. def diff(x,y): return abs(x[0]-y[0]) + abs(x[1]-y[1])
  10.  
  11. def solve(m2d):
  12.     start, goal = findIndex('S', m2d), findIndex('G', m2d)
  13.     openN, closeN = {start:(diff(start,goal), start)}, {}
  14.     while openN != {}:
  15.         (n,r) = sorted(openN.iteritems(), key=lambda(k,v):v[0])[0]
  16.         closeN[n] = openN.pop(n)
  17.         if n == goal: break
  18.         for (x,y) in neighbourhood(n[0], n[1], m2d):
  19.             v = r[0] - diff(goal,n) + diff(goal,(x,y)) + 1
  20.             if (x,y) in openN and v < openN[x,y][0]:
  21.                 openN[x,y] = (v, n)
  22.             if (x,y) in closeN and v < closeN[x,y][0]:
  23.                 openN[x,y] = (v, n)
  24.                 closeN.pop(x,y)
  25.             if (x,y) not in openN and (x,y) not in closeN:
  26.                 openN[x,y] = (v,n)
  27.     print_path(start, goal, closeN)
  28.  
  29. def print_path(start, goal, closeN):
  30.     path, x = [], goal
  31.     while x != start:
  32.         y = closeN[x][1]
  33.         if x[0] > y[0]: path.append('d')
  34.         elif x[0] < y[0]: path.append('u')
  35.         elif x[1] > y[1]: path.append('r')
  36.         elif x[1] < y[1]: path.append('l')
  37.         x = y
  38.     print(''.join(reversed(path)))
  39.  
  40.  
  41. solve([
  42. '#######',
  43. '#.....#',
  44. '#.G.#.#',
  45. '#..#..#',
  46. '#.#.S.#',
  47. '#.....#',
  48. '#######'])
Success #stdin #stdout 0.08s 10920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
uruullld
https://ideone.com/SUA7T
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

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!