Problem:


Score : 400 points

Problem Statement

Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.

The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
area = []
h += 2
w += 2
INF = 1000

for i in range(h):
    if i == 0 or i == h-1:
        array = ['#'] * w
    else:
        array = list(input())
        array.insert(0, '#')
        array.append('#')
    area.append(array)

line = []
for i in range(h):
    for j in range(w):
        if area[i][j] == '#':
            line.append(INF)
        else:
            line.append(1)


def bfs(start):
    unsearched_points = deque()
    searched_points = deque()
    distance_matrix = [INF for _ in range(h*w)]
    unsearched_points.append(start)
    distance_matrix[start] = 0
    while len(unsearched_points) > 0:
        current_point = unsearched_points.popleft()
        searched_points.append(current_point)
        for move in (-1, 1, -w, w):
            if line[current_point+move] == 1 and current_point+move not in searched_points:
                unsearched_points.append(current_point+move)
                distance_matrix[current_point+move] = distance_matrix[current_point] + 1
    l = [x for x in distance_matrix if x < INF]
    return max(l)

max_distance = 0
for i in range(len(line)-w):
    if line[i] == INF:
        continue
    else:
        distance = bfs(i)
        if max_distance < distance:
            max_distance = distance

print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0

for h in range(H):
  for w in range(W):
    if m[h][w] == "#": continue
    q = deque([(h, w, 0)])
    used = set()
    while q:
      h, w, c = q.popleft()
      ans = max(ans, c)
      if 0 <= h-1 and m[h-1][w] == "." and (h-1, w) not in used: q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == "." and (h+1, w) not in used: q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == "." and (h, w-1) not in used: q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == "." and (h, w+1) not in used: q.append((h, w+1, c+1))
      used.add((h, w))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
maxc = 0

for h in range(H):
  for w in range(W):
    if M[h][w] == "#": continue
    m = deepcopy(M)
    q = deque([(h, w, 0)])
    while q:
      h, w, c = q.popleft()
      maxc = max(maxc, c)
      if 0 <= h-1 and m[h-1][w] == ".": q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == ".": q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == ".": q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == ".": q.append((h, w+1, c+1))
      m[h][w] = "#"
print(maxc)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, h, w, si, sj, gi, gj):
    memo = [[0] * w for i in range(h)]
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        if i == gi and j == gj:
            return score[gi][gj]
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])

h, w = map(int, input().split())
maze = [input() for i in range(h)]
memo = []
scores = []
for si in range(h):
    for sj in range(w):
        if maze[si][sj] == "#":
            continue
        for gi in range(h):
            for gj in range(w):
                if maze[gi][gj] == "#" or (si == gi and sj == gj) or (gi, gj) in memo:
                    continue
                scores.append(bfs(maze, h, w, si, sj, gi, gj))
print(max(scores))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, h, w, si, sj, gi, gj):
    memo = [[0] * w for i in range(h)]
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        if i == gi and j == gj:
            return score[gi][gj]
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])

h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si in range(h):
    for sj in range(w):
        if maze[si][sj] == "#":
            continue
        for gi in range(h):
            for gj in range(w):
                if maze[gi][gj] == "#" or (si == gi and sj == gj):
                    continue
                scores.append(bfs(maze, h, w, si, sj, gi, gj))
print(max(scores))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(input())
res = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] != '.':
            continue
        visited = []
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)
            visited.append((c_i, c_j))
            for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
                if 0 <= n_i < h and 0 <= n_j < w and grid[n_i][n_j] == '.' and (n_i, n_j) not in visited:
                    queue.append((n_i, n_j, level + 1))
        res = max(res, level)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split(" "))
s = [input() for _ in range(h)]

ans = 0
direcion = [(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        que = deque([(j,i)])
        dist = [[0]*w for _ in range(h)]
        visited = [[0]*w for _ in range(h)]
        visited[i][j] = 1
        while que:
            j, i = que.popleft()
            for x,y in direcion:
                n_x,n_y = j+x,i+y
                if not 0 <= n_x < w: continue
                if not 0 <= n_y < h: continue
                if visited[n_y][n_x]: continue
                if s[n_y][n_x] == "#": continue
                visited[n_y][n_x] = 1
                dist[n_y][n_x] = dist[i][j] + 1
                que.append((n_x,n_y))
            ans = max(ans,max(max(row) for row in dist))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()

    M = [input() for i in range(H)]

    def search(y, x):
        q = []
        m = [[0]*W for i in range(H)]

        q = deque([(y,x, 0)])
        ans = 0
        while q:
            y, x, k = q.popleft()
            m[y][x] = 1
            ans = max(ans, k)
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                yy = y + i
                xx = x + j

                if 0 <= xx < W and 0 <= yy < H:
                    if M[yy][xx] == "." and m[yy][xx] == 0:
                        q.append((yy, xx, k+1))

        return ans

    ans = 0
    for y in range(H):
        for x in range(W):
            if M[y][x] == ".":
                ans = max(ans, search(y, x))
    print(ans)
if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy
import heapq
import math
import fractions

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


h,w = ips()
pre  = '#'*(w+2)
board = [pre]
road = h*w
for i in range(h):
    a = input()
    road-=a.count('#')
    a = ''.join(['#',a,'#'])
    board.append(a)
board.append(pre)
maxsteps = 0
bh = h+2
bw = w+2
for by in range(1,h+1):
    for bx in range(1,w+1):
        que = []
        checked = []

        if board[by][bx] == '.':
            #print("start",by,bx,by*bw+bx)
            que = []
            checked = [bw*by+bx]
            steps = 0
            if board[by][bx - 1] == '.':que.append([by,bx-1])
            if board[by][bx + 1] == '.':que.append([by,bx+1])
            if board[by - 1][bx] == '.':que.append([by-1,bx])
            if board[by + 1][bx] == '.':que.append([by+1,bx])
            while len(que):
                next = len(que)
                oldque = copy.copy(que)
                que = copy.copy([])
                for i in range(len(oldque)):
                    y,x = oldque.pop(-1) #need to change here
                    checked.append(y*bw+x)
                    if board[y][x - 1] == '.' and bw*y+x-1 not in checked: que.append([y, x - 1])
                    if board[y][x + 1] == '.' and bw*y+x+1 not in checked: que.append([y, x + 1])
                    if board[y - 1][x] == '.' and bw*(y-1)+x not in checked: que.append([y - 1, x])
                    if board[y + 1][x] == '.' and bw*(y+1)+x not in checked: que.append([y + 1, x])
                steps+=1
                #print("che",checked)
                #print("que",que)
            maxsteps = max(steps,maxsteps)
print(maxsteps)

Submission status: Time Limit Exceeded

Solution code:
import copy
import heapq
import math
import fractions

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


h,w = ips()
pre  = '#'*(w+2)
board = [pre]
road = h*w
for i in range(h):
    a = input()
    road-=a.count('#')
    a = ''.join(['#',a,'#'])
    board.append(a)
board.append(pre)
maxsteps = 0
bh = h+2
bw = w+2
for by in range(1,h+1):
    for bx in range(1,w+1):
        que = []
        checked = []

        if board[by][bx] == '.':
            #print("start",by,bx,by*bw+bx)
            que = []
            checked = [bw*by+bx]
            steps = 0
            if board[by][bx - 1] == '.':que.append([by,bx-1])
            if board[by][bx + 1] == '.':que.append([by,bx+1])
            if board[by - 1][bx] == '.':que.append([by-1,bx])
            if board[by + 1][bx] == '.':que.append([by+1,bx])
            while len(que):
                next = len(que)
                for i in range(len(que)):
                    y,x = que.pop(0)
                    checked.append(y*bw+x)
                    if board[y][x - 1] == '.' and bw*y+x-1 not in checked: que.append([y, x - 1])
                    if board[y][x + 1] == '.' and bw*y+x+1 not in checked: que.append([y, x + 1])
                    if board[y - 1][x] == '.' and bw*(y-1)+x not in checked: que.append([y - 1, x])
                    if board[y + 1][x] == '.' and bw*(y+1)+x not in checked: que.append([y + 1, x])
                steps+=1
                #print("che",checked)
                #print("que",que)
            maxsteps = max(steps,maxsteps)
print(maxsteps)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ss = []
for i in range(n):
    s = input()
    ss.append(s)


def bff(src : tuple):
    global ss
    global n, m
    d = [[1e18] * m for i in range(n)]

    # src init
    if ss[src[0]][src[1]] == '#':
        return 0

    d[src[0]][src[1]] = 0

    for itr in range(n * m):
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                u = (i, j)
                if u[0] not in range(0, n) or u[1] not in range(0, m):
                    continue
                v = [(i - 1, j), (i, j - 1)]

                for vv in v:
                    if (vv[0] not in range(n) or vv[1] not in range(m)):
                        continue

                    xx = ss[vv[0]][vv[1]]
                    yy = ss[u[0]][u[1]]
                    if ss[vv[0]][vv[1]] == '#' or ss[u[0]][u[1]] == '#':
                        continue
                    if d[u[0]][u[1]] > d[vv[0]][vv[1]] + 1:
                        d[u[0]][u[1]] = d[vv[0]][vv[1]] + 1

                    if d[vv[0]][vv[1]] > d[u[0]][u[1]] + 1:
                        d[vv[0]][vv[1]] = d[u[0]][u[1]] + 1
    ans = 0
    for i in d:
        for j in i:
            if j != 1e18:
                ans = max(ans, j)
    return ans

fans = -1
for i in range(n):
    for j in range(m):

        d = bff((i, j))
        fans = max(fans, d)

print(fans)

Submission status: Time Limit Exceeded

Solution code:
#input
H, W = map(int, input().split())
import numpy as np
S = np.array([input() for _ in range(H)])

#output
import numpy as np

INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
#input
H, W = map(int, input().split())
import numpy as np
S = np.array([input() for _ in range(H)])

#output
import numpy as np
from collections import deque
INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
#input
H, W = map(int, input().split())
import numpy as np
S = np.array([input() for _ in range(H)])

#output
import numpy as np
from collections import deque
INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
grid = [[c for c in input()] for _ in range(N)]
mat = [[float(N*M)]*(M*N) for _ in range(N*M)]

DX = [0, 0, 1, -1]
DY = [-1, 1, 0, 0]
for row in range(N):
    for col in range(M):
        if grid[row][col] == "#":
            continue
        for dx, dy in zip(DX, DY):
            if 0 <= row+dx < N and 0 <= col+dy < M:
                if grid[row+dx][col+dy] == "#":
                    continue
                mat[(row+dx)*M+col+dy][row*M+col] = 1
                mat[row*M+col][(row+dx)*M+col+dy] = 1
for k in range(N*M):
    for i in range(N*M):
        for j in range(N*M):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
ans = 0
for i in range(N*M):
    for j in range(N*M):
        if mat[i][j] != N*M:
            ans = max(ans, mat[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
#A = [list(map(str,input().split())) for i in range(H)]
A = [list(input()) for i in range(H)]

from queue import Queue
#from collections import deque

dj = [1, 0, -1, 0]
di = [0, 1, 0, -1]

sum_sharp = sum([A[i].count('#') for i in range(H)])

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        #print(s_i,s_j)
        d_max = 0
        q_i = Queue()
        #q_i = deque()
        q_j = Queue()
        #q_j = deque()
        D = [[-1]*W for i in range(H)]
        #flag = [[0]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            q_i.put(s_i)
            #q_i.append(s_i)
            q_j.put(s_j)
            #q_j.append(s_j)
            #while sum(map(sum, flag)) != W*H - sum_sharp:
            #while flag < W*H - sum_sharp:
            while q_i.empty() == False:
            #while len(q_i)!=0:
            #for a in range(W*H):
                i = q_i.get()
                #i = q_i.popleft()
                j = q_j.get()
                #j = q_j.popleft()
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    #if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or 0<=D[ni][nj]<D[i][j]+1:
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or D[ni][nj]!=-1:
                    #if ni<0 or ni>=H or nj<0 or nj>=W:
                        continue
                    #elif A[ni][nj]== '#' or D[ni][nj] < D[i][j]+1:
                        #flag[ni][nj] = 1
                        #continue
                    else:
                        #if D[ni][nj] == -1:
                            #print(flag)
                        flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        q_i.put(ni)
                        #q_i.append(ni)
                        #q_j.append(nj)
                        q_j.put(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
inf=10**3
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))
import collections
def dist(a,b):
  D=[[inf]*(w+2) for _ in range(h+2)]
  D[a][b]=0
  Visit=collections.deque()
  Visit.append(100*a+b)
  while Visit:
    v=Visit.pop()
    va,vb=v//100,v%100
    for dx,dy in d:
      if S[va+dx][vb+dy]=="." and D[va+dx][vb+dy]>D[va][vb]+1:
        Visit.append((va+dx)*100+(vb+dy))
        D[va+dx][vb+dy]=D[va][vb]+1
  ret=0
  for i in range(h):
    for j in range(w):
      if D[i+1][j+1]<inf:
        ret=max(ret,D[i+1][j+1])
  return ret
ans=0
for i in range(h):
  for j in range(w):
    if S[i+1][j+1]==".":
      ans=max(dist(i+1,j+1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
inf=10**3
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))
import collections
def dist(a,b):
  D=[[inf]*(w+2) for _ in range(h+2)]
  D[a][b]=0
  Visit=collections.deque()
  Visit.append(100*a+b)
  while Visit:
    v=Visit.pop()
    va,vb=v//100,v%100
    for dx,dy in d:
      if S[va+dx][vb+dy]=="#":
        continue
      elif D[va+dx][vb+dy]>D[va][vb]+1:
        Visit.append((va+dx)*100+(vb+dy))
        D[va+dx][vb+dy]=D[va][vb]+1
  ret=0
  for i in range(h):
    for j in range(w):
      if D[i+1][j+1]<inf:
        ret=max(ret,D[i+1][j+1])
  return ret
ans=0
for i in range(h):
  for j in range(w):
    if S[i+1][j+1]==".":
      ans=max(dist(i+1,j+1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
inf=10**3
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))
import collections
def dist(a,b):
  if S[a][b]=="#":
    return 0
  else:
    D=[[inf]*(w+2) for _ in range(h+2)]
    D[a][b]=0
    Visit=collections.deque()
    Visit.append(100*a+b)
    while Visit:
      v=Visit.pop()
      va,vb=v//100,v%100
      for dx,dy in d:
        if S[va+dx][vb+dy]=="#":
          continue
        elif D[va+dx][vb+dy]>D[va][vb]+1:
          Visit.append((va+dx)*100+(vb+dy))
          D[va+dx][vb+dy]=D[va][vb]+1
    ret=0
    for i in range(h):
      for j in range(w):
        if D[i+1][j+1]<inf:
          ret=max(ret,D[i+1][j+1])
    return ret
ans=0
for i in range(h):
  for j in range(w):
    ans=max(dist(i+1,j+1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
inf=float("inf")
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))
import collections
def dist(a,b):
  if S[a][b]=="#":
    return 0
  else:
    D=[[inf]*(w+2) for _ in range(h+2)]
    D[a][b]=0
    Visit=collections.deque()
    Visit.append(100*a+b)
    while Visit:
      v=Visit.pop()
      va,vb=v//100,v%100
      for dx,dy in d:
        if S[va+dx][vb+dy]=="#":
          continue
        elif D[va+dx][vb+dy]>D[va][vb]+1:
          Visit.append((va+dx)*100+(vb+dy))
          D[va+dx][vb+dy]=D[va][vb]+1
    ret=0
    for i in range(h):
      for j in range(w):
        if D[i+1][j+1]<inf:
          ret=max(ret,D[i+1][j+1])
    return ret
ans=0
for i in range(h):
  for j in range(w):
    ans=max(dist(i+1,j+1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
inf=float("inf")
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))

def dist(a,b):
  if S[a][b]=="#":
    return 0
  else:
    D=[[inf]*(w+2) for _ in range(h+2)]
    D[a][b]=0
    Visit=[100*a+b]
    while Visit:
      v=Visit.pop()
      va,vb=v//100,v%100
      for dx,dy in d:
        if S[va+dx][vb+dy]=="#":
          continue
        elif D[va+dx][vb+dy]>D[va][vb]+1:
          Visit.append((va+dx)*100+(vb+dy))
          D[va+dx][vb+dy]=D[va][vb]+1
    ret=0
    for i in range(h):
      for j in range(w):
        if D[i+1][j+1]<inf:
          ret=max(ret,D[i+1][j+1])
    return ret
ans=0
for i in range(h):
  for j in range(w):
    ans=max(dist(i+1,j+1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import copy
import numpy as np

def getmax(H2, W2, S):
    T=copy.deepcopy(S)
    lp=True
    st=np.max(T)
    while lp:
        lp=False
        for i in range(1,H2-1):
            for j in range(1,W2-1):
                if (T[i][j]==0 and \
                    ( T[i-1][j]==st or \
                      T[i][j-1]==st or \
                      T[i+1][j]==st or \
                      T[i][j+1]==st)):
                    T[i][j]=st+1
                    lp=True
        st+=1
    return(np.max(T))

def solve(H2, W2, S):
    #try1
    lp=True

    ans=0
    for i in range(1,H2-1):
        for j in range(1,W2-1):
            if S[i][j]==-1:
                continue
            if S[i][j]==0:
                S[i][j]=1
                ans=max(ans, getmax(H2, W2, S))
                S[i][j]=0

    print(ans-1)
    return

def main():
    H, W = map(int, input().split())
    SS=[[-1 for _ in range(W+2)] for _ in range(H+2)]
    S=[]
    for _ in range(H):
        S.append(list(input()))
    for i in range(H):
        for j in range(W):
            SS[i+1][j+1]=0 if S[i][j]=="." else -1
    solve(H+2, W+2, SS)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import Queue


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_y in range(H):
        for start_x in range(W):
            if S[start_y][start_x] == '#':
                continue
            costs = [[0 for w in range(W)] for h in range(H)]
            queue = Queue()
            queue.put((start_y, start_x, 1))
            cost = 1
            while not queue.empty():
                (y, x, c) = queue.get()
                if costs[y][x] != 0:
                    continue
                # print("({},{}): {}".format(y, x, c))
                costs[y][x] = c
                cost = c
                for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if 0 <= next_y < H and 0 <= next_x < W and S[next_y][next_x] == '.':
                        queue.put((next_y, next_x, c + 1))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import copy
import numpy as np

def getmax(H2, W2, S):
    T=copy.deepcopy(S)
    Tn=copy.deepcopy(S)
    lp=True
    st=0
    while lp:
        lp=False
        for i in range(1,H2-1):
            for j in range(1,W2-1):
                if T[i][j]==0:
                    if (T[i-1][j]<1 and
                        T[i][j-1]<1 and
                        T[i+1][j]<1 and
                        T[i][j+1]<1):
                        continue
                    Tn[i][j]=max(T[i-1][j],T[i][j-1],T[i+1][j],T[i][j+1])+1
                    lp=True
        T=copy.deepcopy(Tn)
    return(np.max(T))

def solve(H2, W2, S):
    #try1
    lp=True

    ans=0
    for i in range(1,H2-1):
        for j in range(1,W2-1):
            if S[i][j]==-1:
                continue
            if S[i][j]==0:
                S[i][j]=1
                ans=max(ans, getmax(H2, W2, S))
                S[i][j]=0

    print(ans-1)
    return

def main():
    H, W = map(int, input().split())
    SS=[[-1 for _ in range(W+2)] for _ in range(H+2)]
    S=[]
    for _ in range(H):
        S.append(list(input()))
    for i in range(H):
        for j in range(W):
            SS[i+1][j+1]=0 if S[i][j]=="." else -1
    solve(H+2, W+2, SS)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import Queue


def get_costs(S):
    costs = [[0 for w in range(len(S[0]))] for h in range(len(S))]
    for h in range(len(S)):
        for w in range(len(S[0])):
            if S[h][w] == '#':
                costs[h][w] = -1
    return costs


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_y in range(H):
        for start_x in range(W):
            if S[start_y][start_x] == '#':
                continue
            costs = get_costs(S)
            queue = Queue()
            queue.put((start_y, start_x, 1))
            cost = 1
            while not queue.empty():
                (y, x, c) = queue.get()
                # print("({},{}): {}".format(y, x, c))
                costs[y][x] = c
                cost = c
                for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if 0 <= next_y < H and 0 <= next_x < W and S[next_y][next_x] == '.' and costs[next_y][next_x] == 0:
                        queue.put((next_y, next_x, c + 1))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()