Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Wrong Answer

Solution code:
import queue

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

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

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            seen=[[0 for _ in range(w)] for _ in range(h)]
            length=[[0 for _ in range(w)] for _ in range(h)]
            q=queue.Queue()
            q.put([i,j])
            seen[i][j]=1
            while not q.empty():
                ci,cj=q.get()
                for ni,nj in [[ci-1,cj],[ci+1,cj],[ci,cj-1],[ci,cj+1]]:
                    if 0<=ni<h and 0<=nj<w and s[ni][nj]=="." and seen[ni][nj]==0:
                        q.put([ni,nj])
                        length[ni][nj]=length[ci][cj]+1
                        seen[ni][nj]=1
            ans=max(ans,max(max(length)))

print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

s=[]
for i in range(h):
    s.append(input())

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        qij=queue.Queue()
        qij.put([i,j])
        lis=[[0 for _ in range(w)] for _ in range(h)]
        check=[[0 for _ in range(w)] for _ in range(h)]
        check[i][j]=1
        while not qij.empty():
            ci,cj=qij.get()
            for a,b in [[ci+1,cj],[ci-1,cj],[ci,cj+1],[ci,cj-1]]:
                if 0<=a<=h-1 and 0<=b<=w-1 and s[a][b]=="." and check[a][b]==0:
                    lis[a][b]=lis[ci][cj]+1
                    qij.put([a,b])
                    check[a][b]=1
        ans=max(ans,max(max(lis)))
        
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

s=[]
for i in range(h):
    s.append(input())

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        qij=queue.Queue()
        qij.put([i,j])
        lis=[[0 for _ in range(w)] for _ in range(h)]
        check=[[0 for _ in range(w)] for _ in range(h)]
        check[i][j]=1
        while not qij.empty():
            ci,cj=qij.get()
            for a,b in [[ci+1,cj],[ci-1,cj],[ci,cj+1],[ci,cj-1]]:
                if 0<=a<=h-1 and 0<=b<=w-1 and s[a][b]=="." and check[a][b]==0:
                    lis[a][b]=lis[ci][cj]+1
                    qij.put([a,b])
                    check[a][b]=1
        ans=max(ans,max(max(lis)))
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

s=[]
for i in range(h):
    s.append(input())

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        qij=queue.Queue()
        qij.put([i,j])
        lis=[[0 for _ in range(w)] for _ in range(h)]
        check=[[0 for _ in range(w)] for _ in range(h)]
        while not qij.empty():
            ci,cj=qij.get()
            check[ci][cj]=1
            for a,b in [[ci+1,cj],[ci-1,cj],[ci,cj+1],[ci,cj-1]]:
                if 0<=a<=h-1 and 0<=b<=w-1 and s[a][b]=="." and check[a][b]==0:
                    lis[a][b]=lis[ci][cj]+1
                    qij.put([a,b])
        ans=max(ans,max(max(lis)))
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

s=[]
for i in range(h):
    s.append(input())

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        qij=queue.Queue()
        qij.put([i,j])
        lis=[[0 for _ in range(w)] for _ in range(h)]
        check=[[0 for _ in range(w)] for _ in range(h)]
        while not qij.empty():
            ci,cj=qij.get()
            check[ci][cj]=1
            for a,b in [[ci+1,cj],[ci-1,cj],[ci,cj+1],[ci,cj-1]]:
                if 0<=a<=h-1 and 0<=b<=w-1 and s[a][b]=="." and lis[a][b]==0:
                    lis[a][b]=lis[ci][cj]+1
                    qij.put([a,b])
        ans=max(ans,max(max(lis)))
print(ans)

Submission status: Wrong Answer

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

S = []
for i in range(H):
    S.append(list(input()))
# print('S:',*S,sep='\n')

out=[]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#スタート・ゴール全探索
for i_s in range(H):
    for j_s in range(W):
        for i_g in range(H):
            for j_g in range(W):
                # print('S,G:',i_s,j_s,i_g,j_g)
                #BFS
                init = 10**9
                d = [[init] * W for i in range(H)]  #これを更新していく
                # print('d:',*d, sep='\n')
                que = deque([])
                que.append((i_s,j_s))
                d[i_s][j_s] = 0
                while que:
                    p = que.popleft()
                    if p[0] == i_g and p[1] == j_g:
                        break
                    for i in range(4):  #四方をチェック
                        nx = p[0] + dx[i]
                        ny = p[1] + dy[i]
                        # print('p,nx,ny,S[nx][ny]:',p,nx,ny,S[nx][ny])
                        if (0<=nx<H)and(0<=ny<W)and(S[nx][ny]!="#")and(d[nx][ny]==init):
                            # print('yahhoooo')
                            que.append((nx, ny))  #後で(nx,ny)の四方みていくよ
                            d[nx][ny] = d[p[0]][p[1]] + 1  #d更新しておくよ
                # print('d:',*d, sep='\n')
                # print('ゴール',d[i_g][j_g])
                if d[i_g][j_g]!=init:
                    out.append(d[i_g][j_g])   #ゴールの回数
# print(out)
print(max(out))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
ma = [["#" for _ in range(w+2)] for _ in range(h+2)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        ma[i+1][j+1] = tmp[j]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if ma[i][j] == "#":
            continue
        elif ma[i][j] == ".":
            p = [[-1 for _ in range(w+2)] for _ 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])
            ans = max(ans, max(max(p)))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map( int, input().split() )
s = []
for _ in range( h ):
    s_i = list( str( input() ) )
    s.append( s_i )

def connect( v ):
    con_v = []
    if v[ 0 ] > 0:
        if s[ v[ 0 ] - 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] - 1, v[ 1 ] ) )
    if v[ 1 ] > 0:
        if s[ v[ 0 ] ][ v[ 1 ] - 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] - 1 ) )
    if v[ 0 ] < h - 1:
        if s[ v[ 0 ] + 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] + 1, v[ 1 ] ) )
    if v[ 1 ] < w - 1:
        if s[ v[ 0 ] ][ v[ 1 ] + 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] + 1 ) )
    return con_v

from heapq import heappush, heappop
INF = 10 ** 10
VISITED = 1
NOT_VISITED = 0
def longest_bfs( i, j ):
    cost = [ INF for _ in range( h * w ) ]
    cost[ i * w + j ] = 0
    visit = [ NOT_VISITED for _ in range( h * w ) ]
    queue = [ ( 0, ( i, j ) ) ]
    while len( queue ) > 0:
        c, v = heappop( queue )
        visit[ v[ 0 ] * w + v[ 1 ] ] = VISITED
        for u in connect( v ):
            if visit[ u[ 0 ] * w + u[ 1 ] ] == VISITED:
                continue
            if cost[ u[ 0 ] * w + u[ 1 ] ] > cost[ v[ 0 ] * w + v[ 1 ] ] + 1:
                cost[ u[ 0 ] * w + u[ 1 ] ] = cost[ v[ 0 ] * w + v[ 1 ] ] + 1
                heappush( queue, ( cost[ u[ 0 ] * w + u[ 1 ] ], u ) )
    return cost

longest_path = 0
for i in range( h ):
    for j in range( w ):
        path_length = longest_bfs( i, j )
        for p in path_length:
            if p < INF and p > longest_path:
                longest_path = p
print( longest_path )

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

h,w = inpm()
maze = inplL(h)

sh,sw = (0,0)
gh,gw = (h-1,w-1)

q = queue.Queue()
q.put((sh,sw,0))

field = [[-1]*w for i in range(h)]
sh_new,sw_new = (0,0)
gh_new,gw_new = (0,0)
tmp = 0
while not q.empty():
    yy,xx,kk = q.get()
    if field[yy][xx] >= 0: continue

    field[yy][xx] = kk
    if tmp < kk:
        sh_new,sw_new = (yy,xx)
        tmp = kk
    if yy != h-1 and maze[yy+1][xx] == '.':
        q.put((yy+1,xx,kk+1))
    if xx != w-1 and  maze[yy][xx+1] == '.':
        q.put((yy,xx+1,kk+1))
    if yy != 0 and  maze[yy-1][xx] == '.':
        q.put((yy-1,xx,kk+1))
    if xx != 0 and  maze[yy][xx-1] == '.':
        q.put((yy,xx-1,kk+1))

field = [[-1]*w for i in range(h)]
q = queue.Queue()
q.put((sh_new,sw_new,0))
tmp = 0
while not q.empty():
    yy,xx,kk = q.get()
    if field[yy][xx] >= 0: continue

    field[yy][xx] = kk
    if tmp < kk:
        gh_new,gw_new = (yy,xx)
        tmp = kk
    if yy != h-1 and maze[yy+1][xx] == '.':
        q.put((yy+1,xx,kk+1))
    if xx != w-1 and  maze[yy][xx+1] == '.':
        q.put((yy,xx+1,kk+1))
    if yy != 0 and  maze[yy-1][xx] == '.':
        q.put((yy-1,xx,kk+1))
    if xx != 0 and  maze[yy][xx-1] == '.':
        q.put((yy,xx-1,kk+1))

print(field[gh_new][gw_new])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
def maze_solve(S_1,S_2,maze_list):
    d = deque()
    d.append([S_1,S_2])
    dist[S_1][S_2] = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
ans = 0
maze = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
start_list = []
for i in range(h):
  for j in range(w):
    if maze[i][j] == "#":
      dist[i][j] = 0
    else:
      start_list.append([i,j])
      dist_copy = deepcopy(dist)
      for k in start_list:
        dist = deepcopy(dist_copy)
        ans = max(ans,maze_solve(k[0],k[1],maze))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
def maze_solve(S_1,S_2,maze_list):
    d = deque()
    d.append([S_1,S_2])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
ans = 0
maze = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
start_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            dist[i][j] = 0
        else:
            start_list.append([i,j])
dist_copy = deepcopy(dist)
for k in start_list:
    dist = deepcopy(dist_copy)
    ans = max(ans,maze_solve(k[0],k[1],maze))
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(S, sh, sw, dist):
    dist[sh][sw] = 0
    queue = deque([(sh, sw)])
    while queue:
        h, w = queue.popleft()
        for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            y, x = h + i, w + j
            if S[y][x] == "#":
                continue
            if dist[y][x] == -1:
                dist[y][x] = dist[h][w] + 1
                queue.append((y, x))


def main():
    H, W = map(int, input().split())
    S = [None] * (H + 2)
    S[0] = S[-1] = "#" * (W + 2)
    for i in range(1, H + 1):
        S[i] = "".join(["#", input().rstrip(), "#"])

    ans = 0
    for sh in range(1, H + 1):
        for sw in range(1, W + 1):
            dist = [[-1] * (W + 2) for _ in range(H + 2)]
            bfs(S, sh, sw, dist)
            max_dist = max(map(max, dist))
            ans = max(ans, max_dist)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

H,W = (int(x) for x in input().rstrip('\n').split())

m = []
for i in range(H):
  S = list(input().rstrip('\n'))
  m.append(S)
r = []
for x in range(W):
  for y in range(H):
    if m[y][x] == '.':
      r.append((x,y))
res = 0
for x,y in r:
  res_n = 0
  ok = [(x,y)]
  used = []
  for _ in range(50) :
    ok_n = []
    for X,Y in ok:
      next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0])]
      for i in next:
        if i in used or m[i[1]][i[0]] != '.':
          a=1
        else:
          ok_n.append(i)
    used.extend(ok)
    ok = ok_n
    if len(ok)>0:
      res_n += 1
    else:
      break
  if res < res_n:
    res = res_n
print(res)

Submission status: Wrong Answer

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

H,W = (int(x) for x in input().rstrip('\n').split())

m = []
for i in range(H):
  S = list(input().rstrip('\n'))
  m.append(S)
r = []
for x in range(W):
  for y in range(H):
    if m[y][x] == '.':
      r.append((x,y))
res = 0
for x,y in r:
  res_n = 0
  ok = [(x,y)]
  used = []
  for _ in range(50) :
    ok_n = []
    for X,Y in ok:
      next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0])]
      for i in next:
        if i in used or m[i[1]][i[0]] != '.':
          pass
        else:
          ok_n.append(i)
    used.extend(ok)
    ok = ok_n
    if len(ok)>0:
      res_n += 1
    else:
      break
  if res < res_n:
    res = res_n
print(res)

Submission status: Wrong Answer

Solution code:
import os
import sys
import numpy as np

def solve(H, W, S):
    N = H*W
    G = np.empty((N, N), dtype=np.int64)
    G[:] = 9999999
    for h in range(H):
        for w in range(W):
            i = h*W + w
            if w < W-1 and S[h][w] == S[h][w+1] == 46:
                G[i, i+1] = G[i+1, i] = 1
            if h < H-1 and S[h][w] == S[h+1][w] == 46:
                G[i, i+W] = G[i+W, i] = 1
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i, j] > G[i, k] + G[k, j]:
                    G[i, j] = G[i, k] + G[k, j]
    # G[G>=9999999] = 0
    G = np.where(G>=9999999, 0, G)

    ans = G.max()
    return ans


# >>> numba compile >>>
numba_config = [
    [solve, "i8(i8,i8,u1[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


import sys
def main():
    input= sys.stdin.buffer.readline
    H, W = map(int, input().split())
    S = np.array([np.frombuffer(input(), dtype=np.uint8) for _ in range(H)])
    print(solve(H, W, S))

main()

Submission status: Wrong Answer

Solution code:
class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0

        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    #辺の追加
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]


    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.adjacent

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in G.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in G.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None

    #グラフの直径
    def diameter(self):
        from collections import deque
        inf=float("inf")

        u=set(G.adjacent.keys()).pop()
        T={u:inf  for u in G.adjacent}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)

        w=max(T,key=lambda x:T[x])
        T={u:inf  for u in G.adjacent}

        Q=deque([w])
        T[w]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        w=max(T,key=lambda x:T[x])
        return T[w]

#格子グラフ
def Grid_Graph(m,n):
    E=[]
    for x in range(1,m+1):
        E+=[(x,y) for y in range(1,n+1)]

    G=Graph(E)
    H=[(1,0),(0,1)]

    for y in range(1,n+1):
        for x in range(1,m+1):
            for a,b in H:
                p=x+a
                q=y+b
                if 1<=p<=m and 1<=q<=n:
                    G.add_edge((x,y),(p,q))
    return G
#====================================================
H,W=map(int,input().split())

G=Grid_Graph(W,H)
for y in range(H):
    S=input()
    for x in range(W):
        if S[x]=="#":
            G.remove_vertex((x+1,y+1))
print(G.diameter())

Submission status: Wrong Answer

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

H,W = (int(x) for x in input().rstrip('\n').split())

m = []
for i in range(H):
  S = list(input().rstrip('\n'))
  m.append(S)
r = []
for x in range(W):
  for y in range(H):
    if m[y][x] == '.':
      r.append((x,y))
res = 0
for x,y in r:
  res_n = 0
  ok = [(x,y)]
  used = []
  while len(ok) > 0 :
    ok_n = []
    for X,Y in ok:

      if X==0:
        if Y==0:
          next = [(X+1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X+1,Y),(X,Y-1)]
        else:
          next = [(X+1,Y),(X,Y-1),(X,Y+1)]
      elif X==H-1:
        if Y==0:
          next = [(X-1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X-1,Y),(X,Y-1)]
        else:
          next = [(X-1,Y),(X,Y-1),(X,Y+1)]
      else:
        if Y==0:
          next = [(X+1,Y),(X-1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X+1,Y),(X-1,Y),(X,Y-1)]
        else:
          next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if i not in used]
      for i in next:
        try:
          if m[i[1]][i[0]] == '.':
            ok_n.append(i)
        except:
          pass
    used.extend(ok)
    ok = ok_n
    if len(ok)>0:
      res_n += 1

  if res < res_n:
    res = res_n
print(res)

Submission status: Wrong Answer

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

H,W = (int(x) for x in input().rstrip('\n').split())

m = []
for i in range(H):
  S = list(input().rstrip('\n'))
  m.append(S)
r = []
for x in range(W):
  for y in range(H):
    if m[y][x] == '.':
      r.append((x,y))
res = 0
for x,y in r:
  res_n = 0
  ok = [(x,y)]
  used = []
  while len(ok) > 0 :
    ok_n = []
    for X,Y in ok:
      if X==0:
        if Y==0:
          next = [(X+1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X+1,Y),(X,Y-1)]
        else:
          next = [(X+1,Y),(X,Y-1),(X,Y+1)]
      elif X==H-1:
        if Y==0:
          next = [(X-1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X-1,Y),(X,Y-1)]
        else:
          next = [(X-1,Y),(X,Y-1),(X,Y+1)]
      else:
        if Y==0:
          next = [(X+1,Y),(X-1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X+1,Y),(X-1,Y),(X,Y-1)]
        else:
          next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0])]
      next = [i for i in next if i not in used]
      next = [i for i in next if m[i[1]][i[0]] == '.']
      ok_n.extend(next)
    used.extend(ok)
    ok = ok_n
    res_n += 1
  if res < res_n-1:
    res = res_n-1
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
H,W = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for i in range(H):
    grid[i] = list(input())
ans = 0
for sy in range(H):
    for sx in range(W):
        now_grid = copy.deepcopy(grid)
        time_grid = [[-1]*W for _ in range(H)]
        queue = deque()
        queue.append([sy,sx,0])
        now_grid[sy][sx] = '#'
        while queue:
            y,x,t = queue.popleft()
            for next_y, next_x in [[y+1, x],[y,x+1],[y-1,x],[y,x-1]]:
                if 0<= next_y < H and 0 <= next_x < W and now_grid[next_y][next_x] != '#':
                    queue.append([next_y,next_x,t+1])
                    time_grid[next_y][next_x] = t+1
                    now_grid[next_y][next_x] = '#'
        Max= 0
        for i in range(H):
            for j in range(W):
                Max = max(Max,time_grid[i][j])
        ans = max(ans, Max)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
H,W = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for i in range(H):
    grid[i] = list(input())
ans = 0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if sy == gy and sx == sy:
                    continue
                now_grid = copy.deepcopy(grid)
                time_grid = [[-1]*W for _ in range(H)]
                queue = deque()
                queue.append([sy,sx,0])
                now_grid[sy][sx] = '#'
                while queue:
                    y,x,t = queue.popleft()
                    for next_y, next_x in [[y+1, x],[y,x+1],[y-1,x],[y,x-1]]:
                        if 0<= next_y < H and 0 <= next_x < W and now_grid[next_y][next_x] != '#':
                            queue.append([next_y,next_x,t+1])
                            time_grid[next_y][next_x] = t+1
                            now_grid[next_y][next_x] = '#'
                ans = max(ans, time_grid[gy][gx])
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = []
S.append(['#' for _ in range(W+2)])
for _ in range(H):
  s = input()
  s = '#' + s + '#'
  S.append([])
  for k in range(W+2):
    S[-1].append(s[k])
S.append(['#' for _ in range(W+2)])
b = 0
start = []
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h][w] == '.':
      c = 0
      b += 1
      if S[h+1][w] == '.':
        c += 1
      if S[h-1][w] == '.':
        c += 1
      if S[h][w+1] == '.':
        c += 1
      if S[h][w-1] == '.':
        c += 1
      if c == 1:
        start.append([h, w])
if len(start) == 0:
  for h in range(1, H+1):
    for w in range(1, W+1):
      if S[h][w] == '.':
        c = 0
        if S[h+1][w] == '.':
          c += 1
        if S[h-1][w] == '.':
          c += 1
        if S[h][w+1] == '.':
          c += 1
        if S[h][w-1] == '.':
          c += 1
        if c == 2:
          start.append([h, w])

def solve(nowh, noww, point):
  counter[nowh][noww] = point
  flag = True
  if point > min(anskouho):
    return 0
  if counter[nowh+1][noww] > point + 1:
    solve(nowh+1, noww, point+1)
    flag = False
  if counter[nowh-1][noww] > point + 1:
    solve(nowh-1, noww, point+1)
    flag = False
  if counter[nowh][noww+1] > point + 1:
    solve(nowh, noww+1, point+1)
    flag = False
  if counter[nowh][noww-1] > point + 1:
    solve(nowh, noww-1, point+1)
    flag = False
  if flag:
    anskouho.append(point)
    return 0


ans = 0
for item in start:
  original_counter = [[b for _ in range(W+2)] for _ in range(H+2)]
  for k in range(H+2):
    for j in range(W+2):
      if S[k][j] == '#':
        original_counter[k][j] = -1
  counter = original_counter
  anskouho = [b]
  solve(item[0], item[1], 0)
  ans = max(ans, min(anskouho))

print(ans)