Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- import sys
- class Solution:
- def preprocessing(self):
- self.alist = {}
- moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
- is_valid = lambda r, c: 0<=r<len(self.lis) and 0<=c<len(self.lis[0]) and self.lis[r][c] in (' ', '*')
- s, k, e = (0, 0), (0, 0), (0, 0)
- for i in range(len(self.lis)):
- for j in range(len(self.lis[0])):
- if self.lis[i][j] in (' ', '*'):
- self.alist[(i, j)] = []
- for move in moves:
- r, c = i+move[0], j+move[1]
- if is_valid(r, c):
- self.alist[(i, j)].append((r, c))
- if j==0 and self.lis[i][j]==' ':
- s = (i, j)
- if j==len(self.lis[0])-1 and self.lis[i][j]==' ':
- e = (i, j)
- if self.lis[i][j]=='*':
- k = (i, j)
- return s, k, e
- def bfs(self, src):
- visited, level = {}, {}
- for i in self.alist.keys():
- visited[i], level[i] = False, -1
- queue = deque()
- visited[src] = True
- level[src] = 0
- queue.append(src)
- while queue:
- v = queue.popleft()
- for i in self.alist[v]:
- if not visited[i]:
- visited[i] = True
- queue.append(i)
- level[i] = level[v] + 1
- return level
- def main(self):
- self.lis = []
- row = input()
- while row:
- self.lis.append(row)
- row = input()
- s, k, e = self.preprocessing()
- level1 = self.bfs(s)
- if level1[k]==-1:
- print(-1)
- return
- level2 = self.bfs(k)
- if level2[e]==-1:
- print(-2)
- return
- print(level1[k]+level2[e])
- if __name__=="__main__":
- sol = Solution()
- sol.main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement