Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import queue
- import sys
- vetx = [-1, 0, 1, 0]
- vety = [ 0, 1, 0,-1]
- def bfs(x , y, n, m, mt, dist):
- dist[x][y] = 0
- q = queue.Queue()
- q.put([x, y])
- md = -1 #armazena a maior distancia da origem
- sv = [-1, -1] #armazena o vertice com maior distancia da origem
- while not q.empty():
- u = q.get()
- for i in range (4):
- nx = u[0]+vetx[i]
- ny = u[1]+vety[i]
- if(nx>=0 and nx<n and ny>=0 and ny<m and dist[nx][ny]==-1 and mt[nx][ny]=='.'):
- dist[nx][ny] = dist[u[0]][u[1]] + 1
- if(dist[nx][ny]>md):
- md = dist[nx][ny]
- sv = [nx, ny]
- q.put([nx, ny])
- return [sv, md]
- if(__name__ == "__main__"):
- n, m = list(map(int,sys.stdin.readline().split(' ')))
- while n or m:
- mt = [" "] * n #crianda a matrix de char
- dist = [[-1 for i in range(m)] for i in range(n)] # criando a matrix de distancia
- dist2 = [[-1 for i in range(m)] for i in range(n)] # criando a matrix de dintancia auxiliar
- for i in range (n): #lendo o mapa
- mt[i] = sys.stdin.readline()
- ini = [-1, -1]
- for i in range(n):
- for j in range(m):
- if(mt[i][j]=='.'):
- ini = [i, j]
- break
- if(ini[0] != -1):
- break
- ax = bfs(ini[0], ini[1], n, m, mt, dist)
- ans = bfs(ax[0][0], ax[0][1], n, m, mt, dist2)
- sys.stdout.write(str(ans[1])+"\n")
- n, m = list(map(int,sys.stdin.readline().split(' ')))
Advertisement
Add Comment
Please, Sign In to add comment