Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for m in range(w):
                if i > k:
                    continue
                if s[i][j] == "#" or s[k][m] == "#":
                    continue
                queue = deque([[i, j, 0]])
                visited = [[0 for _ in range(w)] for _ in range(h)]
                while queue:
                    y, x, cnt = queue.popleft()
                    if y == k and x == m:
                        ans = max(ans, cnt)
                        break
                    visited[y][x] = 1
                    for p in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        y2 = y + p[0]
                        x2 = x + p[1]
                        if not (0 <= y2 < h and 0 <= x2 < w) or visited[y2][x2] == 1 or s[y2][x2] == "#":
                            continue
                        queue.append([y2, x2, cnt + 1])
# print(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for m in range(w):
                if s[i][j] == "#" or s[k][m] == "#":
                    continue
                queue = deque([[i, j, 0]])
                visited = [[0 for _ in range(w)] for _ in range(h)]
                while queue:
                    y, x, cnt = queue.popleft()
                    if y == k and x == m:
                        ans = max(ans, cnt)
                        break
                    visited[y][x] = 1
                    for p in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        y2 = y + p[0]
                        x2 = x + p[1]
                        if not (0 <= y2 < h and 0 <= x2 < w) or visited[y2][x2] == 1 or s[y2][x2] == "#":
                            continue
                        queue.append([y2, x2, cnt + 1])
# print(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for m in range(w):
                if s[i][j] == "#" or s[k][m] == "#":
                    continue
                queue = deque([[i, j, 0]])
                visited = [[0 for _ in range(w)] for _ in range(h)]
                while queue:
                    y, x, cnt = queue.popleft()
                    if y == k and x == m:
                        ans = max(ans, cnt)
                        break
                    if not (0 <= y < h and 0 <= x < w) or visited[y][x] == 1 or s[y][x] == "#":
                        continue
                    visited[y][x] = 1
                    for p in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        y2 = y + p[0]
                        x2 = x + p[1]
                        if not (0 <= y2 < h and 0 <= x2 < w):
                            continue
                        queue.append([y2, x2, cnt + 1])
# print(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
H,W = list(map(int,input().split()))

Maze = []
for i in range(H):
    Maze.append(str(input().split()[0]))



def dfs(x,y,seen,ans):
    Map[y][x] = min(Map[y][x],ans)
    for c in [[1,0],[0,1],[-1,0],[0,-1]]:
        if 0<=x+c[0]<W and 0<=y+c[1]<H:
            if Maze[y+c[1]][x+c[0]] == '.'  and [x+c[0],y+c[1]] not in seen:
                seen.append([x+c[0],y+c[1]])
                dfs(x+c[0],y+c[1],seen,ans+1)
                seen.pop(-1)

maxL = []
MapSet = [[np.inf if Maze[j][i]=='.' else -np.inf for i in range(W)] for j in range(H)]
for i in range(W):
    for j in range(H):
        if Maze[j][i] == '.':
            Map = copy.deepcopy(MapSet)
            dfs(i,j,[i,j],0)
            maxL.append(np.array(Map).max())
print(int(max(maxL)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W = list(map(int,input().split()))

Maze = []
for i in range(H):
    Maze.append(str(input().split()[0]))



def dfs(x,y,seen,ans):
    Map[y][x] = min(Map[y][x],ans)
    for c in [[1,0],[0,1],[-1,0],[0,-1]]:
        if 0<=x+c[0]<W and 0<=y+c[1]<H:
            if Maze[y+c[1]][x+c[0]] == '.'  and [x+c[0],y+c[1]] not in seen:
                seen.append([x+c[0],y+c[1]])
                dfs(x+c[0],y+c[1],seen,ans+1)
                seen.pop(-1)

maxL = []
#MapSet = [[np.inf if Maze[j][i]=='.' else -np.inf for i in range(W)] for j in range(H)]
for i in range(W):
    for j in range(H):
        if Maze[j][i] == '.':
            Map = [[np.inf if Maze[j][i]=='.' else -np.inf for i in range(W)] for j in range(H)]
            dfs(i,j,[i,j],0)
            maxL.append(np.array(Map).max())
print(int(max(maxL)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    HW = []
    for h in range(H):
        for w in range(W):
            if S[h][w] != "#":
                HW.append([h, w])

    res = 0
    for i in range(len(HW)):
        for j in range(i + 1, len(HW)):
            sh, sw = HW[i]
            gh, gw = HW[j]
            maze = [[f_inf] * W for _ in range(H)]
            maze[sh][sw] = 0
            que = deque([[sh, sw]])
            while que:
                h, w = que.popleft()
                for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                        continue
                    elif S[next_h][next_w] == "#":
                        continue
                    else:
                        if maze[next_h][next_w] > maze[h][w] + 1:
                            maze[next_h][next_w] = maze[h][w] + 1
                            que.append([next_h, next_w])
            if maze[gh][gw] != f_inf:
                res = max(res, maze[gh][gw])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    start, goal = [], []
    for h in range(H):
        for w in range(W):
            if S[h][w] != "#":
                start.append([h, w])
                goal.append([h, w])
                
    res = 0
    for sh, sw in start:
        for gh, gw in goal:
            maze = [[f_inf] * W for _ in range(H)]
            maze[sh][sw] = 0
            que = deque([[sh, sw]])
            while que:
                h, w = que.popleft()
                for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                        continue
                    elif S[next_h][next_w] == "#":
                        continue
                    else:
                        if maze[next_h][next_w] > maze[h][w] + 1:
                            maze[next_h][next_w] = maze[h][w] + 1
                            que.append([next_h, next_w])
            if maze[gh][gw] != f_inf:
                res = max(res, maze[gh][gw])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for sh in range(H):
        for sw in range(W):
            if S[sh][sw] != "#":
                for gh in range(H):
                    for gw in range(W):
                        if S[gh][gw] != "#":
                            maze = [[f_inf] * W for _ in range(H)]
                            maze[sh][sw] = 0
                            que = deque([[sh, sw]])
                            while que:
                                h, w = que.popleft()
                                for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                                    next_h, next_w = h + dh, w + dw
                                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                                        continue
                                    elif S[next_h][next_w] == "#":
                                        continue
                                    else:
                                        if maze[next_h][next_w] > maze[h][w] + 1:
                                            maze[next_h][next_w] = maze[h][w] + 1
                                            que.append([next_h, next_w])
                            if maze[gh][gw] != f_inf:
                                res = max(res, maze[gh][gw])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
def main():
    H, W = list(map(int, input().split()))
    A = np.array([['#'] * (W + 2)] + [['#', ] + list(input()) + ['#', ] for _ in range(H)] + [['#'] * (W + 2)])
    DXY = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = 0
    INF = 10000
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if A[h, w] == '#':
                continue
            count = np.where(A == '.', INF, -1)
            count[h, w] = 0
            stack = deque([[h, w], ])
            visited = [[0] * W for _ in range(H)]
            while stack:
                x, y = stack.popleft()
                if visited[x - 1][y - 1] == 1:
                    continue
                else:
                    visited[x - 1][y - 1] = 1
                for (dx, dy) in DXY:
                    X = x + dx
                    Y = y + dy
                    if A[X][Y] == '.':
                        if visited[X - 1][Y - 1] == 0:
                            stack.append([X, Y])
                        count[X, Y] = min(count[X, Y], count[x, y] + 1)
            ans = max(ans, np.max(count))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
G = []
for i in range(H+2):
    if i == 0 or i == H+1:
        G.append('#'*(W+2))
    else:
        G.append('#' + input() + '#')

ans = 0
for sx in range(W+2):
    for sy in range(H+2):
        for gx in range(W+2):
            for gy in range(H+2):
                if G[sy][sx] == '.' and G[gy][gx] == '.':
                    dist = [[-float('inf') for i in range(W+2)] for i in range(H+2)]
                    visited = [[-1 for i in range(W+2)] for i in range(H+2)]
                    q = deque([])
                    q.append((sx, sy))
                    dist[sy][sx] = 0
                    visited[sy][sx] = 1
                    while q:
                        x, y = q.popleft()
                        if x == gx and y == gy:
                            break
                        if G[y][x+1] == '.' and visited[y][x+1] == -1:
                            q.append((x+1, y))
                            dist[y][x+1] = dist[y][x] + 1
                            visited[y][x+1] = 1
                        if G[y][x-1] == '.' and visited[y][x-1] == -1:
                            q.append((x-1, y))
                            dist[y][x-1] = dist[y][x] + 1
                            visited[y][x-1] = 1
                        if G[y+1][x] == '.' and visited[y+1][x] == -1:
                            q.append((x, y+1))
                            dist[y+1][x] = dist[y][x] + 1
                            visited[y+1][x] = 1
                        if G[y-1][x] == '.' and visited[y-1][x] == -1:
                            q.append((x, y-1))
                            dist[y-1][x] = dist[y][x] + 1
                            visited[y-1][x] = 1
                    ans = max(ans, dist[gy][gx])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
G = []
for i in range(H+2):
    if i == 0 or i == H+1:
        G.append('#'*(W+2))
    else:
        G.append('#' + input() + '#')

ans = 0
for sx in range(W+2):
    for sy in range(H+2):
        for gx in range(W+2):
            for gy in range(H+2):
                if G[sy][sx] == '.' and G[gy][gx] == '.':
                    dist = [[-float('inf') for i in range(W+2)] for i in range(H+2)]
                    visited = [[-1 for i in range(W+2)] for i in range(H+2)]
                    q = deque([])
                    q.append((sx, sy))
                    dist[sy][sx] = 0
                    visited[sy][sx] = 1
                    while q:
                        x, y = q.popleft()
                        if G[y][x+1] == '.' and visited[y][x+1] == -1:
                            q.append((x+1, y))
                            dist[y][x+1] = dist[y][x] + 1
                            visited[y][x+1] = 1
                        if G[y][x-1] == '.' and visited[y][x-1] == -1:
                            q.append((x-1, y))
                            dist[y][x-1] = dist[y][x] + 1
                            visited[y][x-1] = 1
                        if G[y+1][x] == '.' and visited[y+1][x] == -1:
                            q.append((x, y+1))
                            dist[y+1][x] = dist[y][x] + 1
                            visited[y+1][x] = 1
                        if G[y-1][x] == '.' and visited[y-1][x] == -1:
                            q.append((x, y-1))
                            dist[y-1][x] = dist[y][x] + 1
                            visited[y-1][x] = 1
                    ans = max(ans, dist[gy][gx])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import pprint
H,W=map(int,input().split())
import copy
lastraw=["#"]*(W+2)
field=[["#"]*(W+2)]
for i in range(H):
  field.append(["#"]+list(input())+["#"])

field.append(lastraw)
maxmoves=0
#print(field)
saved_field=copy.deepcopy(field)

for i in range(H):
  for j in range(W):
    field=copy.deepcopy(saved_field)
    goal_point=(0,0)
    [sy,sx]=[j+1,i+1]
    [gy,gx]=[0,0]

    queue=[[sy,sx]]
    tests = ((-1,0),(0, 1),(1, 0),(0, -1))
    moves=0

    if field[sx][sy]=='#':
      queue=[]
    else:
      field[sx][sy]=0

    while True:
      if len(queue)==0:
        maxmoves=max(maxmoves,moves-1)
        break
      queue_next = []
      moves += 1
      #pprint.pprint(field)
      for y, x in queue:
        for ny, nx in tests:
          ty, tx = y + ny, x + nx
          if field[tx][ty] == '.' or field[tx][ty] ==moves:
            field[tx][ty] = moves
            queue_next.append((ty, tx))
      queue = queue_next
      if goal_point in queue:
        break
        #pprint.pprint(field)
        maxmoves=max(maxmoves,moves)
print(maxmoves)

Submission status: Time Limit Exceeded

Solution code:
import pprint
H,W=map(int,input().split())
import copy
lastraw=["#"]*(W+2)
field=[["#"]*(W+2)]
for i in range(H):
  field.append(["#"]+list(input())+["#"])

field.append(lastraw)
maxmoves=0
#print(field)
saved_field=copy.deepcopy(field)

for i in range(H):
  for j in range(W):
    for k in range(H):
      for l in range(W):
        field=copy.deepcopy(saved_field)
        goal_point=(l+1,k+1)
        [sy,sx]=[j+1,i+1]
        [gy,gx]=[l+1,k+1]

        queue=[[sy,sx]]
        tests = ((-1,0),(0, 1),(1, 0),(0, -1))
        moves=0

        if field[sx][sy]=='#':
          queue=[]
        else:
          field[sx][sy]=0

        while True:
          if len(queue)==0:
            moves=-1
            break
          queue_next = []
          moves += 1
          #pprint.pprint(field)
          for y, x in queue:
            for ny, nx in tests:
              ty, tx = y + ny, x + nx
              if field[tx][ty] == '.' or field[tx][ty] ==moves:
                field[tx][ty] = moves
                queue_next.append((ty, tx))
          queue = queue_next
          if goal_point in queue:
            break
        #pprint.pprint(field)
        maxmoves=max(maxmoves,moves)
print(maxmoves)

Submission status: Time Limit Exceeded

Solution code:
# ABC151 D-Maze Master
import queue
H,W = map(int,input().split())
maze = [input() for _ in range(H)]
dydx = ((0,1),(0,-1),(1,0),(-1,0))

def reach(sy,sx,gy,gx):
    visited = [[0]*W for _ in range(H)]
    q = queue.Queue()
    q.put((sy,sx,0))
    while(not q.empty()):
        y,x,d = q.get()
        if [y,x] == [gy,gx]:
            ans = d
            break
        for dy,dx in dydx:
            if (0<=y+dy<H)&(0<=x+dx<W):
                if maze[y+dy][x+dx] == '#' or visited[y+dy][x+dx] == 1:
                    continue
                visited[y+dy][x+dx] = 1
                q.put((y+dy,x+dx,d+1))
    return ans

d = -1
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] == '#' or [sy,sx] == [gy,gx]:
                    continue
                d = max(d,reach(sy,sx,gy,gx))
                
print(d)