Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        while True:
            if len(plan) == 0:
                break
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            visited[y][x] = True
            if step > largest_step:
                largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        if largest_step > max_step:
            max_step = largest_step

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        while True:
            if len(plan) == 0:
                break
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            visited[y][x] = True
            if step > largest_step:
                largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if next_x == -1 or next_x == w or next_y == -1 or next_y == h:
                    continue
                if maze[next_y][next_x] == "#":
                    continue
                # 訪問済みでないかチェック
                if visited[next_y][next_x]:
                    continue
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        if largest_step > max_step:
            max_step = largest_step

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [input() for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

# BFSでは、同じステップ数のノードを先に全探索するので、訪問済みフラグはグローバル共有しても大丈夫

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        while True:
            if len(plan) == 0:
                break
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            visited[y][x] = True
            if step > largest_step:
                largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if next_x == -1 or next_x == w or next_y == -1 or next_y == h:
                    continue
                if maze[next_y][next_x] == "#":
                    continue
                # 訪問済みでないかチェック
                if visited[next_y][next_x]:
                    continue
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        if largest_step > max_step:
            max_step = largest_step

print(max_step)

Submission status: Time Limit Exceeded

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



def bfs(sh,sw,eh,ew,meiro):
	que=deque([[sh,sw]])
	dist=[[-1 for _ in range(w)] for _ in range(h)]
	dist[sh][sw]=0
	
	while True:
		check=que.popleft()
		hnow=check[0]
		wnow=check[1]
		
		dnow=dist[hnow][wnow]
		
		if hnow==eh and wnow== ew:
			return dnow
		
		hnext=hnow-1
		wnext=wnow
		if 0 < hnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow+1
		wnext=wnow
		if h-1 > hnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow
		wnext=wnow-1
		if 0 < wnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow
		wnext=wnow+1
		if w-1 > wnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1

roadlist=[]
for i in range(h):
	for j in range(w):
		if meiro[i][j] == ".":
			roadlist.append([i,j])

max=0
for start in roadlist:
	for end in roadlist:
		tmp=bfs(start[0],start[1],end[0],end[1],meiro)
		if tmp > max:
			max = tmp

print(max)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

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


def get_shortest_steps(S_inner, visited, i_inner, j_inner, steps):
    if i_inner == -1 or i_inner == h or j_inner == -1 or j_inner == w:
        return sys.maxsize
    if visited[i_inner * 20 + j_inner]:
        return sys.maxsize
    if S_inner[i_inner][j_inner] == "#":
        return sys.maxsize
    visited[i_inner * 20 + j_inner] = True
    if shortest_steps_map[i_inner * 20 + j_inner] > steps:
        shortest_steps_map[i_inner * 20 + j_inner] = steps
    get_shortest_steps(S_inner, copy.copy(visited), i_inner + 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner + 1, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner - 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner - 1, steps + 1)
    return


result = -1
for i_outer in range(h):
    for j_outer in range(w):
        visited_outer = [False] * (h * 20 + w + 1)
        shortest_steps_map = [500] * (h * 20 + w + 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer, 0)

        for i in range(len(shortest_steps_map)):
            if shortest_steps_map[i] == 500:
                shortest_steps_map[i] = 0

        if max(shortest_steps_map) > result:
            result = max(shortest_steps_map)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

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


def get_shortest_steps(S, visited, i, j, l, m, steps):
    if i == l and j == m:
        return steps
    if i == -1 or i == h or j == -1 or j == w:
        return sys.maxsize
    if visited[i * 20 + j]:
        return sys.maxsize
    if S[i][j] == "#":
        return sys.maxsize
    visited[i * 20 + j] = True
    returned_steps1 = get_shortest_steps(S, copy.copy(visited), i + 1, j, l, m, steps + 1)
    returned_steps2 = get_shortest_steps(S, copy.copy(visited), i, j + 1, l, m, steps + 1)
    returned_steps3 = get_shortest_steps(S, copy.copy(visited), i - 1, j, l, m, steps + 1)
    returned_steps4 = get_shortest_steps(S, copy.copy(visited), i, j - 1, l, m, steps + 1)
    # print(returned_steps1, returned_steps2, returned_steps3, returned_steps4)
    return min(returned_steps1, returned_steps2, returned_steps3, returned_steps4)


result = -1
for i in range(h):
    for j in range(w):
        for l in range(h):
            for m in range(w):
                visited = [False] * (h * 20 + w + 1)
                shortest_steps = get_shortest_steps(S, visited, i, j, l, m, 0)
                if shortest_steps == sys.maxsize:
                    continue
                if shortest_steps > result:
                    result = shortest_steps
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

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


def get_shortest_steps(S, visited, i, j, l, m, steps):
    if i == l and j == m:
        return steps
    if i == -1 or i == h or j == -1 or j == w:
        return sys.maxsize
    if visited[i][j]:
        return sys.maxsize
    if S[i][j] == "#":
        return sys.maxsize
    visited[i][j] = True
    returned_steps1 = get_shortest_steps(S, copy.deepcopy(visited), i + 1, j, l, m, steps + 1)
    returned_steps2 = get_shortest_steps(S, copy.deepcopy(visited), i, j + 1, l, m, steps + 1)
    returned_steps3 = get_shortest_steps(S, copy.deepcopy(visited), i - 1, j, l, m, steps + 1)
    returned_steps4 = get_shortest_steps(S, copy.deepcopy(visited), i, j - 1, l, m, steps + 1)
    # print(returned_steps1, returned_steps2, returned_steps3, returned_steps4)
    return min(returned_steps1, returned_steps2, returned_steps3, returned_steps4)


result = -1
for i in range(h):
    for j in range(w):
        for l in range(h):
            for m in range(w):
                visited = [[False] * w for _ in range(h)]
                shortest_steps = get_shortest_steps(S, visited, i, j, l, m, 0)
                if shortest_steps == sys.maxsize:
                    continue
                if shortest_steps > result:
                    result = shortest_steps
print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ret = 0
for i in range(H):
    for j in range(W):
        s = S[i][j]
        queue = deque([(i,j,0)])
        footprint = [(i,j)]
        if s == '#':
            continue
        while True:
            x, y, d = queue.popleft()
            for p in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if p[0] >= 0 and p[0] < H and p[1] >=0 and p[1] < W and p not in footprint and S[p[0]][p[1]] != '#':
                        queue.append((p[0], p[1], d+1))
                        footprint.append(p)

            if len(queue) == 0:
                break
        if d > ret:
            ret = d

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [readline().rstrip().decode() for _ in range(h)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
sg = []
memo = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sg.append((i, j))
        else:
            memo[i][j] = True
ans = 0
for ss in sg:
    for g in sg:
        if ss == g:
            continue
        q = [ss]
        cnt = 0
        dist = deepcopy(memo)
        dist[ss[0]][ss[1]] = True
        while q:
            cnt += 1
            qq = []
            for y, x in q:
                for dy, dx in move:
                    xx, yy = x + dx, y + dy
                    if xx < 0 or yy > h - 1 or yy < 0 or xx > w - 1:
                        continue
                    if dist[yy][xx]:
                        continue
                    dist[yy][xx] = True
                    qq.append((yy, xx))
            q = qq
            if g in q:
                ans = max(ans, cnt)
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [readline().rstrip().decode() for _ in range(h)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
sg = []
memo = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sg.append((i, j))
        else:
            memo[i][j] = True
ans = 0
for ss in sg:
    for g in sg:
        q = [ss]
        cnt = 0
        dist = deepcopy(memo)
        dist[ss[0]][ss[1]] = True
        flag = False
        while q:
            cnt += 1
            qq = []
            for y, x in q:
                for dy, dx in move:
                    xx, yy = x + dx, y + dy
                    if xx < 0 or yy > h - 1 or yy < 0 or xx > w - 1:
                        continue
                    if dist[yy][xx]:
                        continue
                    dist[yy][xx] = True
                    if (yy, xx) == g:
                        flag = True
                        ans = max(ans, cnt)
                        break
                    qq.append((yy, xx))
            q = qq
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w=map(int,input().split())
maze=[list(input()) for _ in range(h)]
df=[(1,0),(-1,0),(0,1),(0,-1)]
ans=0
for a in range(h):
  for b in range(w):
    if maze[a][b]=='#':
        continue
    for c in range(h):
      for d in range(w):
        if a==c and b==d:
          continue
        pos=[[a,b,0]]
        meiro=copy.deepcopy(maze)
        while len(pos):
          x,y,depth=pos.pop(0)
          if x==c and y==d:
            ans=max(ans,depth)
            break
          meiro[x][y]='#'
          for dx,dy in df:
            if 0<=x+dx<h and 0<=y+dy<w and meiro[x+dx][y+dy]=='.':
                pos.append([x+dx,y+dy,depth+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
蟻本p37にスタート・ゴールの座標が決まっている場合のコードがある
この問題ではスタート・ゴールの座標が決まっていないので以下のように改変する
"""
h, w = list(map(int, input().split()))
field = [input() for _ in range(h)]

INF = 10**8
d = [[0]*w for i in range(h)] # 各点までの最短距離の配列
dx = [1,0,-1,0]; dy = [0,1,0,-1] # 移動4方向のベクトル

# (sx, sy)から(gx, gy)への最短距離を求める
# たどり着けないとINF
import queue

def bfs(sx, sy, gx, gy):
    que = queue.Queue()
    # 全ての点をINFで初期化
    for i in range(h):
        for j in range(w):
            d[i][j] = INF
    # スタート地点をキューに入れ、その点の距離を0にする
    que.put([sx, sy])
    d[sx][sy] = 0
    
    # キューが空になるまでループ
    while que.qsize():
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索を辞める
        if p[0] == gx and p[1] == gy: break
        
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を(nx, ny)とする
            nx = p[0] + dx[i]; ny = p[1] + dy[i]

            # 移動が可能かの判定と既に訪れたことがあるかの判定(d[nx][ny] != INF なら訪れたことあり)
            if 0 <= nx and nx < h and 0 <= ny and ny < w and field[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.put([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
            
    return d[gx][gy]

# この問題ではスタート・ゴールの位置が決まっていないので取り得る位置の組み合わせを列挙する
from itertools import combinations

sg_candidates = []
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            sg_candidates.append((i,j))
sg_pairs = combinations(sg_candidates, 2)

ans = 0
for s,g in sg_pairs:
    res = bfs(s[0],s[1],g[0],g[1])
    ans = max(res, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
if __name__ == "__main__":
    h, w = map(int, input().split())
    s = []

    for _ in range(h):
        h_i = input()
        s.append(h_i)

    
    ans = (-1)*float('inf')
    
    
    for s_r in range(h):
        for s_c in range(w):
            if s[s_r][s_c] == "#":
                continue
            visited = []
            for _ in range(h):
                w_i = [False] * w
                visited.append(w_i)
            d = deque()
            d.appendleft((s_r, s_c, 0))
            part = 0
            while d:
                now = d.pop()
                visited[now[0]][now[1]] = True
                part = max(now[2], part)
                if now[0] + 1 < h and s[now[0] + 1][now[1]] != "#" and not visited[now[0] + 1][now[1]]:
                    d.appendleft((now[0] + 1, now[1], now[2] + 1))
                if now[0] - 1 >= 0 and s[now[0] - 1][now[1]] != "#" and not visited[now[0] - 1][now[1]]:
                    d.appendleft((now[0] - 1, now[1], now[2] + 1))
                if now[1] + 1 < w and s[now[0]][now[1] + 1] != "#" and not visited[now[0]][now[1] + 1]:
                    d.appendleft((now[0], now[1]+1, now[2] + 1))
                if now[1] - 1 >= 0 and s[now[0]][now[1] - 1] != "#" and not visited[now[0]][now[1] - 1]:
                    d.appendleft((now[0], now[1] - 1, now[2] + 1))
            if ans < part:
                ans = part
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    queue = [start]
    depth = 0
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check[x][y] = True
        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if not check[t[0]][t[1]]:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = np.array([[-1 for _ in range(w)] for _ in range(h)])
    check = set()
    queue = [start]
    depth = 0
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = np.array([[-1 for _ in range(w)] for _ in range(h)])
    check = set()
    queue = [start]
    depth = 0
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])

    return length.max()


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = set()
    queue = [start]
    depth = 0
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res, length[i][j])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = set()
    queue = [start]
    depth = 0
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res, length[i][j])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
import sys
def I(): return int(input())  # '123' -> 123
def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]
def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']
def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

h, w = Is()
maze = LSR(h)

def bfs(sy, sx, gy, gx):
    vmaze = [[INF] * w for _ in range(h)]
    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    que = deque()
    que.append((sy, sx))
    vmaze[sy][sx] = 0

    while que:
        py, px = que.popleft()
        if py == gy and px == gx:
            break
        for ymove, xmove in move:
            ny = py + ymove
            nx = px + xmove
            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] != '#' and vmaze[ny][nx] == INF:
                vmaze[ny][nx] = vmaze[py][px] + 1
                que.append((ny, nx))

    return vmaze[gy][gx]

ans = 0
for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '#':
            continue
        for gy in range(h):
            for gx in range(w):
                if maze[gy][gx] == '#':
                    continue

                ans = max(ans, bfs(sy, sx, gy, gx))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

def bfs(sx, sy):
    s = [[-1] * W for _ in range(H)]
    d = [[0] * W for _ in range(H)]

    que = deque([])
    que.append((sx, sy))
    s[sy][sx] = 1

    res = 0
    while que:
        x, y = que.popleft()
        s[y][x] = 1

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

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] == -1 and c[ny][nx] == '.':
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1
                res = max(res, d[ny][nx])

    return res

ans = 0
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = bfs(j, i)
            ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

def bfs(sx, sy):
    s = [[-1] * W for _ in range(H)]
    d = [[0] * W for _ in range(H)]

    que = deque([])
    que.append((sx, sy))
    s[sy][sx] = 1

    res = 0
    while que:
        x, y = que.popleft()
        s[y][x] = 1

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

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] == -1 and c[ny][nx] == '.':
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1
                res = max(res, d[ny][nx])

    return res

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

def bfs(sx, sy):
    s = [[-1] * W for _ in range(H)]
    d = [[0] * W for _ in range(H)]

    que = deque([])
    que.append((sx, sy))
    s[sy][sx] = 1

    while que:
        x, y = que.popleft()
        s[y][x] = 1

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

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] == -1 and c[ny][nx] == '.':
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1

    return max([max(v) for v in d])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import combinations

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

points = []
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            points.append((j, i))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]        
def bfs(start, goal):
    s = [[-1] * W for _ in range(H)]
    d = [[0] * W for _ in range(H)]

    sx, sy = start
    gx, gy = goal

    que = deque([])
    que.append((sx, sy))
    s[sy][sx] = 1
    
    while que:
        x, y = que.popleft()
        s[y][x] = 1

        if x == gx and y == gy:
            return d[y][x]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != 1 and c[ny][nx] == '.':
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1

ans = 0
for comb in combinations(points, 2):
    start, goal = comb
    ans = max(ans, bfs(start, goal))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  H, W = map(int, input().split())
  graph = [['#'] * (W+2) for _ in range(H+2)]
  for i in range(H):
    S = input()
    for j in range(W):
      graph[i+1][j+1] = S[j]

  def dfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[sx][sy] = 0
    while q:
      x, y = q.popleft()
      dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
      for dx, dy in dxy:
        nextx = x+dx
        nexty = y+dy
        if(dist[nextx][nexty] >= 0):
          continue
        if(graph[nextx][nexty] == '#'):
          continue
        dist[nextx][nexty] = dist[x][y] + 1
        q.append((nextx, nexty))
    return dist[gx][gy]

  ans = 0  
  for sx in range(1, H+1):
    for sy in range(1, W+1):
      for gx in range(1, H+1):
        for gy in range(1, W+1):
          if(graph[sx][sy] == '.' and graph[gx][gy] == '.'):
            tmp = dfs(sx, sy, gx, gy)
            ans = max(ans, tmp)
          
  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
graph = [['#'] * (W+2) for _ in range(H+2)]
for i in range(H):
  S = input()
  for j in range(W):
    graph[i+1][j+1] = S[j]

def dfs(sx, sy, gx, gy):
  q = deque([(sx, sy)])
  dist = [[-1] * (W+2) for _ in range(H+2)]
  dist[sx][sy] = 0
  while q:
    x, y = q.popleft()
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for dx, dy in dxy:
      nextx = x+dx
      nexty = y+dy
      if(dist[nextx][nexty] >= 0):
        continue
      if(graph[nextx][nexty] == '#'):
        continue
      dist[nextx][nexty] = dist[x][y] + 1
      q.append((nextx, nexty))
  return dist[gx][gy]

ans = 0  
for sx in range(1, H+1):
  for sy in range(1, W+1):
    for gx in range(1, H+1):
      for gy in range(1, W+1):
        if(graph[sx][sy] == '.' and graph[gx][gy] == '.'):
          tmp = dfs(sx, sy, gx, gy)
          ans = max(ans, tmp)
          
print(ans)