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 collections
h,w = map(int, input().split())
s=[input()for _ in range(h)]
r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = [[] for _ in range(h*w)]
    que[0].append([i,j])
    for k in range(h*w):
        if que[k]:
            res = k
            for i,j in que[k]:
                f[i*w+j] =k
                for sr in r:
                    ti = i + sr[0]
                    tj = j + sr[1]
                    if ti>=0 and tj>=0 and ti<h and tj<w:
                        if s[ti][tj] == ".":
                            if f[ti*w+tj] == -1:
                                que[k+1].append([ti,tj])
    return res

res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            res = max(res,bfs(i,j))
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []

def bfs(a, b):
	Q = [[a, b, 0]]
	d_lst = [[4000 for _ in range(W)] for _ in range(H)]
	while Q:
		cur = Q.pop(0)
		y, x, d = cur[0], cur[1], cur[2]
		if S[y][x] == "#": continue
		d_lst[y][x] = min(d_lst[y][x], d)
		
		if x > 0 and d + 1 < d_lst[y][x - 1]:
			Q.append([y, x - 1, d + 1])
		if x < W - 1 and d + 1 < d_lst[y][x + 1]:
			Q.append([y, x + 1, d + 1])
		if y > 0 and d + 1 < d_lst[y - 1][x]:
			Q.append([y - 1, x, d + 1])
		if y < H - 1 and d + 1 < d_lst[y + 1][x]:
			Q.append([y + 1, x, d + 1])
	
	ans = 0
	for i in range(H):
		for j in range(W):
			if S[i][j] == "#": continue
			ans = max(ans, d_lst[i][j])
	return ans
		

for i in range(H):
	tmp = list(map(str, input()))
	S.append(tmp)
	
res = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == "#": continue
		res = max(res, bfs(i, j))
		
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    for start_i in range(len(points) - 1):
        way = []
        for goal_i in reversed(list(range(start_i + 1, len(points)))):
            if goal_i in way:
                continue
            step, way = count_step(MAP, points[start_i], points[goal_i])
            if step > max_step:
                max_step = step

    print(max_step)


MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def count_step(MAP, start, goal):
    candidates = [(start, get_distance(start, goal), 0, [start])]

    checked = {}
    while True:
        pos, _, step, way = candidates.pop(0)
        for m in MOVES:
            next_pos = (pos[0] + m[0], pos[1] + m[1])
            if next_pos in checked:
                continue
            if not is_valid(MAP, next_pos):
                continue
            checked[next_pos] = True
            new_way = list(way)
            new_way.append(next_pos)
            distance = get_distance(next_pos, goal)
            if distance == 0:
                return step + 1, new_way
            candidates.append((next_pos, distance, step + 1, new_way))
        candidates.sort(key=lambda x: x[1] + x[2])


def get_distance(p, goal):
    return abs(p[0] - goal[0]) + abs(p[1] - goal[1])


def is_valid(MAP, pos):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= len(MAP) or pos[1] >= len(MAP[0]):
        return False

    if MAP[pos[0]][pos[1]] == '#':
        return False
    return True


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
h,w = map(int, input().split())
s=[input()for _ in range(h)]
r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i*w+j,0]])
    while que:
        ij,k = que.popleft()
        i = ij//w
        j=ij%w
        f[ij] =k
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        que.append([ti*w+tj,k+1])
    return k

res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            tres = bfs(i,j)
            res = max(res,tres)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
h,w = map(int, input().split())
s=[input()for _ in range(h)]
r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    while que:
        i,j,k = que.popleft()
        f[i*w+j] =k
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        que.append([ti,tj,k+1])
    return k

res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            tres = bfs(i,j)
            res = max(res,tres)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
h,w = map(int, input().split())
s=[input()for _ in range(h)]
r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    while que:
        i,j,k = que.popleft()
        f[i*w+j] =k
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        que.append([ti,tj,k+1])
    return max(f)

def main():
    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] ==".":
                tres = bfs(i,j)
                res = max(res,tres)
    print(res)

main()

Submission status: Time Limit Exceeded

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

r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    while que:
        i,j,k = que.popleft()
        f[i*w+j] =k
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        que.append([ti,tj,k+1])
    return max(f)


res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            tres = bfs(i,j)
            res = max(res,tres)
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
N = H * W

chart = [input() for _ in range(H)]

def node(h, w):
    return h * W + w

minDist = [[10**10] * N for _ in range(N)]

for i in range(N):
    minDist[i][i] = 0

for h in range(H):
    for w in range(W):
        if chart[h][w] == '#':
            continue

        if h > 0 and chart[h - 1][w] == '.':
            minDist[node(h, w)][node(h - 1, w)] = 1
            minDist[node(h - 1, w)][node(h, w)] = 1
        if h < H - 1 and chart[h + 1][w] == '.':
            minDist[node(h, w)][node(h + 1, w)] = 1
            minDist[node(h + 1, w)][node(h, w)] = 1
        if w > 0 and chart[h][w - 1] == '.':
            minDist[node(h, w)][node(h, w - 1)] = 1
            minDist[node(h, w - 1)][node(h, w)] = 1
        if w < W - 1 and chart[h][w + 1] == '.':
            minDist[node(h, w)][node(h, w + 1)] = 1
            minDist[node(h, w + 1)][node(h, w)] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = minDist[i][k] + minDist[k][j]
            if minDist[i][j] > d:
                minDist[i][j] = d

ans = 0
for dists in minDist:
    for d in dists:
        if d < 10**10:
            ans = max(ans, d)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split(" ")))
S = []
for h in range(H) :
  S.append(list(input()))
  
l_path = [[W*H for i in range(W*H)] for j in range(W*H)]

for h in range(H) :
  for w in range(W) :
    if((w+1<W) and (S[h][w] == ".") and (S[h][w+1] == ".")) :
      l_path[W*h+w][W*h+(w+1)] = 1
      l_path[W*h+(w+1)][W*h+w] = 1
    if((h+1<H) and (S[h][w] == ".") and (S[h+1][w] == ".")) :
      l_path[W*h+w][W*(h+1)+w] = 1
      l_path[W*(h+1)+w][W*h+w] = 1
       
for k in range(W*H) :
  for i in range(W*H) :
    for j in range(W*H) :
      if(l_path[i][j] > l_path[i][k] + l_path[k][j]) :
        l_path[i][j] = l_path[i][k] + l_path[k][j]

max_path = 0
for i in range(W*H) :
  for j in range(W*H) :
    if((l_path[i][j] < W*H) and (max_path < l_path[i][j])) :
      max_path = l_path[i][j]
        
print(max_path)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h, w))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z + 1
                        visited[x, y] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append([i, j, 0])
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        mx = 0
        while len(q) != 0:
            x, y, z = q[0]
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
                        visited[x][y] = True
                        ans = max(ans, z + 1)
            q.popleft()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(['...', '...', '...']), 4)

    def test_2(self):
        self.assertEqual(think(['...#.', '.#.#.', '.#...']), 10)


def solve():
    maze = read()
    result = think(maze)
    write(result)


def read():
    h, w = read_int(2)
    maze = []
    for _ in range(h):
        maze.append(read_line(n=w))
    return maze


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(maze):
    wall = '#'
    h, w = get_height_and_width_of(maze)
    longest_path_length = 0

    for y in range(h):
        for x in range(w):
            if maze[y][x] == wall:
                continue
            longest_path_length = max(longest_path_length, search(maze, x, y, wall))

    return longest_path_length


def write(result):
    print(result)


def get_height_and_width_of(maze):
    return len(maze), len(maze[0])


def search(maze, x, y, wall):
    h, w = get_height_and_width_of(maze)
    inf = h * w + 1

    dp = prepare_dp_table(h, w, inf)
    dfs(maze, dp, w, h, x, y, 0, wall)

    return get_longest_path_length(dp, inf)


def prepare_dp_table(h, w, inf):
    return [[inf for _ in range(w)] for _ in range(h)]


def dfs(maze, dp, w, h, x, y, distance, wall):
    if dp[y][x] < distance:
        return
    dp[y][x] = distance

    diff_xy = [
        (-1, 0), (1, 0), (0, -1), (0, 1)
    ]

    for dx, dy in diff_xy:
        nx, ny = x + dx, y + dy
        if not in_range(w, h, nx, ny):
            continue
        if maze[ny][nx] == wall:
            continue
        dfs(maze, dp, w, h, nx, ny, distance + 1, wall)


def in_range(w, h, x, y):
    return 0 <= x < w and 0 <= y < h


def get_longest_path_length(dp_table, inf):
    h, w = get_height_and_width_of(dp_table)
    longest_path_length = 0
    for y in range(h):
        for x in range(w):
            if dp_table[y][x] == inf:
                continue
            longest_path_length = max(longest_path_length, dp_table[y][x])
    return longest_path_length


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h, w))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x, y] = 1
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h, w))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append([i, j, 0])
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x, y] = 1
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h + 5, w + 5))
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x][y] = True
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
        visited = np.zeros((h + 5, w + 5))
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x][y] = True
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append([i, j, 0])
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        mx = 0
        while len(q) != 0:
            x, y, z = q[0]
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
            q.popleft()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
        visited = np.zeros((h + 5, w + 5))
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
 
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        mx = 0
        while len(q) != 0:
            x, y, z = q.popleft()
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#いい加減深さ優先探索, 幅優先探索をスムーズに実装してえなおい

H,W = map(int,input().split())

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

inf = 10 ** 3
m = 0
mi = -1
mj = -1
mk = -1
ml = -1
  
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == "#":
            continue
        data = [[inf]*(W+2) for k in range(H+2)]
        data[i][j] = 0
        stack = [[i,j,0]]
        while stack:
            x = stack.pop()
            if S[x[0]+1][x[1]] == "." and data[x[0]+1][x[1]]>x[2]+1:
                data[x[0]+1][x[1]] = x[2]+1
                stack.append([x[0]+1,x[1],x[2]+1])
            if S[x[0]][x[1]+1] == "." and data[x[0]][x[1]+1]>x[2]+1:
                data[x[0]][x[1]+1] = x[2]+1
                stack.append([x[0],x[1]+1,x[2]+1])
            if S[x[0]-1][x[1]] == "." and data[x[0]-1][x[1]]>x[2]+1:
                data[x[0]-1][x[1]] = x[2]+1
                stack.append([x[0]-1,x[1],x[2]+1])
            if S[x[0]][x[1]-1] == "." and data[x[0]][x[1]-1]>x[2]+1:
                data[x[0]][x[1]-1] = x[2]+1
                stack.append([x[0],x[1]-1,x[2]+1])
            #print(i,j,stack)

        for k in range(1,H+1):
            for l in range(1,W+1):
                if data[k][l] > m and data[k][l] != inf:
                    m = data[k][l]
                    mi = i
                    mj = j
                    mk = k
                    ml = l

#print(mi,mj,mk,ml)
print(m)

#DFSならワイの実装力でも割とスムーズにできそう？
#なんで昨日これやらなかったんや
#と言いつつWAするアホ

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def solve(maze, start):
  memo = deque()
  q = deque()
  q.append([start,0])
  ans = 0
  while q:
    cur, cnt = q.popleft()
    if cur in memo:
      continue
    else:
      ans = max(ans, cnt)
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],cnt+1])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    else:
      Ans = max(Ans, solve(Maze, [sy, sx]))
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def solve(maze, start):
  memo = []
  q = deque()
  q.append([start,0])
  ans = 0
  while q:
    cur, cnt = q.popleft()
    if cur in memo:
      continue
    else:
      ans = max(ans, cnt)
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],cnt+1])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    else:
      Ans = max(Ans, solve(Maze, [sy, sx]))
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

def bfs(HW, q, goal):
    num = 0
    mem = []
    while not q.empty():
        current = q.get()
        if current[0] >= H or current[0] < 0 or current[1] >= W or current[1] < 0:
            continue
        if HW[current[0]][current[1]] == '#':
            continue

        if (current[0] == goal[0]) and (current[1] == goal[1]):
            return current[2]

        if [current[0]+1,current[1]]  not in mem:
            mem.append([current[0]+1,current[1]])
            q.put([current[0]+1,current[1],current[2]+1])
        if [current[0],current[1]+1]  not in mem:
            mem.append([current[0],current[1]+1])
            q.put([current[0],current[1]+1,current[2]+1])
        if [current[0]-1,current[1]]  not in mem:
            mem.append([current[0]-1,current[1]])
            q.put([current[0]-1,current[1],current[2]+1])
        if [current[0],current[1]-1]  not in mem:
            mem.append([current[0],current[1]-1])
            q.put([current[0],current[1]-1,current[2]+1])
    return -1


H,W = map(int, input().split())

HW = [[''] * W for i in range(H)]
for i in range(H):
    h = str(input())
    for j in range(len(h)):
        HW[i][j] = h[j]

ans = 0
for si in range(H):
    for sj in range(W):
        if HW[si][sj] == '#':
            continue
        for gi in range(H):
            for gj in range(W):
                if HW[gi][gj] == '#':
                    continue
                q = Queue()
                q.put([si,sj,0])
                ans = max(ans, bfs(HW, q, [gi,gj]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
S = [input() for _ in range(h)]

INF = 100

maze = np.zeros((h*w, h*w))
for i in range(h*w-1):
    for j in range(i+1, h*w):
        i_h, i_w = divmod(i, w)
        j_h, j_w = divmod(j, w)

        if (S[i_h][i_w] == "." and
            S[j_h][j_w] == "." and
            abs(i_h-j_h) + abs(i_w-j_w) == 1):
            maze[i][j] = 1
            maze[j][i] = 1
        else:
            maze[i][j] = INF
            maze[j][i] = INF

# print(maze)

for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            maze[j][k] = min(maze[j][k], maze[j][i] + maze[i][k])


# print(maze)
# print(maze[maze < INF])
print(int(max(maze[maze<INF])))

Submission status: Time Limit Exceeded

Solution code:
def A():
    c = input()
    print(chr(ord(c)+1))

def B():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    K = temp[1]
    M = temp[2]
    A = [int(k) for k in input().split()]
    ans = M*N - sum(A)
    if ans <= K:
        print(max(0, ans))
    else:
        print(-1)

from collections import defaultdict
def C():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    M = temp[1]
    penal = defaultdict(int)
    P = []
    S = []
    for i in range(M):
        temp = input().split()
        P.append(int(temp[0]))
        S.append(temp[1])
    ac_problems = set()

    for i in range(M-1, -1, -1):
        if P[i] not in ac_problems and S[i] == 'AC':
            ac_problems.add(P[i])
        elif P[i] in ac_problems:
            if S[i] == 'WA':
                penal[P[i]] += 1
            elif S[i] == 'AC':
                penal[P[i]] = 0
    
    print(len(ac_problems), sum(penal.values()))

def D():
    temp = [int(k) for k in input().split()]
    H = temp[0]
    W = temp[1]
    S = []
    for i in range(H):
        S.append(input())
    ans = 0
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    def bfs(x, y):
        to_visit = [(x, y, 0)]
        visited = set()
        ret = 0
        while to_visit:
            x, y, distance = to_visit[0]
            del to_visit[0]
            visited.add((x, y))
            ret = max(distance, ret)
            for d in directions:
                if x+d[0] < H and x+d[0] >= 0:
                    if y+d[1] < W and y+d[1] >= 0:
                        if (x+d[0], y+d[1]) not in visited:
                            if S[x+d[0]][y+d[1]] == '.':
                                to_visit.append((x+d[0], y+d[1], distance+1))
        #print(memo)
        return ret

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                ans = max(bfs(i, j), ans)
                
    #print(memo)

    print(ans)

D()

Submission status: Time Limit Exceeded

Solution code:
import queue
def search(sy,sx,ey,ex):
    global H,W,Maze
    q = queue.Queue()

    Visit = [[-1]*W for _ in range(H)]
    Dir = [[0,1],[0,-1],[1,0],[-1,0]]

    Visit[sy][sx] = 0 
    q.put([sy,sx])

    while not q.empty():
        ty,tx = q.get()
        path = Visit[ty][tx]

        for dy,dx in Dir:
            ny = ty + dy
            nx = tx + dx
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if Maze[ny][nx] == '.':
                    if ny == ey and nx == ex:
                        return path+1

                    if Visit[ny][nx] == -1:
                        Visit[ny][nx] = path+1
                        q.put([ny,nx])
    return -1

H,W = map(int,input().split())
Maze = []
for h in range(H):
    Maze.append(input())

ans = 0
for sy in range(H):
    for sx in range(W):
        if Maze[sy][sx] == '#':
            continue
        for ey in range(H):
            for ex in range(W):
                if Maze[ey][ex] == '#':
                    continue
                if sx == ex and sy == ey:
                    continue
                p = search(sy,sx,ey,ex)          
                if p != -1:
                    ans = max(ans,p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m = map(int, input().split())
g = [input() for _ in range(n)]
maze = np.array(list(map(list, g)))

from collections import deque


def dfs(s, maze):
    H, W = maze.shape

    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    visited[s[0]][s[1]] = 0

    actions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([s])

    while queue:
        c = queue.popleft()
        for action in actions:
            nc = [0,0]
            nc[0] = c[0] + action[0]
            nc[1] = c[1] + action[1]
            if nc[0] in range(H) and nc[1] in range(W) and maze[tuple(nc)]=='.' and visited[tuple(nc)]==-1:
                visited[tuple(nc)] = visited[tuple(c)] + 1
                queue.append(nc)
    return np.max(visited)
    
ret = -1
H, W = maze.shape

for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == '.':
            ret = max(dfs((sx,sy), maze), ret)
print(ret)