suehtamfr

beecrowd 1621

Dec 4th, 2023 (edited)
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.42 KB | Source Code | 0 0
  1. import queue
  2. import sys
  3.  
  4. vetx = [-1, 0, 1, 0]
  5. vety = [ 0, 1, 0,-1]
  6.  
  7. def bfs(x , y, n, m, mt, dist):
  8.   dist[x][y] = 0
  9.   q = queue.Queue()
  10.   q.put([x, y])
  11.   md = -1 #armazena a maior distancia da origem
  12.   sv = [-1, -1] #armazena o vertice com maior distancia da origem
  13.   while not q.empty():
  14.     u = q.get()
  15.     for i in range (4):
  16.       nx = u[0]+vetx[i]
  17.       ny = u[1]+vety[i]
  18.       if(nx>=0 and nx<n and ny>=0 and ny<m and dist[nx][ny]==-1 and mt[nx][ny]=='.'):
  19.         dist[nx][ny] = dist[u[0]][u[1]] + 1
  20.         if(dist[nx][ny]>md):
  21.           md = dist[nx][ny]
  22.           sv = [nx, ny]
  23.         q.put([nx, ny])
  24.   return [sv, md]
  25.  
  26. if(__name__ == "__main__"):
  27.   n, m = list(map(int,sys.stdin.readline().split(' ')))
  28.   while n or m:
  29.     mt = [" "] * n #crianda a matrix de char
  30.     dist  = [[-1 for i in range(m)] for i in range(n)] # criando a matrix de distancia
  31.     dist2 = [[-1 for i in range(m)] for i in range(n)] # criando a matrix de dintancia auxiliar
  32.     for i in range (n): #lendo o mapa
  33.       mt[i] = sys.stdin.readline()
  34.    
  35.     ini = [-1, -1]
  36.     for i in range(n):
  37.       for j in range(m):
  38.         if(mt[i][j]=='.'):
  39.           ini = [i, j]
  40.           break
  41.       if(ini[0] != -1):
  42.         break
  43.     ax  = bfs(ini[0], ini[1], n, m, mt, dist)
  44.     ans = bfs(ax[0][0], ax[0][1], n, m, mt, dist2)
  45.     sys.stdout.write(str(ans[1])+"\n")
  46.     n, m = list(map(int,sys.stdin.readline().split(' ')))
Advertisement
Add Comment
Please, Sign In to add comment