fork download
copy 
  1. __author__ = 'Achut'
  2.  
  3. from collections import deque
  4. class vertex:
  5.     def __init__(self,c,a,b):
  6.         self.node = c
  7.         self.occup = 0
  8.         self.count = -1
  9.         self.x = a
  10.         self.y = b
  11. try:
  12.     while True:
  13.         m,n = map(int, input().split())
  14.         if m == n == 0:
  15.             break
  16.         a = []
  17.         start_x,start_y = 0,0
  18.         for i in range(n):
  19.             s = input()
  20.             x = []
  21.             for c in s:
  22.                 z = vertex(c,i,len(x))
  23.                 x.append(z)
  24.                 if c is "S":
  25.                     start_x,start_y = i,len(x)-1
  26.             a.append(x)
  27.  
  28.         queue = deque()
  29.         a[start_x][start_y].occup = 1
  30.         queue.append(a[start_x][start_y])
  31.         ans =[]
  32.         while queue:
  33.             t = queue.pop()
  34.             if t.x - 1 >= 0:# and a[t.x - 1][t.y].occup == 0:
  35.                 if a[t.x - 1][t.y].node != 'D' and a[t.x - 1][t.y].node != 'X' and a[t.x - 1][t.y].node != 'S':
  36.                     if a[t.x - 1][t.y].count < 0 or a[t.x - 1][t.y].count > t.count + int(a[t.x - 1][t.y].node):
  37.                         a[t.x - 1][t.y].count = t.count + int(a[t.x - 1][t.y].node)
  38.                     #a[t.x-1][t.y].occup = 1
  39.                         queue.appendleft(a[t.x - 1][t.y])
  40.                 elif a[t.x - 1][t.y].node == 'D':
  41.                     ans.append(t.count)
  42.  
  43.             if t.x + 1 < n:# and a[t.x + 1][t.y].occup == 0:
  44.                 if a[t.x + 1][t.y].node != 'D' and a[t.x + 1][t.y].node != 'X' and a[t.x + 1][t.y].node != 'S':
  45.                     if a[t.x + 1][t.y].count < 0 or a[t.x + 1][t.y].count > t.count + int(a[t.x + 1][t.y].node):
  46.                         a[t.x + 1][t.y].count = t.count + int(a[t.x + 1][t.y].node)
  47.                     #a[t.x+1][t.y].occup = 1
  48.                         queue.appendleft(a[t.x + 1][t.y])
  49.                 elif a[t.x + 1][t.y].node == 'D':
  50.                     ans.append(t.count)
  51.  
  52.             if t.y - 1 >= 0:# and a[t.x][t.y-1].occup == 0:
  53.                 if a[t.x][t.y - 1].node != 'D' and a[t.x][t.y - 1].node != 'X' and a[t.x][t.y - 1].node != 'S':
  54.                    if a[t.x][t.y - 1].count < 0 or a[t.x][t.y - 1].count > t.count + int(a[t.x][t.y - 1].node):
  55.                         a[t.x][t.y-1].count = t.count + int(a[t.x][t.y-1].node)
  56.                    # a[t.x][t.y-1].occup = 1
  57.                         queue.appendleft(a[t.x][t.y-1])
  58.                 elif a[t.x][t.y-1].node == 'D':
  59.                     ans.append(t.count)
  60.  
  61.             if t.y + 1 < m:# and a[t.x][t.y+1].occup == 0:
  62.                 if a[t.x][t.y+1].node != 'D' and a[t.x][t.y+1].node != 'X' and a[t.x][t.y+1].node != 'S':
  63.                     if a[t.x][t.y + 1].count < 0 or a[t.x][t.y + 1].count > t.count + int(a[t.x][t.y + 1].node):
  64.                         a[t.x][t.y+1].count = t.count + int(a[t.x][t.y+1].node)
  65.                     #a[t.x][t.y+1].occup = 1
  66.                         queue.appendleft(a[t.x][t.y+1])
  67.                 elif a[t.x][t.y+1].node == 'D':
  68.                     ans.append(t.count)
  69.  
  70.         ans = sorted(ans)
  71.         print(ans[0]+1)
  72. except:
  73.     pass
Success #stdin #stdout 0.11s 10104KB
comments (?)
stdin
copy 
4 3
X1S3
42X4
X1D2
5 5
S5213
2X2X5
51248
4X4X2
1445D
0 0
stdout
copy 
4
23
https://ideone.com/ay2W05
language:
Python 3 (python  3.9.5)
created:
9 years 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!