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 copy
H, W = map(int, input().split())
S = [input() for _ in range(H)]

graph = [deque([]) for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            if j+1 < W:
                if S[i][j+1] == ".":
                    graph[i*W+j].append(i*W+j+1)
                    graph[i*W+j+1].append(i*W+j)
            if i+1 < H:
                if S[i+1][j] == ".":
                    graph[i*W+j].append((i+1)*W+j)
                    graph[(i+1)*W+j].append(i*W+j)

def bfs(v, graph):
    d = [-1]*(H*W)
    stack = deque([v])
    d[v] = 0
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if d[w] == -1 or d[v]+1 < d[w]:
                d[w] = d[v]+1
                stack.appendleft(w)
        else:
            stack.pop()
    max_d = [0, 0]
    for i in range(H*W):
        if d[i] > max_d[0]:
            max_d = [d[i], i]
    return max_d

res = bfs(0, copy.deepcopy(graph))
res = bfs(res[1], graph)
print(res[0])

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]


def bfs(sy,sx):
    #頂点をINFで初期化
    d = [[INF]*w for i in range(h)]
    
    #移動４方向のベクトル
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    #スタート位置とゴール位置を探す
    """
    for i in range(h):
        for j in range(w):
            if li[i][j]  == "s":
                sx = i
                sy = j
            if li[i][j] == "g":
                gx = i
                gy = j
    """
    #スタート地点をキューにいれ、頂点を０にする
    que = deque([])
    que.append((sy,sx))
    d[sy][sx] = 0

    #キューが空になるまでループ（行ける要素がなくなるまで）
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        """
        if p[0] == gx and p[1] == gy:
            break
        """
        # 移動4方向をループ
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            #壁との判定とすでに訪れたかどうかをチェック
            if 0<=nx and nx < w and 0 <= ny and ny < h:
                if li[ny][nx] != "#" and d[ny][nx] == INF:
                    #移動できる点なのでキューについか
                    que.append((ny,nx))
                    #前の点+1で移動できる
                    d[ny][nx] = d[p[0]][p[1]] + 1
    return d
ans = 0
for i in range(h):
    for j in range(w):
        c = bfs(i,j)
        for k in range(h):
            for l in range(w):
                if c[k][l] == INF:
                    continue
                ans = max(ans,c[k][l])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]


def bfs(sy,sx):
    #頂点をINFで初期化
    d = [[INF]*w for i in range(h)]
    
    #移動４方向のベクトル
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    #スタート位置とゴール位置を探す
    """
    for i in range(h):
        for j in range(w):
            if li[i][j]  == "s":
                sx = i
                sy = j
            if li[i][j] == "g":
                gx = i
                gy = j
    """
    #スタート地点をキューにいれ、頂点を０にする
    que = deque([])
    que.append((sy,sx))
    d[sy][sx] = 0

    #キューが空になるまでループ（行ける要素がなくなるまで）
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        """
        if p[0] == gx and p[1] == gy:
            break
        """
        # 移動4方向をループ
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            #壁との判定とすでに訪れたかどうかをチェック
            if 0<=nx and nx < w and 0 <= ny and ny < h:
                if li[ny][nx] != "#" and d[ny][nx] == INF:
                    #移動できる点なのでキューについか
                    que.append((ny,nx))
                    #前の点+1で移動できる
                    d[ny][nx] = d[p[0]][p[1]] + 1
    return d
ans = 0
for i in range(h):
    for j in range(w):
        c = bfs(i,j)
        for k in range(h):
            for l in range(w):
                if li[k][l] == "#":
                    continue
                ans = max(ans,c[k][l])
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
Inf = 10**9

S = [input() for i in range(H)]
dis = [[Inf]*(H*W) for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        if i - 1 >= 0 and S[i-1][j] == ".":
            dis[i*W+j][(i-1)*W+j] = 1
        if i + 1 < H and S[i+1][j] == ".":
            dis[i*W+j][(i+1)*W+j] = 1
        if j - 1 >= 0 and S[i][j-1] == ".":
            dis[i*W+j][i*W+j-1] = 1
        if j + 1 < W and S[i][j+1] == ".":
            dis[i*W+j][i*W+j+1] = 1

for i in range(H*W):
    for j in range(H*W):
        for k in range(H*W):
            dis[j][k] = min(dis[j][i] + dis[i][k], dis[j][k])

max_ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dis[i][j] == Inf:
            continue        
        max_ans = max(dis[i][j], max_ans)

print(max_ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
Inf = 10**9

S = [input() for i in range(H)]
dis = [[Inf]*(H*W) for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        if i - 1 >= 0 and S[i-1][j] != "#":
            dis[i*W+j][(i-1)*W+j] = 1
        if i + 1 < H and S[i+1][j] != "#":
            dis[i*W+j][(i+1)*W+j] = 1
        if j - 1 >= 0 and S[i][j-1] != "#":
            dis[i*W+j][i*W+j-1] = 1
        if j + 1 < W and S[i][j+1] != "#":
            dis[i*W+j][i*W+j+1] = 1

for i in range(H*W):
    for j in range(H*W):
        for k in range(H*W):
            dis[j][k] = min(dis[j][i] + dis[i][k], dis[j][k])

max_ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dis[i][j] == Inf:
            continue        
        max_ans = max(dis[i][j], max_ans)

print(max_ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
Inf = 10**9

S = [input() for i in range(H)]
dis = [[Inf]*(H*W) for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        if i - 1 >= 0 and S[i-1][j] != "#":
            dis[i*W+j][(i-1)*W+j] = 1
        if i + 1 < H and S[i+1][j] != "#":
            dis[i*W+j][(i+1)*W+j] = 1
        if j - 1 >= 0 and S[i][j-1] != "#":
            dis[i*W+j][i*W+j-1] = 1
        if j + 1 < W and S[i][j+1] != "#":
            dis[i*W+j][i*W+j+1] = 1

for i in range(H*W):
    for j in range(H*W):
        for k in range(H*W):
            dis[j][k] = min(dis[j][i] + dis[i][k], dis[j][k])

max_ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dis[i][j] != Inf:
            continue        
        max_ans = max(dis[i][j], max_ans)

print(max_ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
Inf = 10**9

S = [input() for i in range(H)]
dis = [[Inf]*(H*W) for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        if i - 1 >= 0 and S[i-1][j] != "#":
            dis[i*W+j][(i-1)*W+j] = 1
        if i + 1 < H and S[i+1][j] != "#":
            dis[i*W+j][(i+1)*W+j] = 1
        if j - 1 >= 0 and S[i][j-1] != "#":
            dis[i*W+j][i*W+j-1] = 1
        if j + 1 < W and S[i][j+1] != "#":
            dis[i*W+j][i*W+j+1] = 1

for i in range(H*W):
    for j in range(H*W):
        for k in range(H*W):
            dis[j][k] = min(dis[j][i] + dis[i][k], dis[j][k])

max_ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dis[i][j] > max_ans and dis[i][j] != Inf:
            max_ans = dis[i][j]

print(max_ans)

Submission status: Wrong Answer

Solution code:
import queue

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

def nexts(h, w):
    l = []
    if h > 0   and S[h-1][w] == '.':
        l.append((h-1, w))
    if h < H-1 and S[h+1][w] == '.':
        l.append((h+1, w))
    if w > 0   and S[h][w-1] == '.':
        l.append((h, w-1))
    if w < W-1 and S[h][w+1] == '.':
        l.append((h, w+1))
    return l

def bfs(h, w):
    d = [[0]*W for _ in range(H)]
    q = queue.Queue()
    q.put((h,w))

    while not q.empty():
        v = q.get()
        vh, vw = v[0], v[1]

        for nxt in nexts(vh, vw):
            nh, nw = nxt[0], nxt[1]
            if d[nh][nw] > 0:
                continue
            d[nh][nw] = d[vh][vw] + 1
            q.put((nh, nw))
    return d

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        d = bfs(h,w)
        mx = 0
        for th in range(H):
            for tw in range(W):
                mx = max(mx, d[th][tw])
        ans = max(ans, mx)
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

def nexts(h, w):
    l = []
    if h > 0   and S[h-1][w] == '.':
        l.append((h-1, w))
    if h < H-1 and S[h+1][w] == '.':
        l.append((h+1, w))
    if w > 0   and S[h][w-1] == '.':
        l.append((h, w-1))
    if w < W-1 and S[h][w+1] == '.':
        l.append((h, w+1))
    return l

def bfs(h, w):
    d = [[0]*W for _ in range(H)]
    q = queue.Queue()
    q.put((h,w))

    while not q.empty():
        v = q.get()
        vh, vw = v[0], v[1]

        for nxt in nexts(vh, vw):
            nh, nw = nxt[0], nxt[1]
            if d[nh][nw] > 0:
                continue
            d[nh][nw] = d[vh][vw] + 1
            q.put((nh, nw))
    return d

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        d = bfs(h,w)
        mx = 10**5
        for th in range(H):
            mx = max(d[th])
        ans = max(ans, mx)
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    import numpy as np
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    def bfs(i,j):
        que = collections.deque([[i,j,0]])
        footprint = [[0 for _ in range(W)] for _ in range(H)]
        cnt = 0

        while len(que) >=1:
            a, b, c = que.popleft()
            footprint[a][b] = c

            if a != 0:
                if footprint[a-1][b] == 0 and grid[a-1][b] == '.':
                    que.append([a-1, b, c+1])
            if a != H-1:
                if footprint[a+1][b] == 0 and grid[a+1][b] == '.':
                    que.append([a+1, b, c+1])
            if b != 0:
                if footprint[a][b-1] == 0 and grid[a][b-1] == '.':
                    que.append([a, b-1, c+1])
            if b != W-1:
                if footprint[a][b+1] == 0 and grid[a][b+1] == '.':
                    que.append([a, b+1, c+1])

        # print(footprint)
        return np.array(footprint).max()

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


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    import numpy as np
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    def bfs(i,j):
        que = collections.deque([[i,j,0]])
        footprint = [[0 for _ in range(W)] for _ in range(H)]
        cnt = 0

        while len(que) >=1:
            a, b, c = que.popleft()
            footprint[a][b] = c

            if a != 0:
                if footprint[a-1][b] == 0 and grid[a-1][b] == '.':
                    que.append([a-1, b, c+1])
            if a != H-1:
                if footprint[a+1][b] == 0 and grid[a+1][b] == '.':
                    que.append([a+1, b, c+1])
            if b != 0:
                if footprint[a][b-1] == 0 and grid[a][b-1] == '.':
                    que.append([a, b-1, c+1])
            if b != W-1:
                if footprint[a][b+1] == 0 and grid[a][b+1] == '.':
                    que.append([a, b+1, c+1])

        # print(footprint)
        return np.array(footprint).max()

    res = 0
    for i in range(H):
        for j in range(W):
            res = max(res, bfs(i,j))
    
    print(res)
        


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

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

g = [[0] * (H * W) for _ in range(H * W)]
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if y - 1 >= 0 and S[y - 1][x] != '#':
            g[y * W + x][(y - 1) * W + x] = 1
        if y + 1 < H and S[y + 1][x] != '#':
            g[y * W + x][(y + 1) * W + x] = 1
        if x - 1 >= 0 and S[y][x - 1] != '#':
            g[y * W + x][y * W + x - 1] = 1
        if x + 1 < W and S[y][x + 1] != '#':
            g[y * W + x][y * W + x + 1] = 1
g = floyd_warshall(csgraph_from_dense(g))

result = 0
for i in range(H * W):
    for j in range(H * W):
        if g[i][j] == 0:
            continue
        result = min(result, g[i][j])
print(int(result))

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '#': continue
                visited[ny][nx] = True
                dist[ny][nx] = dist[y][x] + 1
                q.append((ny, nx))
                #dist[ny][nx] = dist[y][x] + 1
                #visited[ny][nx] = True

        
        for i in range(H):
            ans = max(ans, max(dist[i]))
        
        #ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '#': continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True

        
        for i in range(H):
            ans = max(ans, max(dist[i]))
        
        #ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '#': continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True


        for i in range(H):
            ans = max(ans, max(dist[i]))

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True


        for i in range(H):
            ans = max(ans, max(dist[i]))

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True


        mdist = 0
        for i in range(H):
            for j in range(W):
                mdist = max(mdist, dist[i][j])
        ans = max(ans, mdist)

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True


        mdist = 0
        for i in range(H):
            mdist = max(mdist, max(dist[i]))
        ans = max(ans, mdist)

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True



        for i in range(len(dist)):
            ans = max(ans, max(dist[i]))

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        dist[i][j] = 0
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        tmp = 0
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True



        for i in range(H):
            ans = max(ans, max(dist[i]))

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)


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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        dist[i][j] = 0
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        tmp = 0
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True



        for i in range(H):
            ans = max(ans, max(dist[i]))

            

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        dist[i][j] = 0
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        tmp = 0
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True



        for i in range(H):
            ans = max(ans, max(dist[i]))

            

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        dist = [[-1 for _ in range(W)] for _ in range(H)] 
        dist[i][j] = 0
        tmp = 0
        q = []
        heapq.heappush(q, (dist[i][j], i,j))
        while q:
            cost, y,x = heapq.heappop(q)
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or S[ny][nx] == "#":
                    continue
                if dist[ny][nx] == -1 or cost + 1 < dist[ny][nx]:
                    dist[ny][nx] = cost + 1
                    heapq.heappush(q, (dist[ny][nx], ny, nx))
                    



        for i in range(H):
            ans = max(ans, max(dist[i]))



print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        dist = [[-1 for _ in range(W)] for _ in range(H)] 
        dist[i][j] = 0
        tmp = 0
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or S[ny][nx] == "#":
                    continue
                if dist[ny][nx] == -1 or dist[y][x] + 1 < dist[ny][nx]:
                    q.append((ny, nx))
                    dist[ny][nx] = dist[y][x] + 1
                    tmp = max(tmp, dist[ny][nx])


        for i in range(H):
            ans = max(ans, max(dist[i]))



print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        dist = [[5000 for _ in range(W)] for _ in range(H)] 
        dist[i][j] = 0
        tmp = 0
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or S[ny][nx] == "#":
                    continue
                if dist[y][x] + 1 < dist[ny][nx]:
                    q.append((ny, nx))
                    dist[ny][nx] = dist[y][x] + 1
                    tmp = max(tmp, dist[ny][nx])


        ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def bfs(h, w, m, start):

    import queue
    d = [[0 for i in range(w)]for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    flg = False

    a = queue.Queue()
    a.put(start)
    #print(start)
    while not a.empty():
        hh, ww = map(int, a.get())
        for i in range(4):
            nx, ny = ww+dx[i], hh+dy[i]
            if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "#" and d[ny][nx] == 0:
                a.put([ny, nx])
                d[ny][nx] = d[hh][ww]+1

    return d[hh][ww]



h, w = map(int, input().split())
m = [[]for i in range(h)]
for i in range(h):
    m[i] = list(input().rstrip())

ans=[]
for i in range(h):
    for j in range(w):
        if m[i][j]!="#":
            start=[i,j]
            ans.append(bfs(h,w,m,start))
            #print(ans)

print(max(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
h , w = map(int,input().split())
ma = [["#" for i in range(w+2)]]
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    kar.append("#")
    ma.append(kar)
ma.append(["#" for i in range(w+2)])
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if ma[i][j] == "#":
            break
        elif ma[i][j] ==".":
            p = [[-1 for g in range(w+2)] for f in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i,j])
            while q:
                y,x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1,x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1,x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y,x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y,x-1])
            for l in range(1,h+1):
                ans = max(ans,max(p[l]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

H,W=nm()

INF=10**18
def dijkstra(start,edge):
    d=[[INF]*W for i in range(H)]
    d[start[0]][start[1]]=0
    q=[(0,start[0],start[1])]
    while(len(q)!=0):
        ci,i,j=heappop(q)
        #if(d[start[0]][start[1]]<ci):
        #    continue 
        for p in edge[i][j]:
            if(d[p[0]][p[1]]>d[i][j]+1):
                d[p[0]][p[1]]=d[i][j]+1
                heappush(q,(d[p[0]][p[1]],p[0],p[1]))
    return d

E=[[[] for _ in range(W)] for _ in range(H)] 
S=[] 

for i in range(H):
    tmp=ns()
    S.append(tmp)
    

for i in range(H):
    for j in range(W):
        if( j+1<=W-1 and S[i][j+1]=='.'):
            E[i][j].append((i,j+1))
        if( i+1<=H-1 and S[i+1][j]=='.'):
            E[i][j].append((i+1,j))
        if(S[i][j-1]=='.' and 0<=j-1):
            E[i][j].append((i,j-1))
        if(S[i-1][j]=='.' and 0<=i-1):
            E[i][j].append((i-1,j))



ans=0

d=[[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        d=dijkstra((i,j),E)
        for k in range(H):
            for l in  range(W):
                if(ans<d[k][l] and d[k][l]<10**18):
                    ans=d[k][l]
                    
print(ans)

Submission status: Wrong Answer

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

res = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
	for j in range(w):
		if s[i][j] == "#":
			continue
		cnt = 0
		queue = deque([[i,j]])
		visited = [[0 for ii in range(w)] for jj in range(h)]
		while queue:
			l,m = queue.popleft()
			for k in range(4):
				x = l + dx[k]
				y = m + dy[k]
				if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] != 0 or s[x][y] == "#":
					continue
				visited[x][y] = visited[l][m] + 1
				queue.append([x,y])
		for ii in range(h):
			for jj in range(w):
				res = max(res,visited[ii][jj])
print (res)