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 collections
H, W, *S = open(0).read().split()
H,W=[int(_) for _ in [H,W]]
G = [set() for _ in range(H * W)]
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                G[i].add(nx * W + ny)
INF = 10 ** 10
dist = [INF] * (H * W)
ans = 0
for s in range(H * W):
    if len(G[s]) and dist[s] == INF:
        Q = collections.deque([s])
        se = set()
        while True:
            if not Q:
                break
            i = Q.popleft()
            for j in G[i]:
                if j in se:
                    continue
                se.add(j)
                k = j
                Q += [j]
        dist[k] = 0
        se = set()
        Q = collections.deque([k])
        while True:
            if not Q:
                break
            i = Q.popleft()
            if i in se:
                break
            se.add(i)
            d = dist[i]
            for j in G[i]:
                if dist[j] != INF:
                    continue
                k = j
                dist[j] = d + 1
                Q += [j]
        ans = max(ans, dist[k])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
H, W, *S = open(0).read().split()
H,W=[int(_) for _ in [H,W]]
G = [set() for _ in range(H * W)]
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                G[i].add(nx * W + ny)
INF = 10 ** 10
dist = [INF] * (H * W)
ans = 0
for s in range(H * W):
    if len(G[s]) and dist[s] == INF:
        Q = collections.deque([s])
        se = set()
        while True:
            if not Q:
                break
            i = Q.popleft()
            for j in G[i]:
                if j in se:
                    continue
                se.add(j)
                k = j
                Q += [j]
        dist[k] = 0
        se = set()
        Q = collections.deque([k])
        while True:
            if not Q:
                break
            i = Q.popleft()
            if i in se:
                break
            se.add(i)
            d = dist[i]
            for j in G[i]:
                if dist[j] != INF:
                    continue
                k = j
                dist[j] = d + 1
                Q.appendleft(j)
        ans = max(ans, dist[k])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
H, W, *S = open(0).read().split()
H,W=[int(_) for _ in [H,W]]
G = [set() for _ in range(H * W)]
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                G[i].add(nx * W + ny)
INF = 10 ** 10
dist = [INF] * (H * W)
ans = 0
for s in range(H * W):
    if len(G[s]) and dist[s] == INF:
        Q = collections.deque([s])
        se = set()
        while True:
            if not Q:
                break
            i = Q.popleft()
            for j in G[i]:
                if j in se:
                    continue
                se.add(j)
                k = j
                Q.appendleft(j)
        dist[k] = 0
        se = set()
        Q = collections.deque([k])
        while True:
            if not Q:
                break
            i = Q.popleft()
            if i in se:
                break
            se.add(i)
            d = dist[i]
            for j in G[i]:
                if dist[j] != INF:
                    continue
                k = j
                dist[j] = d + 1
                Q.appendleft(j)
        ans = max(ans, dist[k])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
H, W, *S = open(0).read().split()
H,W=[int(_) for _ in [H,W]]
G = [set() for _ in range(H * W)]
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                G[i].add(nx * W + ny)
for s in range(H * W):
    if len(G[s]):
        break
Q = collections.deque([s])
INF = 10 ** 10
d1 = [INF] * (H * W)
d1[s] = 0
while True:
    if not Q:
        break
    i = Q.popleft()
    d = d1[i]
    for j in G[i]:
        if d1[j] != INF:
            continue
        k = j
        d1[j] = d + 1
        Q.appendleft(j)
d1 = [INF] * (H * W)
d1[k] = 0
Q = collections.deque([k])
while True:
    if not Q:
        break
    i = Q.popleft()
    d = d1[i]
    for j in G[i]:
        if d1[j] != INF:
            continue
        k = j
        d1[j] = d + 1
        Q.appendleft(j)
print(d1[k])

Submission status: Wrong Answer

Solution code:
import collections
H, W, *S = open(0).read().split()
H,W=[int(_) for _ in [H,W]]
G = [set() for _ in range(H * W)]
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                G[i].add(nx * W + ny)
for s in range(H * W):
    if len(G[s]):
        break
Q = collections.deque([s])
INF = 10 ** 10
d1 = [INF] * (H * W)
d1[s] = 0
while True:
    if not Q:
        break
    i = Q.popleft()
    d = d1[i]
    for j in G[i]:
        if d1[j] != INF:
            continue
        k = j
        d1[j] = d + 1
        Q.appendleft(j)
d1 = [INF] * (H * W)
d1[k] = 0
Q = collections.deque([k])
while True:
    if not Q:
        break
    i = Q.popleft()
    d = d1[i]
    for j in G[i]:
        if d1[j] != INF:
            continue
        d1[j] = d + 1
        Q.appendleft(j)
print(d1[k])

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)] #マップ
vi=[ [-1 for _ in range(w)] for _ in range(h)]#visit
st=deque()

d=[[0,1],[-1,0],[1,0],[0,-1]]

mx=0

for i in range(h):
  for j in range(w):
    vi=[ [-1 for _ in range(w)] for _ in range(h)]
    st.append([i,j,0])
    
    while st:
      h1,w1,i=st.popleft()

      if 0<=h1<h and 0<=w1<w and vi[h1][w1]==-1 and s[h1][w1]==".":
        vi[h1][w1]=i+1
        for m in d:
          st.append([h1+m[0],w1+m[1],i+1])
    for m in vi:
      mx=max(mx,max(m)-1)

print(mx)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

h,w=map(int,input().split())
maze1=[]
for _ in range(h):
  s=list(input())
  maze1.append(s)
  
def maze_solve(maze,sy,sx,gy,gx):
  Inf=float(inf)
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        if maze[ny][nx]=='.':
          maze[ny][nx]=T+1
          qu.append([ny,nx])
        elif maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
  if maze[gy][gx]!='.':
    return maze[gy][gx]
  else:
    return -Inf
  
inf=float('inf')
ans=-inf
for i in range(h-1):
  for j in range(w-1):
    if maze1[i][j]=='.':
      for x in range(i,h):
        for y in range(j,w):
          if maze1[x][y]=='.':
            maze2=copy.deepcopy(maze1)
            
            ans=max(ans,maze_solve(maze2,i,j,x,y))
            
            
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    H, W = list(map(int, input().split()))
    maps =[list(input()) for _ in range(H)]
    mv = {(1, 0), (-1, 0), (0, 1), (0, -1)}

    ans = 0
    for i in range(H):
        for j in range(W):
            if maps[i][j] == '#':
                continue
        stk = deque([[i,j,0]])
        seen = [[False]*W for _ in range(H)]
        while len(stk) > 0:
            l = stk.pop()
            i = l[0]
            j = l[1]
            ct = l[2]
            seen[i][j] = True
            for k in mv:
                x = i+k[0]
                y = j+k[1]
                if 0 <= x < H and 0 <= y < W and \
                    maps[x][y] == '.' and seen[x][y] == False:
                        stk.appendleft([x, y, ct+1])
        ans = max(ans, ct)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_count=[[0]*W for i in range(H)]
from collections import deque
def answer(st_X,st_Y):#X,Y座標を指定してそこからの距離を考える
   tmp_X,tmp_Y=st_X,st_Y
   que=deque([[tmp_X,tmp_Y]])
   after=[]
   while que:#スタート地点からの距離を数えながら行ったことのない場所を探索する
      tmp_X,tmp_Y=que.popleft()
      nu=l_count[tmp_Y][tmp_X]
      after.append([tmp_X,tmp_Y])
      if tmp_X>0 and l[tmp_Y][tmp_X-1]=="." and [tmp_X-1,tmp_Y] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X-1]=nu+1
         que.append([tmp_X-1,tmp_Y])
      if tmp_Y>0 and l[tmp_Y-1][tmp_X]=="." and [tmp_X,tmp_Y-1] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y-1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y-1])
      if tmp_X<W-1 and l[tmp_Y][tmp_X+1]=="." and [tmp_X+1,tmp_Y] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X+1]=nu+1
         que.append([tmp_X+1,tmp_Y])
      if tmp_Y<H-1 and l[tmp_Y+1][tmp_X]=="." and [tmp_X,tmp_Y+1] not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y+1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y+1])
   que=deque(set(que))
ans=0
for i in range(H):
   for j in range(W):
      if l[i][j]==".":
         l_count=[[0]*W for i in range(H)]
         answer(j,i)
         tmp=max(sum(l_count,[]))
         ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_count=[[0]*W for i in range(H)]
from collections import deque
def answer(st_X,st_Y):#X,Y座標を指定してそこからの距離を考える
   tmp_X,tmp_Y=st_X,st_Y
   que=deque([[tmp_X,tmp_Y,0]])
   after=deque([])
   while que:#スタート地点からの距離を数えながら行ったことのない場所を探索する
      tmp_X,tmp_Y,nu=que.popleft()
      after.append([tmp_X,tmp_Y])
      if tmp_X>0 and l[tmp_Y][tmp_X-1]=="." and [tmp_X-1,tmp_Y] not in after:
         l_count[tmp_Y][tmp_X-1]=nu+1
         que.append([tmp_X-1,tmp_Y,nu+1])
      if tmp_Y>0 and l[tmp_Y-1][tmp_X]=="." and [tmp_X,tmp_Y-1] not in after:
         l_count[tmp_Y-1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y-1,nu+1])
      if tmp_X<W-1 and l[tmp_Y][tmp_X+1]=="." and [tmp_X+1,tmp_Y] not in after:
         l_count[tmp_Y][tmp_X+1]=nu+1
         que.append([tmp_X+1,tmp_Y,nu+1])
      if tmp_Y<H-1 and l[tmp_Y+1][tmp_X]=="." and [tmp_X,tmp_Y+1] not in after:
         l_count[tmp_Y+1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y+1,nu+1])
ans=0
for i in range(H):
   for j in range(W):
      l_count=[[0]*W for i in range(H)]
      answer(j,i)
      tmp=max(sum(l_count,[]))
      ans=max(ans,tmp)
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
d=deque([])
for i in range(H):
  for j in range(W):
    d.append((i,j,0))
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    c=0
    while d:
      x,y,c=d.popleft()
      for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and visited[nx][ny]==-1 and S[nx][ny]=='.':
          visited[nx][ny]=c+1
          d.append((nx,ny,c+1))
    ans=max(ans,c)
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
d=deque([])
for i in range(H):
  for j in range(W):
    d.append((i,j,0))
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    while d:
      x,y,c=d.popleft()
      for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and visited[nx][ny]==-1 and S[nx][ny]=='.':
          visited[nx][ny]=c+1
          d.append((nx,ny,c+1))
    ans=max(ans,c)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readlines

def main():

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

    lines = input()

    H, W = list(map(int, lines[0].split()))
    v = H * W
    P = [] #kaku tennno joukyou
    for i in range(1, H+1):
        asa = lines[i].split()[0]
        P.append(asa)

    A = [[INFTY] * v for i in range(v)]
    #shokika
    for vi in range(v):
        x = vi % W ; y = vi // W
        if P[y][x] == '#':
            continue
        for i in range(4):#4方向
            nx = x + dx[i] ; ny = y + dy[i]
            if nx < 0 or nx == W or ny < 0 or ny == H :
                continue
            if P[ny][nx] == '#':
                continue

            A[vi][nx+ny*W] = 1
    
    ## Floyd-Warshall
    for k in range(v):
        for i in range(v):
            if A[i][k] == INFTY:
                continue
            for j in range(v):
                if A[k][j] == INFTY:
                    continue
                a = A[i][j]
                b = A[i][k] + A[k][j]
                if a > b:
                    A[i][j] = b

    ## max search
    res = 0
    for vi in range(v):
        x = vi % W ; y = vi // W
        if P[y][x] == '#':
            continue
        for vj in range(v):
            c = A[vi][vj]
            if c > 5000:
                continue
            if c > res:
                res = c

    print(res)

main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, seen):
    queue = deque([start + (0 ,)])
    max_count = 0
    while queue:
        y,x,count = queue.popleft()
        max_count = max(max_count, count)
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            #print(next_y, next_x)
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                seen.add((next_y,next_x))
                queue.append((next_y, next_x, count+1))
    return max_count


def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    #for m in MAZE:
    #    print(m)

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for idx, (s_i, s_j) in enumerate(ways):
        seen = set((s_i, s_j))
        min_count = bfs(MAZE, (s_i, s_j), seen)
        #print((s_i, s_j), '->', (g_i, g_j))
        #print(min_count)
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, seen):
    queue = deque([start + (0 ,)])
    while queue:
        y,x,count = queue.popleft()
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            #print(next_y, next_x)
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                seen.add((next_y,next_x))
                queue.append((next_y, next_x, count+1))
    return count


def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    #for m in MAZE:
    #    print(m)

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for idx, (s_i, s_j) in enumerate(ways):
        seen = set((s_i, s_j))
        min_count = bfs(MAZE, (s_i, s_j), seen)
        #print((s_i, s_j), '->', (g_i, g_j))
        #print(min_count)
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, seen):
    queue = deque([start + (0 ,)])
    while queue:
        y,x,count = queue.popleft()
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            #print(next_y, next_x)
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                seen.add((next_y,next_x))
                queue.append((next_y, next_x, count+1))
    return count


def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    #for m in MAZE:
    #    print(m)

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for idx, (s_i, s_j) in enumerate(ways):
        seen = set()
        min_count = bfs(MAZE, (s_i, s_j), seen)
        #print((s_i, s_j), '->', (g_i, g_j))
        #print(min_count)
        if not min_count:
            continue
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, seen):
    queue = deque([start + (0 ,)])
    while queue:
        y,x,count = queue.popleft()
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            #print(next_y, next_x)
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                seen.add((next_y,next_x))
                queue.append((next_y, next_x, count+1))
    return count


def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    #for m in MAZE:
    #    print(m)

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for idx, (s_i, s_j) in enumerate(ways):
        for g_i, g_j in ways[idx+1:]:
            seen = set()
            min_count = bfs(MAZE, (s_i, s_j), seen)
            #print((s_i, s_j), '->', (g_i, g_j))
            #print(min_count)
            if not min_count:
                continue
            max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def dfs(MAZE, goal, current, seen, H, W, min_count = INF):
    y, x, count = current
    #print(x,y,count)
    if count > min_count:
        return min_count
    if (y,x) == goal:
        min_count = min(min_count, count)
    else:
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y+i, x+j
            if 1 <= next_x <= W and 1 <= next_y <= H and not seen[next_y][next_x] and MAZE[next_y][next_x] == '.':
                seen[next_y][next_x] = 1
                min_count = min(dfs(MAZE, goal, (next_y, next_x, count+1), seen, H, W, min_count), min_count)
                seen[next_y][next_x] = 0
    return min_count

def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    seen = [[0] * (W+2) for i in range(H+1)]

    max_count = 0
    for s_i in range(1, H+1):
        for s_j in range(1, W+1):
            for g_i in range(s_i, H + 1):
                for g_j in range(s_j, W + 1):
                    if s_i == g_i and s_j == g_j:continue
                    seen[s_i][s_j] = 1
                    min_count = dfs(MAZE, (g_i, g_j), (s_i, s_j, 0), seen, H, W)
                    #print((s_i, s_j), '->', (g_i, g_j))
                    #print(min_count)
                    if min_count == INF:
                        continue
                    max_count = max(max_count, min_count)
                    seen[s_i][s_j] = 0

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def dfs(MAZE, goal, current, seen, H, W, min_count = INF):
    y, x, count = current
    #print(x,y,count)
    if count > min_count:
        return min_count
    if (y,x) == goal:
        min_count = min(min_count, count)
    else:
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y+i, x+j
            if 1 <= next_x <= W and 1 <= next_y <= H and not seen[next_y][next_x] and MAZE[next_y][next_x] == '.':
                seen[next_y][next_x] = 1
                min_count = min(dfs(MAZE, goal, (next_y, next_x, count+1), seen, H, W, min_count), min_count)
                seen[next_y][next_x] = 0
    return min_count

def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    seen = [[0] * (W+2) for i in range(H+1)]

    max_count = 0
    for s_i in range(1, H+1):
        for s_j in range(1, W+1):
            for g_i in range(1, H + 1):
                for g_j in range(1, W + 1):
                    if s_i == g_i and s_j == g_j:continue
                    seen[s_i][s_j] = 1
                    min_count = dfs(MAZE, (g_i, g_j), (s_i, s_j, 0), seen, H, W)
                    #print((s_i, s_j), '->', (g_i, g_j))
                    #print(min_count)
                    if min_count == INF:
                        continue
                    max_count = max(max_count, min_count)
                    seen[s_i][s_j] = 0

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
g = []
for _ in range(h):
    S = input()
    tmp = [str(i) for i in S]
    g.append(tmp)
from collections import deque
# print(g)
dp = [[0]*w for _ in range(h)]
def dfs(i,j):
    seen = [[False]*w for _ in range(h)]
    seen[i][j] = True
    q = deque([])
    q.append((i,j,0))
    dist=[(1,0),(-1,0),(0,1),(0,-1)]
    while q:
        x,y,cnt = q.popleft()
        for dx,dy in dist:
            if 0 <=x+dx<h and 0<=y+dy<w and seen[x+dx][y+dy]==False and g[x+dx][y+dy]=='.':
                seen[x+dx][y+dy] = True
                q.append((x+dx,y+dy,cnt+1))
    return cnt
ans = 0
for i in range(h):
    for j in range(w):
        ans =max(ans,dfs(i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

def bfs(u):
    stack = deque([u])
    visited = set()
    seen = set()
    p = [[INF for j in range(W)] for i in range(H)]
    p[u[0]][u[1]] = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                p[i][j] = -1

    while len(stack) > 0:
        v = stack.popleft()
        ###
        visited.add(v)
        ###

        a = (v[0] + 1, v[1])
        b = (v[0]    , v[1] + 1)
        c = (v[0] - 1, v[1])
        d = (v[0]    , v[1] - 1)

        e = [a, b, c, d]

        for ee in e:
            if ee[0] >= 0 and ee[0] <= H-1 and ee[1] >= 0 and ee[1] <= W-1:
                if S[ee[0]][ee[1]] == ".":
                    if ee not in visited:
                        p[ee[0]][ee[1]] = min(p[ee[0]][ee[1]], p[v[0]][v[1]] + 1)
                        if ee not in seen:
                            stack.append(ee)
                            seen.add(ee)


    ans = 0
    for i in range(H):
        ans = max(ans, max(p[i]))
    return ans

sol = 0

for i in range(H):
    for j in range(W):
        sol = max(sol, bfs((i,j)))

print(sol)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

def bfs(u):
    stack = deque([u])
    visited = set()
    seen = set()
    p = [[0 for j in range(W)] for i in range(H)]

    while len(stack) > 0:
        v = stack.popleft()
        ###
        visited.add(v)
        ###

        a = (v[0] + 1, v[1])
        b = (v[0]    , v[1] + 1)
        c = (v[0] - 1, v[1])
        d = (v[0]    , v[1] - 1)

        e = [a, b, c, d]

        for ee in e:
            if ee[0] >= 0 and ee[0] <= H-1 and ee[1] >= 0 and ee[1] <= W-1:
                if S[ee[0]][ee[1]] == ".":
                    if ee not in visited:
                        p[ee[0]][ee[1]] = max(p[ee[0]][ee[1]], p[v[0]][v[1]] + 1)
                        if ee not in seen:
                            stack.append(ee)
                            seen.add(ee)


    ans = 0
    for i in range(H):
        ans = max(ans, max(p[i]))
    return ans

sol = 0

for i in range(H):
    for j in range(W):
        sol = max(sol, bfs((i,j)))

print(sol)

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=0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#スタート・ゴール全探索
for i_s in range(H):
    for j_s 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()
            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)の四方みていくよ
                    # print(d[p[0]][p[1]])
                    d[nx][ny] = d[p[0]][p[1]] + 1  #d更新しておくよ
                    out=max(out,d[p[0]][p[1]] + 1)
        # print('d:',*d, sep='\n')
        # print('ゴール',d[i_g][j_g])
# print(out)
print(out)

Submission status: Wrong Answer

Solution code:
print(38)

Submission status: Wrong Answer

Solution code:
print(1)