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:
import copy

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)



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:
from sys import stdin
import queue

H, W = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split()[0] for _ in range(H)]

ans = 0

for h in range(H):
    for w in range(W):
        if maze[h][w] == '#':
            continue
        else:
            q = queue.Queue()
            q.put((h, w, 0))
            temp_h = h
            temp_w = w
            visited = [[0] * W for _ in range(H)]
            visited[h][w] = 1
            while q.qsize() > 0:
                temp = q.get()
                temp_h = temp[0]
                temp_w = temp[1]
                temp_d = temp[2]
                ans = max(ans, temp_d)
                visited[temp_h][temp_w] = 1
                if temp_h + 1 < H and maze[temp_h + 1][temp_w] == '.' and visited[temp_h + 1][temp_w] == 0:
                    # visited[temp_h + 1][temp_w] = 1
                    q.put((temp_h + 1, temp_w, temp_d + 1))
                if temp_h - 1 >= 0 and maze[temp_h - 1][temp_w] == '.' and visited[temp_h - 1][temp_w] == 0:
                    # visited[temp_h - 1][temp_w] = 1
                    q.put((temp_h - 1, temp_w, temp_d + 1))
                if temp_w + 1 < W and maze[temp_h][temp_w + 1] == '.' and visited[temp_h][temp_w + 1] == 0:
                    # visited[temp_h][temp_w + 1] = 1
                    q.put((temp_h, temp_w + 1, temp_d + 1))
                if temp_w - 1 >= 0 and maze[temp_h][temp_w - 1] == '.' and visited[temp_h][temp_w - 1] == 0:
                    # visited[temp_h][temp_w - 1] = 1
                    q.put((temp_h, temp_w - 1, temp_d + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import queue

H, W = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split()[0] for _ in range(H)]

ans = 0

for h in range(H):
    for w in range(W):
        if maze[h][w] == '#':
            continue
        else:
            q = queue.Queue()
            q.put((h, w, 0))
            temp_h = h
            temp_w = w
            visited = [[0] * W for _ in range(H)]
            while q.qsize() > 0:
                temp = q.get()
                temp_h = temp[0]
                temp_w = temp[1]
                temp_d = temp[2]
                ans = max(ans, temp_d)
                visited[temp_h][temp_w] = 1
                if temp_h + 1 < H and maze[temp_h + 1][temp_w] == '.' and visited[temp_h + 1][temp_w] == 0:
                    q.put((temp_h + 1, temp_w, temp_d + 1))
                if temp_h - 1 >= 0 and maze[temp_h - 1][temp_w] == '.' and visited[temp_h - 1][temp_w] == 0:
                    q.put((temp_h - 1, temp_w, temp_d + 1))
                if temp_w + 1 < W and maze[temp_h][temp_w + 1] == '.' and visited[temp_h][temp_w + 1] == 0:
                    q.put((temp_h, temp_w + 1, temp_d + 1))
                if temp_w - 1 >= 0 and maze[temp_h][temp_w - 1] == '.' and visited[temp_h][temp_w - 1] == 0:
                    q.put((temp_h, temp_w - 1, temp_d + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split()[0] for _ in range(H)]

ans = 0

for h in range(H):
    for w in range(W):
        if maze[h][w] == '#':
            continue
        else:
            q = deque([(h, w, 0)])
            temp_h = h
            temp_w = w
            visited = [[0] * W for _ in range(H)]
            while len(q) > 0:
                temp = q.popleft()
                temp_h = temp[0]
                temp_w = temp[1]
                temp_d = temp[2]
                ans = max(ans, temp_d)
                visited[temp_h][temp_w] = 1
                if temp_h + 1 < H and maze[temp_h + 1][temp_w] == '.' and visited[temp_h + 1][temp_w] == 0:
                    q.append((temp_h + 1, temp_w, temp_d + 1))
                if temp_h - 1 >= 0 and maze[temp_h - 1][temp_w] == '.' and visited[temp_h - 1][temp_w] == 0:
                    q.append((temp_h - 1, temp_w, temp_d + 1))
                if temp_w + 1 < W and maze[temp_h][temp_w + 1] == '.' and visited[temp_h][temp_w + 1] == 0:
                    q.append((temp_h, temp_w + 1, temp_d + 1))
                if temp_w - 1 >= 0 and maze[temp_h][temp_w - 1] == '.' and visited[temp_h][temp_w - 1] == 0:
                    q.append((temp_h, temp_w - 1, temp_d + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split()[0] for _ in range(H)]

d = [[0] * W for _ in range(H)]
ans = 0

for h in range(H):
    for w in range(W):
        q = deque([(h, w, 0)])
        if maze[h][w] == '#':
            continue
        else:
            temp_h = h
            temp_w = w
            visited = [[0] * W for _ in range(H)]
            while len(q) > 0:
                temp = q.popleft()
                temp_h = temp[0]
                temp_w = temp[1]
                temp_d = temp[2]
                ans = max(ans, temp_d)
                visited[temp_h][temp_w] = 1
                if temp_h + 1 < H and maze[temp_h + 1][temp_w] == '.' and visited[temp_h + 1][temp_w] == 0:
                    q.append((temp_h + 1, temp_w, temp_d + 1))
                if temp_h - 1 >= 0 and maze[temp_h - 1][temp_w] == '.' and visited[temp_h - 1][temp_w] == 0:
                    q.append((temp_h - 1, temp_w, temp_d + 1))
                if temp_w + 1 < W and maze[temp_h][temp_w + 1] == '.' and visited[temp_h][temp_w + 1] == 0:
                    q.append((temp_h, temp_w + 1, temp_d + 1))
                if temp_w - 1 >= 0 and maze[temp_h][temp_w - 1] == '.' and visited[temp_h][temp_w - 1] == 0:
                    q.append((temp_h, temp_w - 1, temp_d + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split()[0] for _ in range(H)]

d = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        q = deque([(h, w, 0)])
        if maze[h][w] == '#':
            continue
        else:
            temp_h = h
            temp_w = w
            visited = [[0] * W for _ in range(H)]
            while len(q) > 0:
                temp = q.popleft()
                temp_h = temp[0]
                temp_w = temp[1]
                temp_d = temp[2]
                d[h][w] = max(d[h][w], temp_d)
                visited[temp_h][temp_w] = 1
                if temp_h + 1 < H and maze[temp_h + 1][temp_w] == '.' and visited[temp_h + 1][temp_w] == 0:
                    q.append((temp_h + 1, temp_w, temp_d + 1))
                if temp_h - 1 >= 0 and maze[temp_h - 1][temp_w] == '.' and visited[temp_h - 1][temp_w] == 0:
                    q.append((temp_h - 1, temp_w, temp_d + 1))
                if temp_w + 1 < W and maze[temp_h][temp_w + 1] == '.' and visited[temp_h][temp_w + 1] == 0:
                    q.append((temp_h, temp_w + 1, temp_d + 1))
                if temp_w - 1 >= 0 and maze[temp_h][temp_w - 1] == '.' and visited[temp_h][temp_w - 1] == 0:
                    q.append((temp_h, temp_w - 1, temp_d + 1))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, d[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
h,w = map(int,input().split())
n = h*w

field = []
for i in range(h):
    field.append(input())

dist = [[INF] * n for _ in range(n)]

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        if j + 1 < w and field[i][j+1] != "#":
            dist[i * w + j][i * w + j + 1] = 1
            dist[i * w + j + 1][i * w + j] = 1
        if i + 1 < h and field[i+1][j] != "#":
            dist[i * w + j][(i+1) * w + j] = 1
            dist[(i+1) * w + j][i * w + j] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k])

ans = 0
for i in range(n):
    for j in range(n):
        if(i==j):continue
        if(dist[i][j]==INF):continue
        ans = max(ans,dist[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for s_x, s_y in  [(i, j) for i in range(h) for j in range(w)]:
    if g[s_x][s_y] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = (-1, -1)
    cur = (s_x, s_y)
    cnt = 0
    queue = deque([(cur, pre, cnt)])
    queue_pop = queue.pop
    queue_append = queue.append
    while queue:
        cur, pre, cnt = queue_pop()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        dp_cnt = dp[c_x][c_y]
        if not dp_cnt or dp_cnt > cnt:
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = (cur[0] + x, cur[1] + y)
                if next == (s_x, s_y):
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue_append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for start in  [[i, j] for i in range(h) for j in range(w)]:
    if g[start[0]][start[1]] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = [-1, -1]
    cur = start
    cnt = 0
    queue = deque([[cur, pre, cnt]])
    while queue:
        cur, pre, cnt = queue.pop()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        if not dp[c_x][c_y] or (dp[c_x][c_y] and dp[c_x][c_y] > cnt):
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = [cur[0] + x, cur[1] + y]
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue.append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)

Submission status: Time Limit Exceeded

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

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
    return max(distance_matrix)

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 itertools import product


def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    s = ["#" + _s + "#" for _s in s]
    s = ["#" * (w + 2)] + s + ["#" * (w + 2)]
    ans = 0
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for _h, _w in product(range(1, h + 1), range(1, w + 1)):
        if s[_h][_w] == "#":
            continue
        c = [[h * w] * (w + 2) for _ in range(h + 2)]
        c[_h][_w] = 0
        q = list()
        for x, y in d:
            if s[_h + x][_w + y] == ".":
                q.append((_h + x, _w + y, _h, _w))
        while q:
            cx, cy, px, py = q.pop()
            if c[px][py] + 1 >= c[cx][cy]:
                continue
            c[cx][cy] = c[px][py] + 1
            for x, y in d:
                nx = cx + x
                ny = cy + y
                if s[nx][ny] == ".":
                    q.append((nx, ny, cx, cy))
        for i, j in product(range(1, h + 1), range(1, w + 1)):
            ans = max(ans, c[i][j] * (s[i][j] == "."))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
maze = []
for i in range(H):
    s = list(input())
    maze.append(s)

def clear_maze(sx, sy, gx, gy, maze):
    INF = 100000000
    distance = [[INF for i in range(W)] for j in range(H)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []
        queue.insert(0, (sx, sy))
        distance[sx][sy] = 0

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

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

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

                if 0 <= nx and nx < H and 0 <= ny and ny < W and maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.insert(0, (nx, ny))
                        distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()

ans = 0
for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == ".":
            for gx in range(H):
                for gy in range(W):
                    if maze[gx][gy] == ".":
                        if clear_maze(sx,sy,gx,gy,maze) > ans:
                            ans = clear_maze(sx,sy,gx,gy,maze)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

# start, goal の候補
reps = []
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            reps.append([i, j])
depths = []
for k in range(len(reps)):
    for l in range(k, len(reps), 1):
        # unvisited: -1, visited: 0, goal: 1
        start = reps[k]
        goal = reps[l]
        visits = [[-1 for i in range(w)] for j in range(h)]
        visits[goal[0]][goal[1]] = 1
        queue = [[reps[k]]]
        depth = 0

        while True:
            clear = False
            tmp_queue = []
            for now in queue.pop(0):
                # 1. まず、ゴールに到着しているか確認する
                # 2-1. していれば、その start, goal の組における最短経路が計算できたので、depths に追加する
                # 2-2. していなければ、自分のいるマスを訪問済みにし、次に進む道の候補を挙げて、それらを queue に突っ込む

                if visits[now[0]][now[1]] == 1:
                    clear = True
                    break
                else:
                    visits[now[0]][now[1]] = 0
                if (now[0] <= (h - 2)):
                    if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                        tmp_queue.append([(now[0] + 1), now[1]])
                if (now[1] <= (w - 2)):
                    if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                        tmp_queue.append([now[0], (now[1] + 1)])
                if (1 <= now[0]):
                    if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                        tmp_queue.append([(now[0] - 1), now[1]])
                if (1 <= now[1]):
                    if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                        tmp_queue.append([now[0], (now[1] - 1)])
            if clear:
                break
            else:
                depth += 1
                queue.append(tmp_queue)
        depths.append(depth)
print(max(depths))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
S = [['#']*(w+2)]

for _ in range(h):
    s = str(input())
    new_s = ['#']
    for x in s:
        new_s.append(x)
    new_s.append('#')
    S.append(new_s)
S.append(['#']*(w+2))

Possible_list = []
for i in range(h+2):
    for j in range(w+2):
        if S[i][j] == '.':
            Possible_list.append((i,j))

max_length = 0

for zahyou in Possible_list:
    dq = deque()
    Visited = [-1 for _ in range(len(Possible_list))]
    Visited[Possible_list.index(zahyou)] = 0
    dq.append(zahyou)
    
    while dq:
        now = dq.popleft()
        
        Adj_possible = []
        if (now[0]-1, now[1]) in Possible_list:
            Adj_possible.append((now[0]-1, now[1]))
        if (now[0]+1, now[1]) in Possible_list:
            Adj_possible.append((now[0]+1, now[1]))
        if (now[0], now[1]-1) in Possible_list:
            Adj_possible.append((now[0], now[1]-1))
        if (now[0], now[1]+1) in Possible_list:
            Adj_possible.append((now[0], now[1]+1))
        
        for next_zahyou in Adj_possible:
            if Visited[Possible_list.index(next_zahyou)] != -1:
                continue
            Visited[Possible_list.index(next_zahyou)] = Visited[Possible_list.index(now)] + 1
            dq.append(next_zahyou)
    
    max_length = max(max_length, max(Visited))

print(max_length)

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

reps = []
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            reps.append([i, j])
depths = []
for k in range(len(reps)):
    for l in range(k, len(reps), 1):
        start = reps[k]
        goal = reps[l]
        visits = [[-1 for i in range(w)] for j in range(h)]
        visits[goal[0]][goal[1]] = 1
        queue = [reps[k]]
        depth = 0

        while True:
            clear = False
            tmp_queue = []
            for now in queue:
                if visits[now[0]][now[1]] == 1:
                    clear = True
                    break
                else:
                    visits[now[0]][now[1]] = 0
                if (now[0] <= (h - 2)):
                    if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                        tmp_queue.append([(now[0] + 1), now[1]])
                if (now[1] <= (w - 2)):
                    if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                        tmp_queue.append([now[0], (now[1] + 1)])
                if (1 <= now[0]):
                    if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                        tmp_queue.append([(now[0] - 1), now[1]])
                if (1 <= now[1]):
                    if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                        tmp_queue.append([now[0], (now[1] - 1)])
            if clear:
                break
            else:
                depth += 1
                queue = tmp_queue
        depths.append(depth)
print(max(depths))

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
s = []
s.append("".join(["#" for i in range(w + 2)]))
for i in range(h):
    s.append("#" + input().strip() + "#")
s.append("".join(["#" for i in range(w + 2)]))

reps = []
for i in range(h + 2):
    for j in range(w + 2):
        if s[i][j] == ".":
            reps.append([i, j])
depths = []
for k in range(len(reps)):
    for l in range(k, len(reps), 1):
        start = reps[k]
        goal = reps[l]
        visits = [[-1 for i in range(w + 2)] for j in range(h + 2)]
        visits[goal[0]][goal[1]] = 1
        queue = [reps[k]]
        depth = 0

        while True:
            clear = False
            tmp_queue = []
            for now in queue:
                if visits[now[0]][now[1]] == 1:
                    clear = True
                    break
                else:
                    visits[now[0]][now[1]] = 0
                if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                    tmp_queue.append([(now[0] + 1), now[1]])
                if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                    tmp_queue.append([now[0], (now[1] + 1)])
                if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                    tmp_queue.append([(now[0] - 1), now[1]])
                if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                    tmp_queue.append([now[0], (now[1] - 1)])
            if clear:
                break
            else:
                depth += 1
                queue = tmp_queue
        depths.append(depth)
print(max(depths))

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
s = []
s.append("".join(["#" for i in range(w + 2)]))
for i in range(h):
    s.append("#" + input().strip() + "#")
s.append("".join(["#" for i in range(w + 2)]))

reps = []
for i in range(h + 2):
    for j in range(w + 2):
        if s[i][j] == ".":
            reps.append([i, j])
depths = []
for start in reps:
    for goal in reps:
        visits = [[-1 for i in range(w + 2)] for j in range(h + 2)]
        visits[goal[0]][goal[1]] = 1
        queue = [start]
        depth = 0

        while True:
            clear = False
            tmp_queue = []
            for now in queue:
                if visits[now[0]][now[1]] == 1:
                    clear = True
                    break
                else:
                    visits[now[0]][now[1]] = 0
                if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                    tmp_queue.append([(now[0] + 1), now[1]])
                if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                    tmp_queue.append([now[0], (now[1] + 1)])
                if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                    tmp_queue.append([(now[0] - 1), now[1]])
                if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                    tmp_queue.append([now[0], (now[1] - 1)])
            if clear:
                break
            else:
                depth += 1
                queue = tmp_queue
        depths.append(depth)
print(max(depths))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF = float('inf') 
(H, W) = list(map(int,input().split()))
# print(H,W)

S = []
N = H * W
c = [[INF for j in range(N)] for u in range(N)]
d = [[INF for j in range(H*W)] for u in range(H*W)]

for k in range(N):
    c[k][k] = 0
    d[k][k] = 0

for i in range(H):
    S.append(input())

#print(S)

def vindex(i,j):
    global W
    return W * (i-1) + j -1

# print(vindex(H,W))
for i in range(1,H+1):
    for j in range(1,W+1):
        index = vindex(i,j)
        s = S[i-1][j-1]
        # print(index,s)
        if i != 1:
            index_t = vindex(i-1,j)
            sup = S[i-2][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
                
        if i != H:
            index_t = vindex(i+1,j)
            sup = S[i][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != 1:
            index_t = vindex(i,j-1)
            sup = S[i-1][j-2]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != W:
            index_t = vindex(i,j+1)
            sup = S[i-1][j]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1

#print("D",d)


for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j] , d[i][k]+d[k][j])
    #print(k,d)

ans = 0 
for i in range(N):
    for j in range(N):

        if (d[i][j] != INF and d[i][j] > ans):
            ans = d[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
INF = 100000000

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

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

def bfs(sx, sy, gx, gy):
    d = [[INF for i in range(W)] for j in range(H)]
    d[sx][sy] = 0

    q = queue.Queue()
    q.put([sx, sy])

    while not q.empty():
        p = q.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx) & (nx < H) & (0 <= ny) & (ny < W):
                if (S[nx][ny] != "#") & (d[nx][ny] == INF):
                    d[nx][ny] = min(d[nx][ny], d[p[0]][p[1]] + 1)
                    q.put([nx, ny])

    if d[gx][gy] == INF:
        return 0
    else:
        return d[gx][gy]

res = 0
for sx in range(H):
    for sy in range(W):
        for gx in range(H):
            for gy in range(W):
                res = max(res, bfs(sx, sy, gx, gy))

print(res)

Submission status: Time Limit Exceeded

Solution code:
def bfs(start, goal, maze, visited):
    queue = [start]
    visited[start[0]][start[1]] = True
    dist = {(start[0], start[1]): 0}
    while queue:
        y, x = queue.pop(0)
        if y == goal[0] and x == goal[1]:
            return dist[(y, x)]
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x_, y_ = x + i, y + j
            if y_ >= 0 and y_ < h and x_ >= 0 and x_ < w and maze[y_][x_] == "." and not visited[y_][x_]:
                queue.append((y_, x_))
                visited[y_][x_] = True
                dist[y_, x_] = dist[y, x] + 1


h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
max_dist = 0
for sy in range(h):
    for sx in range(w):
        for gy in range(h):
            for gx in range(w):
                if maze[sy][sx] == "." and maze[gy][gx] == ".":
                    visited = [[False for _ in range(w)] for _ in range(h)]
                    max_dist = max(max_dist, bfs(
                        (sy, sx), (gy, gx), maze, visited))
print(max_dist)

Submission status: Time Limit Exceeded

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

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
    return max(distance_matrix)

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)