Advertisement
t_naveen_2308

Untitled

Feb 11th, 2025
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.98 KB | None | 0 0
  1. from collections import deque
  2. import sys
  3.  
  4. class Solution:
  5.    
  6.     def preprocessing(self):
  7.         self.alist = {}
  8.         moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
  9.         is_valid = lambda r, c: 0<=r<len(self.lis) and 0<=c<len(self.lis[0]) and self.lis[r][c] in (' ', '*')
  10.         s, k, e = (0, 0), (0, 0), (0, 0)
  11.         for i in range(len(self.lis)):
  12.             for j in range(len(self.lis[0])):
  13.                 if self.lis[i][j] in (' ', '*'):
  14.                     self.alist[(i, j)] = []
  15.                     for move in moves:
  16.                         r, c = i+move[0], j+move[1]
  17.                         if is_valid(r, c):
  18.                             self.alist[(i, j)].append((r, c))
  19.                     if j==0 and self.lis[i][j]==' ':
  20.                         s = (i, j)
  21.                     if j==len(self.lis[0])-1 and self.lis[i][j]==' ':
  22.                         e = (i, j)
  23.                     if self.lis[i][j]=='*':
  24.                         k = (i, j)
  25.         return s, k, e
  26.    
  27.     def bfs(self, src):
  28.         visited, level = {}, {}
  29.         for i in self.alist.keys():
  30.             visited[i], level[i] = False, -1
  31.         queue = deque()
  32.         visited[src] = True
  33.         level[src] = 0
  34.         queue.append(src)
  35.         while queue:
  36.             v = queue.popleft()
  37.             for i in self.alist[v]:
  38.                 if not visited[i]:
  39.                     visited[i] = True
  40.                     queue.append(i)
  41.                     level[i] = level[v] + 1
  42.         return level
  43.    
  44.     def main(self):
  45.         self.lis = []
  46.         row = input()
  47.         while row:
  48.             self.lis.append(row)
  49.             row = input()
  50.         s, k, e = self.preprocessing()
  51.         level1 = self.bfs(s)
  52.         if level1[k]==-1:
  53.             print(-1)
  54.             return
  55.         level2 = self.bfs(k)
  56.         if level2[e]==-1:
  57.             print(-2)
  58.             return
  59.         print(level1[k]+level2[e])
  60.  
  61. if __name__=="__main__":
  62.     sol = Solution()
  63.     sol.main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement