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:
def calc_distance(maze, sx, sy, gx, gy):
        # Goalまでの距離としてはあり得ない数値を設定
        INF = 100000000

        field_x_length = len(maze[0])
        field_y_length = len(maze)

        # mazeと同じ配列構造ですべての箇所がINFで埋まっている二次元配列を作る
        # startからの距離をこのdistance配列に格納していく
        distance = []
        for i in range(field_y_length):
            distance.append([])
            for j in range(field_x_length):
                distance[i].append(INF)

        # queue配列を作り、ここに座標を格納する
        queue = []

        # queueの末尾にStart座標を入れる
        queue.insert(0, (sy, sx))

        # Startの座標距離は0に設定
        distance[sy][sx] = 0

        # Goalにつくまで以下ループ
        while True:
            # 最初に入れた要素を取り出す
            if len(queue) == 0:
                break
            y, x = queue.pop()

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

            # 新しい座標(ny, nx)に現時点の座標から
            # (0, 1)(1, 0)(0, -1)(-1, 0)移動した値を代入
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                # 移動先ny, nxが迷路の範囲内
                # かつ壁（maze配列が#）でなく、
                # かつ未到達（distance配列がINF）であるときに
                # 現時点の距離+1をdistance配列に格納する
                # 現時点の座標をqueue配列に格納する（再ループの時にその座標から始める）
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1

        # Goalについたらループを抜け、Goalまでの距離を返す
        return distance[gy][gx]




def main():
    H, W = map(int, input().split())
    maze = []
    max = 0

    for _ in range(H):
        l = list(input())
        maze.append(l)

    for i in range(H):
        for j in range(W):
            for k in range(H):
                for l in range(W):
                    if (i == k) & (j==l):
                        pass
                    else:
                        distance = calc_distance(maze, j, i, l, k)

                        if (distance != 100000000) & (distance > max):
                            max = distance

    print(max)
    return 0
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def num():
    return int(input())
def nums():
    return list(map(int,input().split()))

import itertools as iter
import math
import fractions
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

H,W = nums()
meiro = [[1] + [int(n == "#") for n in list(input())] + [1] for _ in range(H)]
meiro.insert(0,[1 for _ in range(W+2)])
meiro.insert(len(meiro),[1 for _ in range(W+2)])



import math

class MazeNode:
    def __init__(self,x,y,st,cond):
        self.x = x
        self.y = y
        self.state = st
        self.cond = cond
        self.parent = None
        self.fs = 0
        self.hs = 0
        self.gs = 0

    def calc_hs(self,gx,gy):
        dx = self.x - gx
        dy = self.y - gy
        self.hs = math.sqrt(dx ** 2 + dy ** 2)
    
    def update_gs(self):
        self.gs = self.fs - self.hs

    def set_gs(self,val):
        self.gs = val

    def set_cond(self,cond):
        if cond == "open" or cond == "close":
            self.cond = cond
        else:
            ##print("cond set error")
            pass
    
    # debug
    def show_pos(self):
        pass
        ##print("(%d:%d) %d %s" % (self.x,self.y,self.state,self.cond))

def get_min_fs_node(maze_nodes):
    # open_nodeのうちmin_fsのものを1つreturn
    res_node = None
    for row in maze_nodes:
        for node in row:
            if node.cond != "open":
                continue
            if not res_node:
                res_node = node
            elif node.fs < res_node.fs:
                res_node = node
    return res_node

def check_next_node(target_node,maze_nodes):
    # get next nods
    tx = target_node.x
    ty = target_node.y
    next_nodes = [
            maze_nodes[ty-1][tx  ],
            maze_nodes[ty  ][tx+1],
            maze_nodes[ty+1][tx  ],
            maze_nodes[ty  ][tx-1]
            ]

    # process next nodes
    target_node.update_gs()
    for node in next_nodes:
        if node.state == 1:
            continue
        f_dash = target_node.gs + node.hs + 1
        if node.cond == "none":
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "open" and f_dash < node.fs:
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "close" and f_dash < node.fs:
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node

def print_route(maze,fin_node):
    # make map data
    print()
    map = []
    for y in range(len(maze)):
        row = []
        for x in range(len(maze[0])):
            row.append("-" if maze[y][x] == 1 else " ")
        map.append(row)

    # make route data
    node = fin_node
    while node:
        map[node.y][node.x] = "x"
        node = node.parent

    # print route data
    for y in range(len(map)):
        for x in range(len(map[0])):
            print(map[y][x], end="")
        print("")

def make_route(fin_node):
    route = ""
    node = fin_node

    while node.parent:
        dx = node.x - node.parent.x
        dy = node.y - node.parent.y

        if dx == 1:
            route += "E"
        elif dx == -1:
            route += "W"
        elif dy == 1:
            route += "S"
        elif dy == -1:
            route += "N"
        
        node = node.parent

    return route[::-1]



def checkio(data,start,goal):
    maze = data
    maze_nodes = []

    goal_pos_x,goal_pos_y = goal

    for y in range(len(maze)):
        row = []
        for x in range(len(maze[0])):
            node = MazeNode(x,y,maze[y][x],"none")
            node.calc_hs(goal_pos_x,goal_pos_y)
            row.append(node)
        maze_nodes.append(row)

    start_node = maze_nodes[start[0]][start[1]]
    start_node.set_cond("open")
    start_node.set_gs(0)
    start_node.fs = start_node.hs

    while True: # step12:repeat
        # step3,4
        target_node = get_min_fs_node(maze_nodes)
        if not target_node:
            # step3
            #print("search fail")
            return "fail"
        elif target_node.x == goal_pos_x and target_node.y == goal_pos_y:
            #step5_finish
            #print("search finish")
            #print_route(maze,target_node)
            return len(make_route(target_node)) #step13
        else:
            # step5_continue
            target_node.set_cond("close")
            check_next_node(target_node,maze_nodes) #step6-11



    
ans = set()
goals = [(x,y) for y in range(H+2) for x in range(W + 2)]
starts = [(x,y) for y in range(H) for x in range(W)]
for s in starts:
    for g in goals:
        try:
            r = checkio(meiro,s,g)
            if not r == "fail":ans.add(r)
        except:pass
print(max(ans)-1)

Submission status: Time Limit Exceeded

Solution code:
# D
from collections import deque
INF = float('inf')
h, w = map(int, input().split())
maps = []

for _ in range(h):
    lst = list(input())
    maps.append(lst)

def bfs(start, maps, distance, height, width):
    d = deque()
    d.append(start)
    sx, sy = start
    distance[sx][sy] = 0
    
    while d:
        now = d.pop()
        nowx, nowy = now
        
        for i in range(0, 4):
            nx, ny = nowx + [1, 0, -1, 0][i], nowy + [0, 1, 0, -1][i]
            if (0<=nx<height)and(0<=ny<width):
                if (maps[nx][ny] == '.'):
                    if (distance[nx][ny] == -1) or \
                        (distance[nowx][nowy]+1<distance[nx][ny]):
                        d.append((nx, ny))
                        distance[nx][ny] = distance[nowx][nowy] + 1
    #print(distance)
    max_ = -1
    for row in distance:
        for val in row:
            if val > max_:
                max_ = val
    return max_

cand = []
for sx in range(h):
    for sy in range(w):
        if maps[sx][sy] == '#':
            continue
        distance = [[-1 for _ in range(w)] for _ in range(h)]
        cand.append(bfs((sx, sy), maps, distance, h, w))
print(max(cand))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product


INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for (i, j) in E[v]: dist[v][(i, j)] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    for v in V:
        if dist[v][v] < 0: return None
    return dist

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = defaultdict(list)
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.': E[(i, j)].append((x, y)); E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    ans = max(ans, max(D.values()))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      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],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
memo = [[False]*(W+2) for _ in range(H+2)]
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    for ey in range(sy, H+1):
      for ex in range(1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from array import array

h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(input())

nodes = h*w

g = []

for i in range(nodes):
    g.append(array('l', [10000000] * (w * h)))

for i in range(nodes):
    g[i][i] = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            continue
        if maze[i][j] == '.':
            if i > 0 and maze[i-1][j] != '#':
                g[i * w + j][(i-1) * w + j] = 1
                g[(i-1) * w + j][i * w + j] = 1
            if i < h-1 and maze[i+1][j] != '#':
                g[i * w + j][(i+1) * w + j] = 1
                g[(i+1) * w + j][i * w + j] = 1
            if j > 0 and maze[i][j-1] != '#':
                g[i * w + j][i * w + j-1] = 1
                g[i * w + j-1][i * w + j] = 1
            if j < w-1 and maze[i][j+1] != '#':
                g[i * w + j][i * w + j+1] = 1
                g[i * w + j+1][i * w + j] = 1

def floyed(g, nodes):
    result = 0
    for k in range(nodes):
        for i in range(nodes):
            if i == k:
                continue
            if g[i][k] == 10000000:
                continue
            for j in range(nodes):
                if g[k][j] == 10000000:
                    continue
                if i == j or i == k or k == j:
                    continue
                if g[i][j] > g[i][k] + g[k][j]:
                    g[i][j] = g[i][k] + g[k][j]

floyed(g,nodes)

result = 0
for i in range(nodes):
    for j in range(nodes):
        if g[i][j] < 10000000 and g[i][j] > result:
            result = g[i][j]
print(result)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from collections import deque

# 最短にする
# 0回以上でたどり着けるのでスタート=ゴールのことがある ふざけんな
h, w = map(int, input().split())
table = [[] for _ in range(h)]
for i in range(h):
    table[i] = list(input())


def bfs(y, x, t):
    steps = [0, 1, 0, -1, 0]
    queue = deque([[y, x]])
    arr = []
    while len(queue) > 0:
        cur_y, cur_x = queue.popleft()
        for i in range(4):
            next_y, next_x = cur_y + steps[i], cur_x + steps[i + 1]
            if 0 <= next_y < h and 0 <= next_x < w:
                if t[next_y][next_x] == "G":
                    arr.append(t[cur_y][cur_x])
                    continue
                if t[next_y][next_x] == ".":
                    t[next_y][next_x] = t[cur_y][cur_x] + 1
                    queue.append([next_y, next_x])

    return 0 if len(arr) == 0 else min(arr) + 1


ans = 0
for sy in range(h):
    for sx in range(w):
        # table[sy][sx]をスタート地点とする
        if table[sy][sx] != ".":
            continue
        for gy in range(h):
            for gx in range(w):
                if sy == gy and sx == gx:
                    continue
                if table[gy][gx] == ".":
                    mytable = deepcopy(table)
                    mytable[sy][sx] = 0
                    mytable[gy][gx] = "G"
                    # ans = min(ans, bfs(sy, sx, mytable))
                    ret = bfs(sy, sx, mytable)
                    ans = max(ans, ret)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
import sys
input = sys.stdin.readline

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

ans = 0

d = ((0, 1), (0, -1), (1, 0), (-1, 0))


def bfs(x, y):
    global ans
    m = np.full((H, W), -1, dtype=np.int)

    q = deque()
    q.append([y, x, 0])

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                q.append([dj, di, v+1])
                if ans < v+1:
                    ans = v+1


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        bfs(i, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
raw = []
for _ in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(2)
  raw.append(add)
nex = [[0,1],[0,-1],[1,0],[-1,0]]
can = []
from copy import deepcopy as dc
for a in range(h):
  for b in range(w):
    if raw[a][b] == 2:
      continue
    now = dc(raw)
    now[a][b] = 1
    ans = 0
    while True:
      last = dc(now)
      ans += 1
      check = 1
      for i in range(h):
        for j in range(w):
          if last[i][j] == 0:
            for x in nex:
              if 0 <= i+x[0] < h and 0 <= j+x[1] < w:
                if last[i+x[0]][j+x[1]] == 1:
                  now[i][j] = 1
                  break
            else:
              check = 0
      if check == 1:
        can.append(ans)
        break
print(max(can))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd, deque

input = raw_input

h,w = map(int,input().split())
M = [input().strip()+'#' for _ in range(h)]
M.append(w*'#')

road = []

start = None
for i in range(h):
    for j in range(w):
        if M[i][j] == '.':
            road.append((j,i))

def dist(aa,bb,cc,dd):
    Q = deque()
    Q.append((0, aa, bb))
    seen = set()
    while Q:
        d,x,y = Q.popleft()

        if (x,y) == (cc,dd):
            return d
        if (x,y) in seen: continue
        seen.add((x,y))

        for nx,ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
            if M[ny][nx] == '.':
                Q.append((d+1, nx, ny))

    raise AssertionError('D:')


print(max(dist(a[0], a[1], b[0], b[1]) for a in road for b in road))

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    s_list = list(str(input()))
    S.append(s_list)

from collections import deque
INF = 100000000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(sx, sy, gx, gy):
    d = []
    for i in range(H):
        d.append([INF] * W)
    
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while len(que):
        p = que.popleft()
        if p == (gx, gy):
            break
        for i in range(4):
            nx = p[0] + dx[i]; ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] != '#' and d[nx][ny] == INF:
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

ans = 0
checked = []
for _ in range(H * W):
    checked.append([0] * (H * W))
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        for k in range(H):
            for l in range(W):
                if S[k][l] == '#':
                    continue
                if checked[i * W + j][k * W + l] == 1:
                    continue
                if i == k and j == l:
                    continue
                ans = max(bfs(i, j, k, l), ans)
                checked[i * W + j][k * W + l] = 1
                checked[k * W + l][i * W + j] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D幅優先探索
from collections import deque
h, w = list(map(int,input().split()))

def bfs(que,c):
    while que:
        c += 1
        qq = que
        que = deque([])
        while qq:
            x, y = qq.popleft()
            field[x][y] = "#"
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
        
                if 0 <= nx <= h-1 and 0 <= ny <= w-1 and field[nx][ny] == ".":
                    que.append((nx,ny))
            
    return c-1
            
A = [list(input()) for _ in range(h)]



dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque([]) 
ans = []

for p in range(h):
    for q in range(w):
        if A[p][q] == ".":
            field = [k[:] for k in A]
            
            que.append((p,q))
            ans.append(bfs(que,0))
print(max(ans))

Submission status: Time Limit Exceeded

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

def clear_maze(sx, sy, gx, gy, maze):
    INF = float('infinity')
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]

    def bfs():
        queue = deque([])
        queue.append((sx, sy))
        distance[sx][sy] = 0
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        while queue:
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]
                if (0 <= nx < field_x_length) and (0 <= ny < field_y_length):
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.appendleft((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1
        return distance[gx][gy]
    return bfs()


pairs = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            pairs.append([i, j])

MAX = 0
for i in range(len(pairs)):
    sx, sy = pairs[i]
    for j in range(len(pairs)):
        gx, gy = pairs[j]
        r = clear_maze(sx, sy, gx, gy, maze)
        if r == float('infinity'):
            continue
        MAX = max(MAX, r)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split(" ")]


class Node:
    def __init__(self, text, pos):
        self.text = text
        self.pos = pos
        self.next_nodes = []

    def add_next(self, node):
        self.next_nodes.append(node)


nodes = dict()
for i in range(H):
    for j, text in enumerate(input()):
        nodes[(i, j)] = Node(text, (i, j))


for i in range(H):
    for j in range(W):
        node = nodes[(i, j)]
        if node.text == "#":
            continue
        for pos in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
            if 0 <= pos[0] <= H-1 and 0 <= pos[1] <= W-1 and nodes[pos].text == ".":
                node.add_next(nodes[pos])


def all_pats():
    pat = []
    for i in range(H):
        for j in range(W):
            pat.append((i, j))
    return pat


def search(start, end):
    queue = []
    queue.append(start)
    count = dict()
    count[start.pos] = 0

    while True:
        if not queue:
            break
        node = queue[0]
        if node.pos == end:
            break
        queue = queue[1:]

        for next_node in node.next_nodes:
            if next_node.pos in count:
                continue
            count[next_node.pos] = count[node.pos] + 1
            queue.append(next_node)
    return count[end.pos]


total = []
for start in all_pats():
    for end in all_pats():
        start_node = nodes[start]
        end_node = nodes[end]
        if start_node.text == "." and end_node.text == ".":
            res = search(start_node, end_node)
            total.append(res)

print(max(total))

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
sys.setrecursionlimit(10**9)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: divisors.append(n//i)
    return divisors
def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False 
    return True
def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n + 1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def sieve_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime
def run_length_encode(s):
    count = 1
    code = []
    target = s[0]
    for i in range(1, len(s)):
        if target == s[i]: count += 1
        else:
            code.append((target, count))
            target = s[i]
            count = 1
    code.append((target, count))
    return code

H,W = imn()
S = [input() for _ in range(H)]
an = 10**10
def m(a, b, c, d, cnt, done):
    if a < 0 or a >= H or b < 0 or b >= W: return False
    if S[a][b] == '#': return False 
    do = copy.deepcopy(done)
    global an
    if a == c and b == d:
        an = min(an, cnt)
        return True
    else:
        do[a][b] = True
        cnt += 1
        if a-1 >= 0 and not done[a-1][b]: m(a-1,b,c,d,cnt,do)
        if b-1 >= 0 and not done[a][b-1]: m(a,b-1,c,d,cnt,do)
        if b+1 < W  and not done[a][b+1]: m(a,b+1,c,d,cnt,do)
        if a+1 < H  and not done[a+1][b]: m(a+1,b,c,d,cnt,do)
        return 
ans = -1
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                done = [[False for _ in range(W)]for _ in range(H)]
                m(i,j,k,l,0, copy.deepcopy(done))
                if an != 10**10:
                    ans = max(ans, an)
                an = 10**10 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
import itertools
r,c=map(int,input().split())
r += 2
c += 2
row = r
col = c
maze = [None for _ in range(r)]
maze[0] = ['#' for _ in range(c)]
maze[r - 1] = ['#' for _ in range(c)]
for i in range(1, r - 1):
  maze[i] = ['#'] + list(input()) + ['#']

PATH = '.'
WALL = '#'
UP = [1, 0]
DOWN = [-1, 0]
RIGHT = [0, 1]
LEFT = [0, -1]

list_r = [int(i) for i in range(1, r - 1)]
list_c = [int(i) for i in range(1, c - 1)]
zahyo = list(itertools.product(list_r, list_c))
sgs = list(itertools.product(zahyo, zahyo))

max_dis = 0
for sg in sgs:
  start_y, start_x = sg[0]
  goal_y, goal_x = sg[1]
  if start_y == goal_y and start_x == goal_x:
    continue
  if maze[start_y][start_x] == '#' or maze[goal_y][goal_x] == '#':
    continue

  GOAL = [goal_y, goal_x]
  queue = []
  distance = [[-1]*col for _ in range(row)]
  distance[start_y][start_x] = 0
  queue.append([start_y, start_x])
  while queue:
      current_y, current_x = queue.pop(0)
      if [current_y, current_x] == GOAL:
          dis = distance[current_y][current_x]
          if max_dis < dis:
            max_dis = dis
          # print(distance[current_y][current_x])
          break
          
      for y, x in [UP, DOWN, RIGHT, LEFT]:
          next_y, next_x = current_y + y, current_x + x
          if maze[next_y][next_x] == PATH and \
              distance[next_y][next_x] < 0:
              queue.append([next_y, next_x])
              distance[next_y][next_x] = distance[current_y][current_x] + 1
  # print('could not reach the goal')

print(max_dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]
INF = 10**9
def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]

ans = []
can = []
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                sx, sy = i, j
                gx, gy = k, l
                if c[sx][sy] == '#' or c[gx][gy] == '#':
                    continue
                can.append((sx, sy, gx, gy))

for sx, sy, gx, gy in can:
    ans.append(bfs())
                
ans = [i for i in ans if i != INF]
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd, deque

h,w = map(int,input().split())
M = [input().strip()+'#' for _ in range(h)]
M.append(w*'#')

road = []

start = None
for i in range(h):
    for j in range(w):
        if M[i][j] == '.':
            road.append((j,i))

def dist(aa,bb,cc,dd):
    Q = deque()
    Q.append((0, aa, bb))
    seen = set()
    while Q:
        d,x,y = Q.popleft()

        if (x,y) == (cc,dd):
            return d
        if (x,y) in seen: continue
        seen.add((x,y))

        for nx,ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
            if M[ny][nx] == '.':
                Q.append((d+1, nx, ny))

    raise AssertionError('D:')


print(max(dist(a[0], a[1], b[0], b[1]) for a in road for b in road))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
    l = []
    ans = 0
    for sy, sx in S:
      for gy, gx in G:
        if sy == gy and sx == gx:
          continue
        maze1 = copy.deepcopy(maze)
        maze1[sy][sx]=0
        que=deque([[sy,sx]])
        while que:
          y,x=que.popleft()
          for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!='#':
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                if nexty == gy and nextx == gx:
                  break
                que.append([nexty,nextx])
        ans = max(ans, maze1[gy][gx])
    print(ans)
bfs()