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] = [int(i) for i in input().split()]
S = [0]*(H+2)
S[0] = ['#']*(W+2)
S[H+1] = ['#']*(W+2)

for i in range(1, H+1):
    row = ['#'] + list(input()) + ['#']
    S[i] = row

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
    
def bfs(p, q, c):
    distance = {(p, q):0}
    que = deque([(p, q)])
    reached = [[0]*(W+2) for k in range(H+2)]
    
    while len(que) > 0: 
        (y, x) = que.popleft()
        
        if c[y][x] == '#':
            continue
        
        reached[y][x] = 1
        
        for k in range(4):
            yy, xx = y + dy[k], x + dx[k]
            if reached[yy][xx] == 1 or c[yy][xx] == '#':
                continue
            else:
                distance[(yy, xx)] = distance[(y, x)] + 1
                que.append((yy, xx))
        
    distances = list(distance.values())
    return max(distances)

anss = [0]*(H*W)
times = 0

for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == '.':
            anss[times] = bfs(i, j, S)
        times += 1

print(max(anss))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

[H, W] = [int(i) for i in input().split()]
S = [0]*(H+2)
S[0] = ['#']*(W+2)
S[H+1] = ['#']*(W+2)

for i in range(1, H+1):
    row = ['#'] + list(input()) + ['#']
    S[i] = row
    
def bfs(p, q, c):
    distance = {(p, q):0}
    que = deque([(p, q)])
    reached = {(p, q):1}
    
    while len(que) > 0: 
        (y, x) = que.popleft()
        if c[y][x] == '#':
            continue
        
        reached[(y, x)] = 1
        try:
            if reached[(y+1, x)] == 1:
                pass
        except KeyError:
            if c[y+1][x] == '.':
                que.append((y+1, x))
                distance[(y+1, x)] = distance[(y, x)] + 1
        
        try:
            if reached[(y-1, x)] == 1:
                pass
        except KeyError:
            if c[y-1][x] == '.':
                que.append((y-1, x))
                distance[(y-1, x)] = distance[(y, x)] + 1
        
        try:
            if reached[(y, x+1)] == 1:
                pass
        except KeyError:
            if c[y][x+1] == '.':
                que.append((y, x+1))
                distance[(y, x+1)] = distance[(y, x)] + 1
        
        try:
            if reached[(y, x-1)] == 1:
                pass
        except KeyError:
            if c[y][x-1] == '.':
                que.append((y, x-1))
                distance[(y, x-1)] = distance[(y, x)] + 1
        
    distances = list(distance.values())
    return max(distances)

anss = [0]*(H*W)
times = 0

for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == '.':
            anss[times] = bfs(i, j, S)
        times += 1

print(max(anss))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def min_rounte(s, sta, path):
    move = [[0,1],[0,-1],[1,0],[-1,0]]
    for i in move:
        ax = [sta[0]+i[0], sta[1]+i[1]]
        if s[ax[0]][ax[1]] == -1:
            continue
        if s[ax[0]][ax[1]] > path:
            s[ax[0]][ax[1]] = path
    return s
 
def bfs(s, sta):
    s_ = np.array(s)
    s_[sta[0]][sta[1]] = 0
    for i in range(400):
        ind = np.where(s_==i)
        for j in range(len(ind[0])):
            s_ = min_rounte(s_, [ind[0][j], ind[1][j]], i+1)
        if len(ind[0]) == 0:
            break
    return i-1
        

h, w = map(int, input().split())
#s_ = [[0 if i=="." else -1 for i in input()] for j in range(h)]
s = [[-1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == ".":
            s[i+1][j+1] = 512
        else:
            s[i+1][j+1] = -1
  
ans = 1

for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == -1:
            continue
        temp = bfs(s, [i,j])
        if temp > ans:
            ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]

    def bfs(sy, sx, gy, gx):
        que = deque()
        dist = [[-1]*W for h in range(H)]
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))
        return dist[gy][gx]

    ans = 0
    for s in st:
        for t in st:
            if s == t or c[s[0]][s[1]] == "#" or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, bfs(s[0], s[1], t[0], t[1]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import queue
from itertools import combinations

def cal(s, g, f_org):
  f = copy.deepcopy(f_org)
  m = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  q = queue.Queue()
  q.put(s)
  while not q.empty():
    x, y, t = q.get()
    if (x == g[0]) and (y == g[1]):
      break
    for i, j in m:
      if f[y+i][x+j] == '.':
        q.put((x+j, y+i, t+1))
        f[y+i][x+j] = '#'
  return t

def run():
  H, W = map(int, input().split())
  f = [['#']*(W+2)]
  f += [list('#'+input()+'#') for _ in range(H)]
  f += [['#']*(W+2)]
  t_li = []
  po_li = []
  for x in range(1, W+1):
    for y in range(1, H+1):
      po_li.append((x, y))
  m = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  for (sx, sy), (gx, gy) in combinations(po_li, 2):
    if f[sy][sx] == '#' or f[gy][gx] == '#':
      continue
    tmp = 0
    for i, j in m:
      if f[sy+i][sx+j] == '#':
        tmp += 1
    if tmp >= 2:
      t = cal((sx, sy, 0), (gx, gy), f)
    #print(sx, sy, gx, gy, t)
      t_li.append(t)
  #print(t_li)
  print(max(t_li))

if __name__ == '__main__':
  run()

Submission status: Time Limit Exceeded

Solution code:
import copy
import queue
from itertools import combinations

def cal(s, g, f_org):
  f = copy.deepcopy(f_org)
  m = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  q = queue.Queue()
  q.put(s)
  while not q.empty():
    x, y, t = q.get()
    if (x == g[0]) and (y == g[1]):
      break
    for i, j in m:
      if f[y+i][x+j] == '.':
        q.put((x+j, y+i, t+1))
        f[y+i][x+j] = '#'
  return t

def run():
  H, W = map(int, input().split())
  f = [['#']*(W+2)]
  f += [list('#'+input()+'#') for _ in range(H)]
  f += [['#']*(W+2)]
  t_li = []
  po_li = []
  for x in range(1, W+1):
    for y in range(1, H+1):
      po_li.append((x, y))
  for (sx, sy), (gx, gy) in combinations(po_li, 2):
    if f[sy][sx] == '#' or f[gy][gx] == '#':
      continue
    t = cal((sx, sy, 0), (gx, gy), f)
    #print(sx, sy, gx, gy, t)
    t_li.append(t)
  #print(t_li)
  print(max(t_li))

if __name__ == '__main__':
  run()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
]

def bfs(start, goal):
    visited = [[False] * w for _ in range(h)]
    que = deque([start + (0,)])

    max_cnt = -1
    while que:
        y, x, cnt = que.popleft()
        if 0 <= x < w and 0 <= y < h and maze[y][x] == '.' and not visited[y][x]:
            max_cnt = max(cnt, max_cnt)
            visited[y][x] = cnt + 1
            for dy, dx in directions:
                que.append((y + dy, x + dx, visited[y][x]))
    # print("\n".join([" ".join(map(str, v)) for v in visited]))
    return max_cnt

ans = 0
for sx in range(w):
    for sy in range(h):
        for gx in range(w):
            for gy in range(h):
                ans = max(ans, bfs((sy, sx), (gy, gx)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def mk_idx(y,x):
    return y*32+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            idx = mk_idx(y,x)
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            q = []
            heapq.heappush(q, [0, mk_idx(y,x)])
            while len(q) != 0:
                v = heapq.heappop(q)
                n = v[0]
                idx = v[1]
                d[ idx ] = n;
                dmax = max(dmax, n)
                for nv in G[ idx ]:
                    if d[ nv ] <= n+1 :
                        continue
                    heapq.heappush(q, [n+1, nv ] )
print(dmax)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def mk_idx(y,x):
    return y*32+x

H,W=map(int, input().split())
DINF = 100000
d = [ DINF for _ in range( mk_idx(22,22) ) ]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            idx = mk_idx(y,x)
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            q = []
            heapq.heappush(q, [0, mk_idx(y,x)])
            while len(q) != 0:
                v = heapq.heappop(q)
                n = v[0]
                idx = v[1]
                d[ idx ] = n;
                for nv in G[ idx ]:
                    if d[ nv ] <= n+1 :
                        continue
                    heapq.heappush(q, [n+1, nv ] )
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    idx = mk_idx(iy,ix)
                    if d[idx] != DINF:
                        dmax = max(dmax, d[idx])
                    d[idx] = DINF
print(dmax)

Submission status: Time Limit Exceeded

Solution code:
import heapq

H,W=map(int, input().split())
DINF = 100000
d = [ [ DINF for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [ [] for _ in range(W+2)] for _ in range(H+2)]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y-1][x] == '.'):  G[y][x].append([y-1,x])
        if (S[y][x-1] == '.'):  G[y][x].append([y,x-1])
        if (S[y+1][x] == '.'):  G[y][x].append([y+1,x])
        if (S[y][x+1] == '.'):  G[y][x].append([y,x+1])

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            q = []
            heapq.heappush(q, [0,y,x])
            while len(q) != 0:
                v = heapq.heappop(q)
                n = v[0]
                iy = v[1]
                ix = v[2]
                d[iy][ix] = n;
                for nv in G[iy][ix]:
                    if d[nv[0]][nv[1]] <= n+1 :
                        continue
                    heapq.heappush(q, [n+1, nv[0], nv[1] ] )
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    if d[iy][ix] != DINF:
                        dmax = max(dmax, d[iy][ix])
                    d[iy][ix] = DINF
print(dmax)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
DINF = 100000
d = [ [ DINF for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [ [] for _ in range(W+2)] for _ in range(H+2)]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y-1][x] == '.'):  G[y][x].append([y-1,x])
        if (S[y][x-1] == '.'):  G[y][x].append([y,x-1])
        if (S[y+1][x] == '.'):  G[y][x].append([y+1,x])
        if (S[y][x+1] == '.'):  G[y][x].append([y,x+1])

def SUB(x,y,n):
    d[y][x] = n
    for v in G[y][x]:
        if d[v[0]][v[1]] > n+1:
            SUB(v[1],v[0],n+1)

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            SUB(x,y,0)
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    if d[iy][ix] != DINF:
                        dmax = max(dmax, d[iy][ix])
                    d[iy][ix] = DINF
print(dmax)

Submission status: Time Limit Exceeded

Solution code:

H,W=map(int, input().split())
d = [ [ 100000 for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))

def SUB(x,y,n):
    d[y][x] = n
    if (S[y-1][x] == '.') and (d[y-1][x] > n+1): SUB(x,y-1,n+1)
    if (S[y][x-1] == '.') and (d[y][x-1] > n+1): SUB(x-1,y,n+1)
    if (S[y+1][x] == '.') and (d[y+1][x] > n+1): SUB(x,y+1,n+1)
    if (S[y][x+1] == '.') and (d[y][x+1] > n+1): SUB(x+1,y,n+1)

dmax = 0
for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            SUB(x,y,0)
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    if d[iy][ix] != 100000:
                        if dmax < d[iy][ix]:
                            dmax = d[iy][ix]
                        d[iy][ix] = 100000
print(dmax)

Submission status: Time Limit Exceeded

Solution code:

H,W=map(int, input().split())
d = [ [ 100000 for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))

def SUB(x,y,n):
    d[y][x] = n
    if (S[y-1][x] == '.') and (d[y-1][x] > n+1): SUB(x,y-1,n+1)
    if (S[y][x-1] == '.') and (d[y][x-1] > n+1): SUB(x-1,y,n+1)
    if (S[y+1][x] == '.') and (d[y+1][x] > n+1): SUB(x,y+1,n+1)
    if (S[y][x+1] == '.') and (d[y][x+1] > n+1): SUB(x+1,y,n+1)

dmax = 0
for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    d[iy][ix] = 100000
            SUB(x,y,0)
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    if d[iy][ix] != 100000:
                        if dmax < d[iy][ix]:
                            dmax = d[iy][ix]
print(dmax)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
h, w = map(int, input().split())
maze = [input() for _ in range(h)]
dest = [(1, 0), (-1, 0), (0, 1), (0, -1)]
score = 0

for sx, sy in product(range(w), range(h)):
  if maze[sy][sx] == '#':
    continue
  r = [[-1] * w for _ in range(h)]
  r[sy][sx] = 0
  queue = deque([(sx, sy)])
  while queue:
    x, y = queue.popleft()
    for dx, dy in dest:
      nx, ny = x + dx, y + dy
      if not (0 <= nx < w and 0 <= ny < h):
        continue
      if maze[ny][nx] == '#' and r[ny][nx] != -1:
        continue
      r[ny][nx] = r[y][x] + 1
      queue.append((nx, ny))
      score = max(score, r[ny][nx])
print(score)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from itertools import chain, combinations
import json


def main():
    # N = int(input())
    H, W = [int(a) for a in input().split()]
    S = [
        input()
        for _ in range(H)
    ]

    def saitan(start, end):
        mem = {start}

        def get_rinsetsu(ii, jj):
            d = [
                (1, 0),
                (-1, 0),
                (0, 1),
                (0, -1),
            ]
            res = []
            for di, dj in d:
                ni = ii + di
                nj = jj + dj
                if ni < 0 or nj < 0:
                    continue
                if ni >= H or nj >= W:
                    continue
                if S[ni][nj] == '.':
                    if (ni, nj) not in mem:
                        res.append((ni, nj))
            return res

        q = [(start, 0)]
        while len(q) != 0:
            (i, j), distance = q.pop(0)
            rinsetsu = get_rinsetsu(i, j)
            for r in rinsetsu:
                if r == end:
                    return distance + 1, mem
                q.append((r, distance + 1))
                mem.add(r)
        return -1, mem

    res = -1
    for a in range(H * W):
        start = a // W, a % W
        mm = set()
        if S[start[0]][start[1]] == '#':
            continue
        for b in range(a + 1, H * W):
            end = b // W, b % W
            if S[end[0]][end[1]] == '#':
                continue
            if end in mm:
                continue
            ddd, m = saitan(start, end)
            mm |= m
            res = max(res, ddd)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from itertools import chain, combinations
import json


def main():
    # N = int(input())
    H, W = [int(a) for a in input().split()]
    S = [
        input()
        for _ in range(H)
    ]

    def saitan(start, end):
        mem = {start}

        def get_rinsetsu(ii, jj):
            d = [
                (1, 0),
                (-1, 0),
                (0, 1),
                (0, -1),
            ]
            res = []
            for di, dj in d:
                ni = ii + di
                nj = jj + dj
                if ni < 0 or nj < 0:
                    continue
                if ni >= H or nj >= W:
                    continue
                if S[ni][nj] == '.':
                    if (ni, nj) not in mem:
                        res.append((ni, nj))
            return res

        q = [(start, 0)]
        while len(q) != 0:
            (i, j), distance = q.pop(0)
            rinsetsu = get_rinsetsu(i, j)
            for r in rinsetsu:
                if r == end:
                    return distance + 1
                q.append((r, distance + 1))
                mem.add(r)
        return -1

    res = -1
    for a in range(H * W):
        start = a // W, a % W
        if S[start[0]][start[1]] == '#':
            continue
        for b in range(a + 1, H * W):
            end = b // W, b % W
            if S[end[0]][end[1]] == '#':
                continue
            ddd = saitan(start, end)
            res = max(res, ddd)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def bfs():
      global count
      now=que.popleft()
      now_step=steps[now[0]][now[1]]
      for dx,dy in (0,-1),(1,0),(0,1),(-1,0):
            ny=now[0]+dy
            nx=now[1]+dx
            if 0<=ny<=H-1 and 0<=nx<=W-1:
                  if maze[ny][nx]=="G":
                        count=now_step+1
                        break
                  elif maze[ny][nx]==".":
                        if ([ny,nx] in que)==False:
                              que.append([ny,nx])
                              steps[ny][nx]=now_step+1
                  else:
                        pass

import copy
from collections import deque

H,W=map(int,input().split())
maze=[]
for i in range(H):
   S=input()
   S=[c for c in S]
   maze.append(S)

maze_copy=copy.deepcopy(maze)
max_step=0

for s_i in range(H):
   for s_j in range(W):
      if maze[s_i][s_j]=="#":
         continue

      for g_i in range(H):
         for g_j in range(W):
            if maze[g_i][g_j]=="#":
               continue
            
            maze=copy.deepcopy(maze_copy)
            que=deque([[s_i,s_j]])
            maze[s_i][s_j]="S"
            maze[g_i][g_j]="G"
            steps=[[-1]*W for c in range(H)]
            steps[s_i][s_j]=0
            count=0

            if (s_i,s_j)==(g_i,g_j):
               max_step=max(max_step,0)

            else:
               while(count==0):
                  bfs()
               max_step=max(max_step,count)

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

maze = [[False for i in range(W)] for j in range(H)]

for h in range(H):
    ret = input()
    for i, x in enumerate(ret):
        if x == "#":
            pass
        else: # == "."
            maze[h][i] = True

class MazePath():
    def __init__(self, H, W, maze):
        self.H = H
        self.W = W
        self.maze = maze
        self.path_list = []
    
    def start_find(self, y, x):
        start_pos = [[y, x]]
        self.path_list.append(start_pos)
        self.find_next_path(y, x, start_pos)

    def can_move(self, y, x, visited_pos):
        if y < 0 or x < 0:
            return False
        if y >= H or x >= W:
            return False
        for yy, xx in visited_pos:
            if y == yy and x == xx:
                return False
        return self.maze[y][x]

    def find_next_path(self, y, x, visited_pos):
        next_pathes = []
        for dy, dx in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            next_y = y + dy
            next_x = x + dx
            if self.can_move(next_y, next_x, visited_pos):
                new_path = copy.copy(visited_pos)
                new_path.append([next_y, next_x])
                next_pathes.append(new_path)
        if len(next_pathes) == 0:
            return
        self.path_list.extend(next_pathes)
        for new_visited_pos in next_pathes:
            new_y, new_x = new_visited_pos[-1]
            self.find_next_path(new_y, new_x, new_visited_pos)

    def min_len(self, y, x):
        min_len = self.H * self.W
        for path in self.path_list:
            for l, (yy, xx) in enumerate(path):
                if y == yy and x == xx:
                    if l < min_len:
                        min_len = l
        if min_len == self.H * self.W:
            return -1
        return min_len

max_len = 0
for j in range(H):
    for i in range(W):
        if maze[j][i] == False:
            continue
        start_maze = MazePath(H, W, maze)
        start_maze.start_find(j, i)
        # for path in start_maze.path_list:
        #     print(len(path), path)
        for yy in range(H):
            for xx in range(W):
                # print(start_maze.min_len(yy, xx))
                cur_min_len = start_maze.min_len(yy, xx)
                if cur_min_len > max_len:
                    max_len = cur_min_len
print(max_len)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

maze = [[False for i in range(W)] for j in range(H)]

for h in range(H):
    ret = input()
    for i, x in enumerate(ret):
        if x == "#":
            pass
        else: # == "."
            maze[h][i] = True

class MazePath():
    def __init__(self, H, W, maze):
        self.H = H
        self.W = W
        self.maze = maze
        self.path_list = []
    
    def start_find(self, y, x):
        start_pos = [[y, x]]
        self.path_list.append(start_pos)
        self.find_next_path(y, x, start_pos)

    def can_move(self, y, x, visited_pos):
        if y < 0 or x < 0:
            return False
        if y >= H or x >= W:
            return False
        for yy, xx in visited_pos:
            if y == yy and x == xx:
                return False
        return self.maze[y][x]

    def find_next_path(self, y, x, visited_pos):
        next_pathes = []
        for dy, dx in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            next_y = y + dy
            next_x = x + dx
            if self.can_move(next_y, next_x, visited_pos):
                new_path = copy.copy(visited_pos)
                new_path.append([next_y, next_x])
                next_pathes.append(new_path)
        if len(next_pathes) == 0:
            return
        self.path_list.extend(next_pathes)
        for new_visited_pos in next_pathes:
            new_y, new_x = new_visited_pos[-1]
            self.find_next_path(new_y, new_x, new_visited_pos)

    def min_len(self, y, x):
        min_len = self.H * self.W
        for path in self.path_list:
            for l, (yy, xx) in enumerate(path):
                if y == yy and x == xx:
                    if l < min_len:
                        min_len = l
        if min_len == self.H * self.W:
            return -1
        return min_len

max_len = 0
for j in range(H):
    for i in range(W):
        start_maze = MazePath(H, W, maze)
        start_maze.start_find(j, i)
        # for path in start_maze.path_list:
        #     print(len(path), path)
        for yy in range(H):
            for xx in range(W):
                # print(start_maze.min_len(yy, xx))
                cur_min_len = start_maze.min_len(yy, xx)
                if cur_min_len > max_len:
                    max_len = cur_min_len
print(max_len)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
    grid += '#' + input() + '#'
grid += '#' * (W+2)
move = [1, -1, W+2, -W-2]

def bfs(start):
  lst = [10**9] *((H+2)*(W+2))
  lst[start] = 0
  q = deque([start])
  while q:
    x = q.popleft()
    dx = lst[x]
    for d in move:
      y = x + d
      if grid[y] == '#':
        continue
      dy = dx + 1
      if dy > lst[y]:
        continue
      lst[y] = dy
      q.append(y)
  ans = max(x for x in lst if x < 10**9)
  return ans
  
  
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '#'))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
    grid += '#' + input() + '#'
grid += '#' * (W+2)
move = [1, -1, W+2, -W-2]

def bfs(start):
  lst = [10**9] *((H+2)*(W+2))
  lst[start] = 0
  q = deque([start])
  while q:
    x = q.popleft()
    dx = lst[x]
    for d in move:
      y = x + d
      if grid[y] == '#':
        continue
      dy = dx + 1
      if dy > lst[y]:
        continue
      lst[y] = dy
      q.append(y)
  ans = max(x for x in lst if x < 10**9)
  return ans
  
cnt = 0
for i in range((H+2)*(W+2)):
  if grid[i] != '#':
    cnt =  max(cnt,bfs(i))
print(cnt)

Submission status: Time Limit Exceeded

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

def serch(S, x, y):
  ans = []
  cand = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
  for pos in cand:
    a, b = pos
    if S[a][b] == ".":
      ans.append(pos)
  return ans

def length(S, i, j):
  S[i][j] = 0
  temp = serch(S, i, j)
  counter = 0
  while len(temp) != 0:
    next_temp = []
    counter += 1
    for pos in temp:
      x, y = pos
      S[x][y] = counter
      next_temp += serch(S, x, y)
    else:
      temp = next_temp
  return counter

import copy
max_l = 0
for i in range(1, h + 1):
  for j in range(1, w + 1):
    if S[i][j] == ".":
      T = copy.deepcopy(S)
      max_l = max(length(T, i, j), max_l)
print(max_l)

Submission status: Time Limit Exceeded

Solution code:
# H（縦マス） W（横マス）
# 3 5
# ...#.
# .#.#.
# .#...  → ループ内では S[i][j] で表す

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

S = [list(input()) for i in range(H)]
# Sは元の地図

T = [[0 for i in range(W)] for j in range(H)]
# Tはそれぞれの位置からの最大距離を示す（まず0、このあと距離を埋めていく）

for i in range(H):  
  for j in range(W):
    # このループ内で点[i][j]からの最大距離を求める
    # 0 <= i <= H-1
    # 0 <= j <= W-1
    
    if S[i][j] == "#":
      continue
    # もし点[i][j]が壁ならループを終了し次の点を調べる
    
    U = [[999 for i in range(W)] for j in range(H)]
    U[i][j] = 0
    # 点[i][j]から各点までの距離をUで表す（まず999で初期化）
    # ただし点[i][j]は0で自明
    
    queue = []
    if 0 <= i <= H-1 and 0 <= j-1 <= W-1:
      if S[i][j-1] == ".":
        queue.append([i, j-1])
    if 0 <= i <= H-1 and 0 <= j+1 <= W-1:
      if S[i][j+1] == ".":
        queue.append([i, j+1])
    if 0 <= i-1 <= H-1 and 0 <= j <= W-1:
      if S[i-1][j] == ".":
        queue.append([i-1, j])
    if 0 <= i+1 <= H-1 and 0 <= j <= W-1:
      if S[i+1][j] == ".":
        queue.append([i+1, j])
    # 最初の点の周辺をqueueに追加

    while queue != []:
      
      [qi, qj] = queue.pop(0) # queueの先頭を取得して削除

      kyori = []
      if 0 <= qi <= H-1 and 0 <= qj-1 <= W-1:
        kyori.append(U[qi][qj-1])
        if U[qi][qj-1] == 999 and S[qi][qj-1] == ".":
          queue.append([qi, qj-1])
      if 0 <= qi <= H-1 and 0 <= qj+1 <= W-1:
        kyori.append(U[qi][qj+1])
        if U[qi][qj+1] == 999 and S[qi][qj+1] == ".":
          queue.append([qi, qj+1])
      if 0 <= qi-1 <= H-1 and 0 <= qj <= W-1:
        kyori.append(U[qi-1][qj])
        if U[qi-1][qj] == 999 and S[qi-1][qj] == ".":
          queue.append([qi-1, qj])
      if 0 <= qi+1 <= H-1 and 0 <= qj <= W-1:
        kyori.append(U[qi+1][qj])
        if U[qi+1][qj] == 999 and S[qi+1][qj] == ".":
          queue.append([qi+1, qj])
      U[qi][qj] = min(kyori) + 1
      # queueの先頭から最初の点[i][j]までの距離をUに代入      
      # queueの先頭に隣接する点のうち、まだ考慮していない分をqueueに追加

    # 点[i][j]からの最大の距離をTに代入する（開始）
    for k in range(H):
      for l in range(W):
        if T[i][j] < U[k][l] and S[k][l] == ".":
          T[i][j] = U[k][l]
    # 点[i][j]からの最大の距離をTに代入する（終了）

# ここまででTが全て埋まる

maxkyori = 0
for i in range(H):
  for j in range(W):
    if maxkyori < T[i][j]:
      maxkyori = T[i][j]

print(maxkyori)