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:
from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]#迷路の入力

ans = 0
for x in range(H):#すべてのマスからスタート
    for y in range(W):
        #壁からはスタートできない：スルー
        if maze[x][y] == "#":
            continue

        #初期化：0埋め、HとWの順番に注意
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])#デキューに入れる

        while stack:#スタックが有るあいだ
            h,w = stack.popleft()#スタックの先頭を取ってくる
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:#マスの四方
                new_h, new_w = h+i, w+j#新しいマス
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue#範囲外ならスルー
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1#BFS、+1
                    stack.append([new_h, new_w])
                    #新しいマスをスタックへ

        #start位置は0で初期化
        #distance[x][y] = 0
        ans = max(ans, np.max(distance))#npは二次元のmax取れる

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def BFS(x,y):
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    color[x][y]="gray"
    D[x][y]=0
    queue=deque([[x,y]])

    num=0
    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=a+c,b+d
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white" and S[X][Y]==".":
                    D[X][Y]=D[a][b]+1
                    num=max(num,D[X][Y])
                    color[X][Y]="gray"
                    queue.append([X,Y])
        color[X][Y]="black"

    return num


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

ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]==".":ans=max(ans,BFS(i,j))
        
print(ans)

Submission status: Wrong Answer

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

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

def longest_BFS(h, w):
    ret = -1
    if S[h][w] == '#':
        return -1
    table = [[-1 for i in range(W)] for j in range(H)]
    table[h][w]
    next_step = [[h, w]]
    while next_step:
        ret += 1
        step = next_step[:]
        next_step = []
        while step:
            u = step.pop()
            for i in range(4):
                if u[0]+dx[i] >= 0 and u[0]+dx[i] < H \
                    and u[1]+dy[i] >= 0 and u[1]+dy[i] < W \
                    and S[u[0]+dx[i]][u[1]+dy[i]] == '.' \
                    and table[u[0]+dx[i]][u[1]+dy[i]] == -1:
                    next_step += [[u[0]+dx[i], u[1]+dy[i]]]
                    table[u[0]+dx[i]][u[1]+dy[i]] = ret

    return ret

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, longest_BFS(h, w))
print(ans)

Submission status: Wrong Answer

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

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

def longest_BFS(h, w):
    ret = -1
    if S[h][w] == '#':
        return -1
    table = [[-1 for i in range(W)] for j in range(H)]
    table[h][w]
    next_step = [[h, w]]
    while next_step:
        ret += 1
        step = next_step[:]
        next_step = []
        while step:
            u = step.pop()
            for i in range(4):
                if u[0]+dx[i] >= 0 and u[0]+dx[i] < H \
                    and u[1]+dy[i] >= 0 and u[1]+dy[i] < W \
                    and S[u[0]+dx[i]][u[1]+dy[i]] == '.' \
                    and table[u[0]+dx[i]][u[1]+dy[i]] == -1:
                    next_step += [[u[0]+dx[i], u[1]+dy[i]]]
                    table[u[0]+dx[i]][u[1]+dy[i]] = ret

    return ret

ans = -1
for h in range(H):
    for w in range(W):
        ans = max(ans, longest_BFS(h, w))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
D = [list(input()) for _ in range(h)]
# 　D[高さ][横]
flag = 0
for i in range(h):
    for j in range(w):
        if D[i][j] == ".":
            start = (i, j)
            flag = 1
            break
    if flag:
        break

di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]


def check(i, j):
    if i >= 0 and i < h and j >= 0 and j < w:
        cond = True
    else:
        cond = False
    return cond


def dfs(start, D):
    res = 0
    basho = (0, 0)
    dist = [[-1] * w for _ in range(h)]
    sy, sx = start
    dist[sy][sx] = 0
    stack = []
    stack.append(start)
    while stack:
        nowi, nowj = stack.pop()
        kyori = dist[nowi][nowj]
        for i in range(4):
            newi = nowi + di[i]
            newj = nowj + dj[i]
            if check(newi, newj):
                if dist[newi][newj] >= 0:
                    continue
                if D[newi][newj] == "#":
                    continue
                dist[newi][newj] = kyori + 1
                if res < kyori + 1:
                    res = kyori + 1
                    basho = (newi, newj)
                stack.append((newi, newj))
    return res, basho


_, temp = dfs(start, D)
ans, _ = dfs(temp, D)
print(ans)

Submission status: Wrong Answer

Solution code:
# via https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95

h, w = map(int, input().split())
ss = []
for hh in range(h):
    ss += list(input())
n = h * w

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[0] * n for _ in range(n)]

#print(d)
for i in range(n):
    for j in range(n):
        if i != j:
            d[i][j] = float('inf')
        elif i == j and ss[i] == '#':
            d[i][j] = float('inf')
#print(d)

for hh in range(h):
    for ww in range(w):
        i = hh * w + ww
        upper = i - w
        lower = i + w
        left = i - 1 if ww > 0 else -1
        right = i + 1 if ww < w-1 else -1
        neighbors = [m for m in [upper, lower, left, right] if m in range(0, n)]
        for neighbor in neighbors:
            if ss[i] != ss[neighbor]:
                d[i][neighbor] = float('inf')
                d[neighbor][i] = float('inf')                
            else:
                d[i][neighbor] = 1
                d[neighbor][i] = 1
#print(d)
wf = warshall_floyd(d)
#print(wf)
ans = max([max([c for c in row if c < n]) for row in wf])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def maze(h, w, sh, sw, list1):
    if list1[sh][sw]=="#":
        return 0
    flag = True
    for i in range(h):
        for j in range(w):
            if list1[i][j]=="#":
                flag=False
    if flag:
        return 10000000000
    
    que = deque()
    que.append([sh, sw, 0])
    list2 = list1.copy()
    direct = [(0,1), (0,-1), (1,0), (-1, 0)]
    count = 0
    while que:
        nh, nw, co = que.pop()
        count = co
        co +=1
        li=list(list2[nh])
        li[nw]="#"
        list2[nh]="".join(li)
        for i, j in direct:
            if nh+i<0 or nh+i>=h or nw+j<0 or nw+j>=w:
                pass
            elif list2[nh+i][nw+j]==".":
                que.appendleft([nh+i, nw+j, co])
    return count
        
h, w = (int(x) for x in input().split())
list1 = []
ans = 0
for i in range(h):
    list1.append(input())
for i in range(h):
    for j in range(w):
        ans_ij = maze(h, w, i, j , list1)
        if ans_ij>ans:
            ans=ans_ij
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def check(ny, nx, sS):
    if 0<=ny<H and 0<=nx<W:
        if sS[ny][nx]=='.':
            return True
    else:
        return False

def bfs(sy, sx, sS):
    deq = deque()
    deq.append([(sy-1, sx-1)]) # insert indices
    sS[sy-1][sx-1] = '#'
    ddy = [-1, 0, 1, 0]
    ddx = [0, -1, 0, 1]
    step = 0
    while deq[0]:
        nqueue = []
        cqueue = deq.popleft()
        for val in cqueue:
            y, x = val
            for dy, dx in zip(ddy, ddx):
                ny, nx = y+dy, x+dx
                if check(ny, nx, sS):
                    sS[ny][nx] = '#'
                    nqueue.append((ny, nx))
        deq.append(nqueue)
        if not(deq[0]):
            break
        step += 1
    return step

res = 0
for i in range(H):
    for j in range(W):
        sS = deepcopy(S)
        val = bfs(i+1, j+1, sS)
        #print('i, j, val:', i, j, val)
        res = max(res, val)

print(res)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def check(ny, nx, sS):
    if 0<=ny<H and 0<=nx<W:
        if sS[ny][nx]=='.':
            return True
    else:
        return False

def bfs(sy, sx, sS):
    deq = deque()
    deq.append([(sy-1, sx-1)]) # insert indices
    ddy = [-1, 0, 1, 0]
    ddx = [0, -1, 0, 1]
    step = 0
    while deq[0]:
        nqueue = []
        cqueue = deq.popleft()
        for val in cqueue:
            y, x = val
            for dy, dx in zip(ddy, ddx):
                ny, nx = y+dy, x+dx
                if check(ny, nx, sS):
                    sS[ny][nx] = '#'
                    nqueue.append((ny, nx))
        deq.append(nqueue)
        step += 1
    return step

res = 0
for i in range(H):
    for j in range(W):
        sS = deepcopy(S)
        val = bfs(i+1, j+1, sS)
        #print('i, j, val:', i, j, val)
        res = max(res, val)

print(res-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

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


def bfs(start):
    i, j = start
    INF = 10**18
    dist = [[-INF] * w for _ in range(h)]
    dist[i][j] = 0
    next_v = deque([start])
    visited = set()
    while next_v:
        i, j = next_v.popleft()
        direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in direction:
            x, y = i+di, j+dj
            if MAZE[x][y] == "#":
                continue
            if (x, y) in visited:
                continue
            dist[x][y] = dist[i][j] + 1
            visited.add((i, j))
            next_v.append((x, y))
    return dist


ans = 0
for s1 in start:
    r = bfs(s1)
    _max = max(max(r))
    ans = max(ans, _max)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal


for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            start = [i,j]
MAX, goal = bfs(tuple(start))
# print(goal,start)
MAX, _ = bfs(tuple(goal))
print(MAX)
exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal


for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            MAX, goal = bfs(tuple([i,j]))

            MAX, _ = bfs(tuple(goal))
            print(MAX)
            exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]
MAX = 0 

def bfs(s):
    global MAX
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for d in depth.values():
        MAX = max(MAX,d)


for i in range(0,H):
    for j in (0,W-1):
        if MAP[i][j] == '.':
            bfs(tuple([i,j]))

for i in range(0,W):
    for j in (0,H-1):
        if MAP[j][i] == '.':
            bfs(tuple([j,i]))

print(MAX)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))
print(MAP)
move = [[0,1],[0,-1],[1,0],[-1,0]]
MAX = 0 

def bfs(s):
    global MAX
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for d in depth.values():
        MAX = max(MAX,d)


for i in range(0,H):
    for j in (0,W-1):
        if MAP[i][j] == '.':
            bfs(tuple([i,j]))

for i in range(0,W):
    for j in (0,H-1):
        if MAP[j][i] == '.':
            bfs(tuple([j,i]))

print(MAX)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
# Maze by warshall_floyd
# ワーシャルフロイド法


def solve(H, W, a):
    # print(a)
    inf = 200
    d = [[inf]*(H*W) for _ in range(H*W)]
    for h in range(H):
        for w in range(W):
            if (a[h][w] == "0"):
                d[h*W+w][h*W+w] = 0
                if (w+1<W)and(a[h][w+1] == "0"):
                    d[h*W+w][h*W+w+1] = 1
                if (h+1<H)and(a[h+1][w] == "0"):
                    d[h*W+w][(h+1)*W+w] = 1
                if (w-1>=0)and(a[h][w-1] == "0"):
                    d[h*W+w][h*W+w-1] = 1
                if (h-1>=0)and(a[h-1][w] == "0"):
                    d[h*W+w][(h-1)*W+w] = 1
                
    # print(*d, sep='\n')

    for k in range(H*W):  # via k [k//W][k% W]
        for st in range(H*W):  # start from st
            for ed in range(H*W):  # go to ed
                d[st][ed] = min(d[st][ed], d[st][k]+d[k][ed])

    # print(*d, sep="\n")

    print(max(*map(lambda x: max(x), d)))
    return

if __name__ == '__main__':
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int

    a = [[_ for _ in next(tokens).replace(".","0").replace("#","1")] for _ in range(H)]  # type: "List[int]"
    solve(H, W, a)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(sy,sx):
    m_dis=0
    
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if 0<=my<tate and 0<=mx<yoko:
                if maze[my][mx]=="." and visited[my][mx]==-1:
                    queue.append([my,mx])
                    visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
                    m_dis=visited[my][mx]
        
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=-1
for y in range(tate):
    for x in range(yoko):
        ans=max(ans,bfs(y,x))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(sy,sx):
    m_dis=0
    
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if 0>my or my>=tate or 0>mx or mx>=yoko:
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
                m_dis=visited[my][mx]
        
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=0
for y in range(tate):
    for x in range(yoko):
        ans=max(ans,bfs(y,x))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(sy,sx):
    m_dis=0
    
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
                m_dis=visited[my][mx]
        
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=0
for y in range(tate):
    for x in range(yoko):
        ans=max(ans,bfs(y,x))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(sy,sx):
    m_dis=0
    mv_ok=False
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        mv_ok=False
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
                mv_ok=True
        if mv_ok:
            m_dis+=1
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=0
for y in range(tate):
    for x in range(yoko):
        ans=max(ans,bfs(y,x))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(sy,sx):
    m_dis=0
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
                m_dis+=1
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=0
for y in range(tate):
    for x in range(yoko):
        ans=max(ans,bfs(y,x))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(sy,sx):
    m_dis=0
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
                m_dis=max(m_dis,visited[my][mx])
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=0
for y in range(tate):
    for x in range(yoko):
        ans=max(ans,bfs(y,x))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

inf = float('inf')
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

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

# bfs
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#':
            continue
        dist = [[inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0][0]
            j = q[0][1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '#':
                    continue
                update(ni, nj, dist[i][j] + 1)

ans = 0        
for i in range(h):
    for j in range(w):
        if dist[i][j] == inf:
            continue
        ans = max(ans, dist[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

inf = float('inf')

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

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

def bfs():
    que = deque()
    d = [[inf for j in range(w)] for i in range(h)]
    que.append([sx, sy])
    d[sx][sy] = 0

    while len(que):
        p = que[0]
        que.popleft()
        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx and nx < h and 0 <= ny and ny < w and s[nx][ny] != '#' and d[nx][ny] == inf:
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[gx][gy]


ans = 0
for sx in range(h):
    for sy in range(w):
        for gx in range(h):
            for gy in range(w):
                if bfs() > ans:
                    ans = bfs()

print(ans)

Submission status: Wrong Answer

Solution code:
import queue
H,W = map(int,input().split())
maze = list()
q = queue.Queue()
for i in range(H):
   maze.append( [x for x in input()])
print(maze)
maxim = 1
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." :
            maze_score = [[0]*W for k in range(H)]
            maze_score[i][j] = 1
            q.put([i,j])
            
        else :
            continue
        
        while(True):
            if q.empty() :
                if maze_score[x][y] > maxim:
                    maxim = maze_score[x][y]
                break
            [x,y] = q.get()
            
            
            
            
            ##top
            if x != 0:
                if maze_score[x-1][y] ==0 and maze[x-1][y] == ".":
                    maze_score[x-1][y] = maze_score[x][y] +1
                    q.put([x-1,y])
            ##right
            if y+1 != W:
                if maze_score[x][y+1] ==0 and maze[x][y+1] == ".":
                    maze_score[x][y+1] = maze_score[x][y] +1
                    q.put([x,y+1])
            ##bottom
            if x != H-1:
                if maze_score[x+1][y] ==0 and maze[x+1][y] == ".":
                    maze_score[x+1][y] = maze_score[x][y] +1
                    q.put([x+1,y])
            ##left
            if y != 0:
                if maze_score[x][y-1] ==0 and maze[x][y-1] == ".":
                    maze_score[x][y-1] = maze_score[x][y] +1
                    q.put([x,y-1])
        
print(maxim-1)

Submission status: Wrong Answer

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
inf = -9999999999
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    h, w = nm()
    s = s = [['#'] * (w+1)]
    for _ in range(h):
        temp = ['#']
        temp.extend(list(ns()))
        temp.extend(['#'])
        s.append(temp)
    s.append(['#'] * (w+1))
        
    def bfs(arr, x, y):
        que = deque([[x, y]])
        dist = [[0]*(w+2) for _ in range(h+2)]
        for i in range(h+2):
            for j in range(w+2):
                if i == 0 or i == h + 1 or j == 0 or j == w + 1:
                    dist[i][j] = inf
        visited = set((x, y))
        while True:
            #print(x, y, que)
            #print(dist)
            now = que.popleft()
            if arr[now[0]][now[1]] == '.':
                if (now[0]+1, now[1]) not in visited:
                    que.append([now[0]+1, now[1]])
                    visited.add((now[0]+1, now[1]))
                    dist[now[0]+1][now[1]] = dist[now[0]][now[1]] + 1
                if (now[0], now[1]+1) not in visited:
                    que.append([now[0], now[1]+1])
                    visited.add((now[0], now[1]+1))
                    dist[now[0]][now[1]+1] = dist[now[0]][now[1]] + 1
                if (now[0]-1, now[1]) not in visited:
                    que.append([now[0]-1, now[1]])
                    visited.add((now[0]-1, now[1]))
                    dist[now[0]-1][now[1]] = dist[now[0]][now[1]] + 1
                if (now[0], now[1]-1) not in visited:
                    que.append([now[0], now[1]-1])
                    visited.add((now[0], now[1]-1))
                    dist[now[0]][now[1]-1] = dist[now[0]][now[1]] + 1
            elif arr[now[0]][now[1]] == '#':
                dist[now[0]][now[1]] = inf
            if que == deque():
                break 
        mx = []
        for i in range(h+2):
            mx.append(max(dist[i]))       
        return max(mx)

    ans = []
    #print(bfs(s, 1, 1))
    for i in range(1, h+1):
        for j in range(1, w+1):
            ans.append(bfs(s, i, j))

    print(max(ans))


if __name__ == '__main__':
    main()