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: Wrong Answer

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):
                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: Wrong Answer

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):
                queue = deque([[i, j, 0]])
                visited = [[0 for j in range(w)] for i 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: Wrong Answer

Solution code:
import collections, copy

h, w = map(int, input().split())
maze = []
maze.append("#" * (w + 2))
for i in range(h):
    maze.append("#" + input() + "#")
maze.append("#" * (w + 2))
dis = []
for i in range(h + 2):
    temp = [-1] * (w + 2)
    dis.append(temp)

def search(x, y):
    dis2 = copy.deepcopy(dis)
    move = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    queue = collections.deque([[x, y]])
    dis2[x][y] = 0
    while queue:
        test = queue.popleft()
        for i in move:
            place = [test[0] + i[0], test[1] + i[1]]
            if maze[place[0]][place[1]] == ".":
                if dis2[place[0]][place[1]] == -1:
                    dis2[place[0]][place[1]] = dis2[test[0]][test[1]] + 1
                    queue.append(place)
    return max([max([dis2[i][j] for j in range(w + 2)]) for i in range(h + 2)])

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i + 1][j + 1] == ".":
            dist = search(i + 1, j + 1)
            ans = max(ans, dist)
            print([i + 1, j + 1], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Sss = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

def bfsGridGraph(Sss, xS, yS, INF):
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]
    distss = [[(INF if S != '#' else -1) for S in Ss] for Ss in Sss]
    distss[xS][yS] = 0
    Q = deque([(xS, yS)])
    while Q:
        x, y = Q.popleft()
        dist = distss[x][y]
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if distss[x2][y2] == INF:
                distss[x2][y2] = dist + 1
                Q.append((x2, y2))
    return distss

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        distss = bfsGridGraph(Sss, i, j, INF)
        maxDist = max(map(max, distss))
        ans = max(ans, maxDist)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))
for i in range(h):
    j=input()
    l.append('#'+j+'#')
l.append('#'*(w+2))
def bfs(a,b):
  s=[[-1 for j in i] for i in l]
  s[a][b]=0
  q=deque([[a,b]])
  while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
      if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
        q.append([x+i,y+j])
        s[x+i][y+j]=s[x][y]+1
        num = s[x+i][y+j]
        c = x+i
        d = y+j
  return([c,d,num])
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      z = bfs(i,j)
      y = bfs(z[0],z[1])
      print(bfs(y[0],y[1])[2])
      exit(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))
for i in range(h):
    j=input()
    l.append('#'+j+'#')
l.append('#'*(w+2))
def bfs(a,b):
  s=[[-1 for j in i] for i in l]
  s[a][b]=0
  q=deque([[a,b]])
  while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
      if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
        q.append([x+i,y+j])
        s[x+i][y+j]=s[x][y]+1
        num = s[x+i][y+j]
        c = x+i
        d = y+j
  return([c,d,num])
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      z = bfs(i,j)
      print(bfs(z[0],z[1])[2])
      exit(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)

H, W = (None, None)
S = None


def bfs(h, w):
    q = queue.Queue()
    q.put((w, h))
    steps = [[-1 for _ in range(W)]for _ in range(H)]
    steps[h][w] = 0
    while not q.empty():
        p = q.get()
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for d in DIR:
            n = (p[0] + d[0], p[1] + d[1])
            if not (0 <= n[0] < W and 0 <= n[1] < H):
                continue
            if steps[n[1]][n[0]] != -1:
                continue
            if S[n[1]][n[0]] == '#':
                continue
            steps[n[1]][n[0]] = steps[p[1]][p[0]] + 1
            q.put(n)
    res = 0
    for s in steps:
        res = max(res, max(s))
    return res


def solve():
    global H, W, S
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, bfs(h, w))
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [list("#"+input()) for _ in range(H)] + [["#"]*(W+1)]
#print(S)
m = 0

for i in range(1, H+1):
    for j in range(1, W+1):
        if S[H-i][j] == "#":
            continue

        else:
            seen = [[False for _ in range(W+1)] for _ in range(H+1)]
            seen[H-i][j]=True
            #print(seen)

            D = [-1, 1]
            stack = [[H-i, j]]
            r = -1

            while stack:
                now = stack.pop()
                h = now[0]
                w = now[1]
                if h == 0 and w == W-1:
                    break
                #print(S[h][0][w])
                for d in D:
                    try:
                        if seen[h-d][w] ==True:
                            pass
                        elif S[h-d][w] == ".":
                            stack.append([h-d, w])
                            seen[h-d][w] = True
                    except:
                        pass
                    try:
                        if seen[h][w+d] ==True:
                            pass
                        elif S[h][w+d] == ".":
                            stack.append([h, w+d])
                            seen[h][w+d] = True
                    except:
                        pass
                #print(seen)
                r += 1
            m = max(m, r)
            #print(seen)
print(m)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [list("#"+input()) for _ in range(H)] + [["#"]*(H+1)]
#print(S)

seen = [[False for _ in range(W+1)] for _ in range(H+1)]
seen[H-1][1]=True
#print(seen)

D = [-1, 1]
stack = [[H-1, 1]]
i = -1

while stack:
    now = stack.pop()
    h = now[0]
    w = now[1]
    if h == 0 and w == W-1:
        break
    #print(S[h][0][w])
    for d in D:
        try:
            if seen[h-d][w] ==True:
                pass
            elif S[h-d][w] == ".":
                stack.append([h-d, w])
                seen[h-d][w] = True
        except:
            pass
        try:
            if seen[h][w+d] ==True:
                pass
            elif S[h][w+d] == ".":
                stack.append([h, w+d])
                seen[h][w+d] = True
        except:
            pass
    #print(seen)
    i += 1

#print(seen)
print(i)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

h, w = map(int, input().split())
ini_grid = []
ans = 0
for i in range(h):
    s = list(input())
    ini_grid.append(s)

dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(h):
    for j in range(w):
        if ini_grid[i][j] == '.':
            temp_grid = [row[:] for row in ini_grid]
            dis_grid = [[-1]*w for i in range(h)]
            dis_grid[i][j] = 0
            dq = deque([(i, j, 0)])
            while dq:
                curr = dq.popleft()
                for di, dj in dd:
                    ni = curr[0] + di
                    nj = curr[1] + dj 
                    if (0 <= ni <= h-1) and (0 <= nj <= w-1) and temp_grid[ni][nj] == '.':
                        temp_grid[ni][nj] = '#'
                        dis_grid[ni][nj] = curr[2] + 1
                        dq.append((ni, nj, curr[2] + 1))
                        if curr[2] + 1 > ans:
                            ans = curr[2] + 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

h, w = map(int, input().split())
ini_grid = []
ans = 0
for i in range(h):
    s = list(input())
    ini_grid.append(s)

dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(h):
    for j in range(w):
        if ini_grid[i][j] == '.':
            temp_grid = [row[:] for row in ini_grid]
            dis_grid = [[-1]*w for i in range(h)]
            dis_grid[i][j] = 0
            dq = deque([(i, j, 0)])
            while dq:
                curr = dq.popleft()
                for di, dj in dd:
                    ni = curr[0] + di
                    nj = curr[1] + dj 
                    if (0 <= ni <= h-1) and (0 <= nj <= w-1) and temp_grid[ni][nj] == '.':
                        temp_grid[ni][nj] = '#'
                        dis_grid[ni][nj] = curr[2] + 1
                        dq.append((ni, nj, curr[2] + 1))
                        if curr[2] + 1 > ans:
                            ans = curr[2] + 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for i in range(H):
  S.append(input())
ans=0
  
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      L=[[-1]*W for i in range(H)]
      L[i][j]=0
      q=queue.Queue()
      q.put([i,j])
      while not q.empty():
        r=q.get()
        for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
          if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==-1:
            L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
            q.put([r[0]+k,r[1]+l])
      if max(max(L))>ans:
        ans=max(max(L))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for i in range(H):
  S.append(input())
ans=0
  
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      L=[[-1]*W for i in range(H)]
      q=queue.Queue()
      q.put([i,j])
      while not q.empty():
        r=q.get()
        for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
          if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==-1:
            L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
            q.put([r[0]+k,r[1]+l])
      if max(max(L))>ans:
        ans=max(max(L))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for i in range(H):
  S.append(input())
ans=0
  
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      L=[[0]*W for i in range(H)]
      q=queue.Queue()
      q.put([i,j])
      while not q.empty():
        r=q.get()
        for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
          if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==0:
            L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
            q.put([r[0]+k,r[1]+l])
      if max(max(L))>ans:
        ans=max(max(L))
print(ans)

Submission status: Wrong Answer

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):
            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: Wrong Answer

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

f = []
for i in range(h):
    s = list(map(lambda x:0 if x== "." else 1,list(input())))
    f.append(s)

from collections import deque
def dfs_field(field,st,go):
    """
    :param field: #が1,.が0になったfield
    st: [i,j]
    go: [i,j]
    :return: 色々今は回数returnしている。
    """
    h = len(field)
    w = len(field[0])
    around = [[-1,0],[1,0],[0,1],[0,-1]]
    que = deque()
    visited = set()
    visited.add(str(st[0])+","+str(st[1]))
    que.append([st[0],st[1],0])
    max_cos = 0
    while True:
        if len(que) == 0:
            return  max_cos
        top = que.popleft()
        nowi = top[0]
        nowj = top[1]
        cost = top[2]
        for a in around:
            ni = nowi+a[0]
            nj = nowj+a[1]
            if ni < 0 or ni > h-1 or nj < 0 or nj > w-1:
                continue
            if field[ni][nj] == 1:
                continue
            if ni == go[0] and nj == go[1]:
                return cost+1
            else:
                key = str(ni)+","+str(nj)
                if key not in visited:
                    que.append([ni,nj,cost+1])
                    visited.add(key)
                    if cost+1 > max_cos:
                        max_cos = cost+1



ans = 0
for i in range(h):
    for j in range(w):
        ct = dfs_field(f,[i,j],[-2,-2])
        if ans < ct:
            ans = ct

print(ans)

Submission status: Wrong Answer

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

f = []
for i in range(h):
    s = list(map(lambda x:0 if x== "." else 1,list(input())))
    f.append(s)

from collections import deque
def dfs_field(field,st,go):
    """
    :param field: #が1,.が0になったfield
    st: [i,j]
    go: [i,j]
    :return: 色々今は回数returnしている。
    """
    h = len(field)
    w = len(field[0])
    around = [[-1,0],[1,0],[0,1],[0,-1]]
    que = deque()
    visited = set()
    visited.add(str(st[0])+","+str(st[1]))
    que.append([st[0],st[1],0])
    while True:
        if len(que) == 0:
            return  -1
        top = que.popleft()
        nowi = top[0]
        nowj = top[1]
        cost = top[2]
        for a in around:
            ni = nowi+a[0]
            nj = nowj+a[1]
            if ni < 0 or ni > h-1 or nj < 0 or nj > w-1:
                continue
            if field[ni][nj] == 1:
                continue
            if ni == go[0] and nj == go[1]:
                return cost+1
            else:
                key = str(ni)+","+str(nj)
                if key not in visited:
                    que.append([ni,nj,cost+1])
                    visited.add(key)


ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                ct = dfs_field(f,[i,j],[k,l])
                if ct > ans:
                    ans = ct

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
S = [input()[:-1] for _ in [0]*H]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(h, w, H, W):
    visited = [False]*(W*H)
    q = deque()
    q.append((0, h, w))
    while q:
        d, h, w = q.popleft()
        if visited[h*W+w]:
            continue
        visited[h*W+w] = True

        for dh, dw in dirs:
            nh, nw = h+dh, w+dw
            if 0 <= nh < H and 0 <= nw < W and not visited[(nh)*W+nw] and S[nh][nw] == '.':
                q.append((d+1, nh, nw))

    return d, h, w


ans = 0
for h, _S in enumerate(S):
    for w, s in enumerate(_S):
        if s == '.':
            d, h, w = bfs(h, w, H, W)
            if d > ans:
                ans = d

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
S = [input()[:-1] for _ in [0]*H]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(h, w, H, W):
    visited = [False]*(W*H)
    q = deque()
    q.append((0, h, w))
    while q:
        d, h, w = q.popleft()
        if visited[h*W+w]:
            continue
        visited[h*W+w] = True

        for dh, dw in dirs:
            if 0 <= h+dh < H and 0 <= w+dw < W and not visited[(h+dh)*W+w+dw] and S[h][w] == '.':
                q.append((d+1, h+dh, w+dw))

    return d, h, w


ans = 0
for h, _S in enumerate(S):
    for w, s in enumerate(_S):
        if s == '.':
            d, h, w = bfs(h, w, H, W)
            if d > ans:
                ans = d

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
S = [input()[:-1] for _ in [0]*H]


def bfs(h, w, H, W):
    from collections import deque
    visited = [[False]*W for _ in range(H)]
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    q.append((0, h, w))
    while q:
        d, h, w = q.popleft()
        visited[h][w] = True

        for dh, dw in dirs:
            if 0 <= h+dh < H and 0 <= w+dw < W and not visited[h+dh][w+dw] and S[h][w] == '.':
                q.append((d+1, h+dh, w+dw))

    return d, h, w


ans = 0
for h, _S in enumerate(S):
    for w, s in enumerate(_S):
        if s == '.':
            d, h, w = bfs(h, w, H, W)
            if d > ans:
                ans = d

print(ans)