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:
# coding: utf-8
import queue

row, col = map(int, input().split(' '))
maze = [list(input()) for _ in range(row)]

                
def BPS(si, sj):
    done = [[0 for _ in range(col)] for _ in range(row)]
    q = queue.Queue()
    q.put((si, sj, 0))
    around = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    maxv = 0
    while not q.empty():
        i, j, cnt = q.get()
        done[i][j] = 1
        for ar in around:
            di, dj = ar[0], ar[1]
            i_n, j_n = i + di, j + dj
            if (i_n >= 0 and i_n < row and j_n >= 0 and j_n < col) == False:
                continue
            if maze[i_n][j_n] == '#':
                continue
            if done[i_n][j_n] == 1:
                continue
            if done[i_n][j_n] == 2:
                continue
            maxv = max(maxv, cnt + 1)
            q.put((i_n, j_n, cnt + 1))
            done[i_n][j_n] = 2
        
    return maxv
            
            
def main():        
    maxv = 0
    for i in range(row):
        for j in range(col):
            maxv = max(maxv, BPS(i,j))
    print(maxv)
                    
                
                    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    H,W = [int(n) for n in input().split()]
    grid = [[0 if n=="." else 1 for n in input()] for _ in range(H)]
    INF = 10**10
    graph = [[INF]*H*W for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            graph[i*W+j][i*W+j]=0
            if grid[i][j] == 0:
                if i<H-1 and grid[i+1][j]==0:
                    graph[i*W+j][(i+1)*W+(j)] = 1
                    graph[(i+1)*W+(j)][i*W+j] = 1
                if j>0 and grid[i][j-1] == 0:
                    graph[i*W+j][(i)*W+j-1] = 1
                    graph[(i)*W+j-1][i*W+j] = 1
                if j<W-1 and grid[i][j+1] == 0:
                    graph[i*W+j][(i)*W+(j+1)] = 1
                    graph[(i)*W+(j+1)][i*W+j] = 1
                if i>0 and grid[i-1][j] == 0:
                    graph[i*W+j][(i-1)*W+(j)] = 1
                    graph[(i-1)*W+(j)][i*W+j] = 1
    
    
    for k in range(H*W):
        for i in range(H*W):
            for k in range(H*W):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    # for i in range(H*W):
    #     for j in range(W*H):
    #         print(graph[i][j], end="\t")
    #     print()
    m = 0
    for i in range(H*W):
        for j in range(H*W):
            if graph[i][j] == INF:
                continue
            m = max(m,graph[i][j])
    print(m)
main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
ans=-1
s=[]
for i in range(h):
	ss=input()
	s.append(ss)
from collections import deque as dq
for i in range(h):
	for j in range(w):
		if s[i][j]=="#":
			continue
		dis=[[10**3 for _ in range(w)]for _ in range(h)]
		dis[i][j]=0
		queue=dq([[i,j]])
		while queue:
			r=queue.popleft()
			if r[0]+1<h:
				if s[r[0]+1][r[1]]=="." and dis[r[0]+1][r[1]]==10**3:
					queue.append([r[0]+1,r[1]])
					dis[r[0]+1][r[1]]=dis[r[0]][r[1]]+1
			if r[0]-1>=0:
				if s[r[0]-1][r[1]]=="." and dis[r[0]-1][r[1]]==10**3:
					queue.append([r[0]-1,r[1]])
					dis[r[0]-1][r[1]]=dis[r[0]][r[1]]+1
			if r[1]+1<w:
				if s[r[0]][r[1]+1]=="." and dis[r[0]][r[1]+1]==10**3:
					queue.append([r[0],r[1]+1])
					dis[r[0]][r[1]+1]=dis[r[0]][r[1]]+1
			if r[1]+1>=0:
				if s[r[0]][r[1]-1]=="." and dis[r[0]][r[1]-1]==10**3:
					queue.append([r[0],r[1]-1])
					dis[r[0]][r[1]-1]=dis[r[0]][r[1]]+1
		for k in range(h):
			for l in range(w):
				if dis[k][l]!=10**3:
					ans=max(ans,dis[k][l])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


# このグラフ構造の中で一番遠い連結成分では？
H, W = read_ints()

from collections import deque, defaultdict
from itertools import product
Tree = defaultdict(lambda: [])

# input data
S = read_map(H)
node = -1
for i, j in product(range(H), range(W)):
    node += 1
    if S[i][j] == '#':
        continue
    for ni, nj in zip([0, 1, 0, -1], [1, 0, -1, 0]):
        if -1 < i + ni < H and -1 < j + nj < W and S[i + ni][j + nj] == '.':
            Tree[node].append((node + (W * ni + nj), 1))
            Tree[node + (W * ni + nj)].append((node, 1))


def bfs(Tree, n_V, s):
    '''
    指定した点sからの単一始点で各点までの距離を返す。
    n_Vは頂点の数
    Treeはdefault dictで、valueには(隣接ノード,そこまでのコスト)がリスト形式で格納されているとする。
    '''
    INF = -10**9
    Dists = [INF] * n_V  # 距離の初期化 #こいつを更新して返すことにする
    is_visited = [False] * n_V
    is_visited[s] = True
    que = deque([(s, 0)])  # (ノード番号,そこまでたどり着くためのコスト)
    while que:
        cur, cost = que.popleft()
        Dists[cur] = cost
        for nx_node, nx_cost in Tree[cur]:
            if is_visited[nx_node]:
                continue
            que.append((nx_node, nx_cost + cost))
            is_visited[nx_node] = True

    return Dists


# 任意の点から一番遠い点を求めて、そこからさらに一番遠い点がほしい
for i, j in product(range(H), range(W)):
    if S[i][j] == '.':
        Dists = bfs(Tree, W * H, i * W + j)
        break

next_node = Dists.index(max(Dists))  # numpyでいうargmaxしてる
Dists = bfs(Tree, W * H, next_node)

print(max(Dists))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import deque

def main():
    h,w=map(int,input().split())
    MAP=[['#']*(w+2)]
    for _ in range(h):
        S=list(input().strip())
        S=['#']+S+['#']
        MAP.append(S)
    MAP.append(['#']*(w+2))
    #print(MAP)
    ans=0
    
    def Dist(k,l):
        delta=[[1,0],[0,1],[-1,0],[0,-1]]
        Dist=[[float('inf')]*(w+2) for _ in range(h+2)]
        Dist[k][l]=0
        #Visited=[[False]*(w+2) for _ in range(h+2)]
        #Visited[k][l]=True
        q=deque()
        q.append((k,l))
        while q:
            y,x=q.popleft()
            for dx,dy in delta:
                #print(y+dy,x+dx)
                if Dist[y+dy][x+dx]==float('inf') and MAP[y+dy][x+dx]=='.':
                    q.append((y+dy,x+dx))
                    Dist[y+dy][x+dx]=Dist[y][x]+1
        ret=0
        for i in range(h+2):
            for j in range(w+2):
                if Dist[i][j]==float('inf'):
                    continue
                ret=max(ret,Dist[i][j])
        return ret
        
    for i in range(1,h+1):
        for j in range(1,w+1):
            dist=Dist(i,j)
            ans=max(ans,dist)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
MEIJI = [[0] * W for i in range(H)]

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            MEIJI[i][j] = 1


def findStart():
    for x in range(H-1, -1, -1):
        for y in range(W-1, -1, -1):
            if MEIJI[x][y] == 0:
                return x, y

    return False


def bfs(H, W, sx, sy):
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

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

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

if l < 0:
    l = 0

print(l)

Submission status: Wrong Answer

Solution code:
def main():
    H,W = [int(n) for n in input().split()]
    grid = [[0 if n=="." else 1 for n in input()] for _ in range(H)]
    INF = 10**2
    graph = [[INF]*H*W for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            graph[i*W+j][i*W+j]=0
            if grid[i][j] == 0:
                if i<H-1 and grid[i+1][j]==0:
                    graph[i*W+j][(i+1)*W+(j)] = 1
                    graph[(i+1)*W+(j)][i*W+j] = 1
                if j>0 and grid[i][j-1] == 0:
                    graph[i*W+j][(i)*W+j-1] = 1
                    graph[(i)*W+j-1][i*W+j] = 1
                if j<W-1 and grid[i][j+1] == 0:
                    graph[i*W+j][(i)*W+(j+1)] = 1
                    graph[(i)*W+(j+1)][i*W+j] = 1
                if i>0 and grid[i-1][j] == 0:
                    graph[i*W+j][(i-1)*W+(j)] = 1
                    graph[(i-1)*W+(j)][i*W+j] = 1
    
    
    for k in range(H*W):
        for i in range(H*W):
            for k in range(H*W):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    # for i in range(H*W):
    #     for j in range(W*H):
    #         print(graph[i][j], end="\t")
    #     print()
    m = 0
    for i in range(H*W):
        for j in range(H*W):
            if graph[i][j] == INF:
                continue
            m = max(m,graph[i][j])
    print(m)
main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
from itertools import groupby, permutations, combinations
from fractions import gcd
import numpy as np
from sys import stdin, stderr


def lcm(x, y):
    return (x * y) // gcd(x, y)

def movement_max(start_h, start_w, maze):
    H, W = len(maze), len(maze[0])
    score = []
    unvisited = set()
    unvisited.add(start_h + start_w*100)
    for h in range(H):
        score.append([-1] * len(maze[0]))
    score[start_h][start_w] = 0
    ret = 0
    while len(unvisited) > 0:
        hw = unvisited.pop()
        h = hw % 100
        w = hw // 100
        if maze[h][w] == "#":
            continue
        s = score[h][w] + 1
        ret = max(ret, score[h][w])
        if h > 0 and score[h-1][w] == -1:
            score[h-1][w] = s
            unvisited.add(h-1 + w*100)
        if h < H - 1 and score[h+1][w] == -1:
            score[h+1][w] = s
            unvisited.add(h+1 + w*100)
        if w > 0 and score[h][w-1] == -1:
            score[h][w-1] = s
            unvisited.add(h + (w-1)*100)
        if w < W - 1 and score[h][w+1] == -1:
            score[h][w+1] = s
            unvisited.add(h + (w+1)*100)
    return ret


def main():
    H, W = [int(x) for x in input().split()]
    maze = [""] * H
    for i in range(H):
        maze[i] = input()
    result = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            result = max(result, movement_max(h, w, maze))
            # print(result)
    return result


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

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

from collections import deque
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            continue
        ll = [[0] * W for _ in range(H)]
        q = deque([(i, j)])
        while q:
            y, x = q.popleft()
            for dy, dx in d:
                if 0 <= y+dy < H and 0 <= x+dx < W and l[y+dy][x+dx] == '.' and ll[y+dy][x+dx] == 0:
                    n = ll[y][x] + 1
                    ll[y+dy][x+dx] = n
                    if ans < n:
                        ans = n
                    q.append((y+dy, x+dx))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")

XX = [1, -1, 0, 0]
YY = [0, 0, 1, -1]


def main():

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

    dist = [[-1]*W for _ in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            # スタート位置 (h, w)
            if S[h][w] == "#":
                continue
            # 距離
            dist = [[INF]*W for _ in range(H)]

            q = deque([(h, w, 0)])
            while len(q) > 0:
                y, x, p = q.popleft()
                # 上下左右に移動可能ならば、移動して更新する
                for dx, dy in zip(XX, YY):
                    if y + dy < 0 or y + dy >= H:
                        continue
                    if x + dx < 0 or x + dx >= W:
                        continue
                    if S[y+dy][x+dx] == "#":
                        continue
                    if p + 1 < dist[y+dy][x+dx]:
                        dist[y+dy][x+dx] = p+1
                        q.append((y+dy, x+dx, p+1))

            # 一番遠く
            toku = -1
            for i in range(H):
                for j in range(W):
                    if dist[i][j] != INF:
                        toku = max(dist[i][j], toku)
            ans = max(toku, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
inf=float("inf")
data=[[inf]*W for i in range(H)]
start=[0,0]
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            start=[i,j]
d=[[1,0],[0,1],[-1,0],[0,-1]]
que=[[start[0],start[1]]]
data[start[0]][start[1]]=0
count=1
while que:
    h=[]
    for x,y in que:
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                h.append([nx,ny])
                data[nx][ny]=count
    que=h
    count+=1
z=[0,0]
num=0
for i in range(H):
    for j in range(W):
        if data[i][j]!=inf and data[i][j]>num:
            num=data[i][j]
            z=[i,j]
data=[[inf]*W for i in range(H)]
que=[z]
data[z[0]][z[1]]=0
count=1
while que:
    h=[]
    for x,y in que:
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                h.append([nx,ny])
                data[nx][ny]=count
    que=h
    count+=1
ans=0
for i in range(H):
    for j in range(W):
        if data[i][j]==inf:
            continue
        ans=max(ans,data[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque

    h, w = map(int, input().split())

    s = [input() for _ in range(h)]

    drdc = (1, 0), (-1, 0), (0, 1), (0, -1)

    dist = [[-1] * w for _ in range(h)]

    vs = []
    for r in range(h):
        for c in range(w):
            if dist[r][c] == -1 and s[r][c] == '.':
                dist[r][c] = 0

                q = deque()
                q.append((r, c, 0))

                md = -1
                tr, tc = -1, -1
                while q:
                    qr, qc, d = q.popleft()
                    for dr, dc in drdc:
                        nr = qr + dr
                        if nr < 0 or h <= nr:
                            continue
                        nc = qc + dc
                        if nc < 0 or w <= nc:
                            continue
                        if s[nr][nc] == '#':
                            continue
                        if dist[nr][nc] != -1:
                            continue
                        nd = d + 1
                        dist[nr][nc] = nd
                        if md < nd:
                            md = nd
                            tr = nr
                            tc = nc

                        q.append((nr, nc, nd))

                if tr != -1:
                    vs.append((tr, tc))

    dist = [[-1] * w for _ in range(h)]

    max_d = -1
    for sr, sc in vs:
        q = deque()
        q.append((sr, sc, 0))
        dist[sr][sc] = 0

        while q:
            r, c, d = q.popleft()
            for dr, dc in drdc:
                nr = r + dr
                if nr < 0 or h <= nr:
                    continue
                nc = c + dc
                if nc < 0 or w <= nc:
                    continue
                if s[nr][nc] == '#':
                    continue
                if dist[nr][nc] != -1:
                    continue
                nd = d + 1
                dist[nr][nc] = nd
                if max_d < nd:
                    max_d = nd
                q.append((nr, nc, nd))

    print(max_d)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#全てのマスに対して、そこからスタートして幅探索で最長を求め、そのうちの最大をとる

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
if s==[list('.'*20) for i in range(h)]:
    print(40-2)
else:
    ans=0
    Q=deque()
    vec=[(1,0),(0,1),(-1,0),(0,-1)]
    his=[[False for i in range(w)] for j in range(h)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            Q.append([i,j,0])
            while Q:
                x,y,d=Q.popleft()
                for dx,dy in vec:
                    tx=x+dx
                    ty=y+dy
                    if 0<=tx and tx<h and 0<=ty and ty<w and his[tx][ty]==False and s[tx][ty]=='.':
                        Q.append([tx,ty,d+1])
                        his[x][y]=True
                        ans=max(d+1,ans)
            his=[[False for i in range(w)] for j in range(h)]
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

INF = 10 ** 6
visited = [[10 ** 6] * W for _ in range(H)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


def bfs(y, x):
    q = deque()
    q.append((y, x))

    while len(q):
        y, x = q.popleft()

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

            if (0 <= ny < H and 0 <= nx < W and
                visited[ny][nx] == INF and S[ny][nx] != '#'):

                q.append((ny, nx))
                visited[ny][nx] = visited[y][x] + 1

ans = 0
for y in range(H):
    for x in range(W):
        visited = [[10 ** 6] * W for _ in range(H)]
        visited[y][x] = 0
        bfs(y, x)
        for i in range(H):
            for j in range(W):
                if visited[i][j] != INF:
                    ans = max(ans, visited[i][j])

print(ans)

Submission status: Wrong Answer

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

from collections import deque
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
for i in range(H):
    for j in range(W):
        ll = [[0] * W for _ in range(H)]
        q = deque([(i, j)])
        while q:
            y, x = q.popleft()
            for dy, dx in d:
                if 0 <= y+dy < H and 0 <= x+dx < W and l[y+dy][x+dx] == '.' and ll[y+dy][x+dx] == 0:
                    n = ll[y][x] + 1
                    ll[y+dy][x+dx] = n
                    if ans < n:
                        ans = n
                    q.append((y+dy, x+dx))

print(ans)

Submission status: Wrong Answer

Solution code:
def visit(maze, state, i, j):
  #maze: 迷路 (H, W)
  #state 各マスに、Sの位置からの最小値が格納された状態 (H, W)
  if i>0 and maze[i-1][j]=="." and state[i-1][j]>=state[i][j]+1:
    state[i-1][j]=state[i][j]+1
    state=visit(maze, state, i-1, j)
  if i<H-1 and maze[i+1][j]=="." and state[i+1][j]>=state[i][j]+1:
    state[i+1][j]=state[i][j]+1
    state=visit(maze, state, i+1, j)
  if j>0 and maze[i][j-1]=="." and state[i][j-1]>=state[i][j]+1:
    state[i][j-1]=state[i][j]+1
    state=visit(maze, state, i, j-1)
  if j<W-1 and maze[i][j+1]=="." and state[i][j+1]>=state[i][j]+1:
    state[i][j+1]=state[i][j]+1
    state=visit(maze, state, i, j+1)
  return state

H, W=map(int, input().split())
S=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    state=[[1000 for _ in range(W)] for _ in range(H)]
    state[i][j]=0
    state=visit(S, state, i, j)
    for i in range(H):
      for j in range(W):
        if state[i][j]==1000:
          state[i][j]=0
    for i in range(H):
      ans=max(ans, max(state[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
h, w = [int(v) for v in input().split()]
field = [list(input()) for i in range(h)]

def bfs(s, t):
    si, sj = s
    ti, tj = t
    search_field = [ [ -1 for i in range(w) ] for j in range(h) ]
    search_list = [s]
    turn = 0
    search_field[si][sj] = turn
    
    
    while search_list:
        turn += 1
        new_search_list = []
        for p in search_list:
            pi, pj = p
            
            for q in adjust_list:
                qi, qj = q
                if 0 <= pi+qi < h and 0 <= pj+qj < w:
                    if search_field[pi+qi][pj+qj] == -1 and field[pi+qi][pj+qj] == ".":
                        new_search_list.append((pi+qi,pj+qj))
                        search_field[pi+qi][pj+qj] = turn
        search_list = new_search_list

    return search_field[ti][tj]
    

ans = 0
coodinate = [ (i, j) for i in range(h) for j in range(w) ]
k = h*w

for i in range(k-1):
    for j in range(i+1, k):
        ans = max(ans, bfs(coodinate[i], coodinate[j]))
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
r,c=map(int,input().split())
ko =[list(input()) for i in range(r)]

ans = 0
for sy in range(r):
    for sx in range(c):
        for gy in range(r):
            for gx in range(c):
                if ko[sy][sx] == "." and ko[gy][gx] == ".":
                    a = [[0 for i in range(c)] for i in range(r)]
                    q = queue.Queue()
                    d=[(-1,0),(1,0),(0,-1),(0,1)]
                    a[sy][sx]=0

                    for i in d:
                        if 0<=sy+i[0]< r and 0<=sx+i[1]< c and ko[sy+i[0]][sx+i[1]]==".":
                            a[sy+i[0]][sx+i[1]]=1
                            q.put((sy+i[0],sx+i[1]))

                    while True:
                        y,x=q.get()
                        if y==gy and x==gx:
                            break
                        for i in d:
                            if 0<=y+i[0]< r and 0<=x+i[1]< c and ko[y+i[0]][x+i[1]]==".":
                                a[y+i[0]][x+i[1]]=a[y][x]+1
                                q.put((y+i[0],x+i[1]))
                    #print("出発地", sx, sy, "到着地", gx, gy,a[gy][gx])
                    if a[gy][gx] > ans:
                        ans = a[gy][gx]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 10**5
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy):
    # すべての点を INF で初期化
    d = [[-INF] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # for i in range(n):
    #     for j in range(m):
            # スタートとゴールの座標を探す
            # if maze[i][j] == "S":
            #     sx = i
            #     sy = j
            # if maze[i][j] == "G":
            #     gx = i
            #     gy = j

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

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

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == -INF:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d


n, m = map(int, input().split())
ma = [list(input()) for i in range(n)]
maxm=0
for i in range(m):
    for j in range(n):
        a = bfs(ma, j, i)
        # print(a)
        for x in a:
            for y in x:
                maxm = maxm if maxm>y else y
print(maxm)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
ans=-1
s=[]
for i in range(h):
	ss=input()
	s.append(ss)
from collections import deque as dq
for i in range(h):
	for j in range(w):
		dis=[[10**3 for _ in range(w)]for _ in range(h)]
		dis[i][j]=0
		queue=dq([[i,j]])
		while queue:
			r=queue.popleft()
			if r[0]+1<h:
				if s[r[0]+1][r[1]]=="." and dis[r[0]+1][r[1]]==10**3:
					queue.append([r[0]+1,r[1]])
					dis[r[0]+1][r[1]]=dis[r[0]][r[1]]+1
			if r[0]-1>=0:
				if s[r[0]-1][r[1]]=="." and dis[r[0]-1][r[1]]==10**3:
					queue.append([r[0]-1,r[1]])
					dis[r[0]-1][r[1]]=dis[r[0]][r[1]]+1
			if r[1]+1<w:
				if s[r[0]][r[1]+1]=="." and dis[r[0]][r[1]+1]==10**3:
					queue.append([r[0],r[1]+1])
					dis[r[0]][r[1]+1]=dis[r[0]][r[1]]+1
			if r[1]+1>=0:
				if s[r[0]][r[1]-1]=="." and dis[r[0]][r[1]-1]==10**3:
					queue.append([r[0],r[1]-1])
					dis[r[0]][r[1]-1]=dis[r[0]][r[1]]+1
		for k in range(h):
			for l in range(w):
				if dis[k][l]!=10**3:
					ans=max(ans,dis[k][l])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
MEIJI = [[0] * W for i in range(H)]

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            MEIJI[i][j] = 1


def findStart():
    for x in range(H):
        for y in range(W):
            if MEIJI[x][y] == 0:
                return x, y

    return False


def bfs(H, W, sx, sy):
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

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

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

if l < 0:
    l = 0

print(l)

Submission status: Wrong Answer

Solution code:
map_height,map_width=map(int,input().split())
d={'.':0,'#':-1}
map_data= [list(map(lambda x: d[x],list(input()))) for _ in range(map_height)]

import itertools
Z= map_width*map_height

#m = np.ones((map_width*map_height,map_width*map_height))*float("inf")
m = [[401 for _ in range(Z)] for _ in range(Z)]
for i,j in itertools.product(range(map_height),range(map_width)):
    if map_data[i][j] == 0:
        for i_n, j_n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 0 <= i_n < map_height and 0 <= j_n < map_width:
                if map_data[i_n][j_n] == 0:
                    m[map_width*i+j][map_width*i_n+j_n] = 1
for k in range(Z):
    for i in range(Z):
        for j in range(Z):
            temp = min(m[i][j],m[i][k] + m[k][j])
            m[i][j] = temp
                
ans = 0
for i in range(Z):
    for j in range(Z):
        temp = m[i][j]
        if temp != 401:
            if ans < m[i][j]:
                ans = m[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
lst1 = [list(list(input())) for i in range(H)]

def dfs(maze,visited, sh, sw):
    a = 0
    stack = deque([[sh, sw]])
    visited[sh][sw] = 0
    while stack:
        h, w = stack.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #4近傍について探索
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W: #リスト外でないならelif条件へ
                continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == 0: #行ったことがないかつ、壁でないなら
                visited[new_h][new_w] = visited[h][w]+1
                stack.append([new_h, new_w])
    a = 0
    for s in range(H):
        for x in range(W):
            a = max(a,visited[s][x])
    return a

ans = 0

for i in range(H):
    for q in range(W):
        visited = [[0]*W for _ in range(H)]
        if lst1[i][q] == ".":
            ans = max(ans,dfs(lst1,visited,i,q))
print(ans)