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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w = LI()
    a = [[c=='#' for c in S()] for _ in range(h)]
    s = (-1,-1)
    for i in range(h):
        for j in range(w):
            if not a[i][j]:
                s = (i,j)

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for di,dj in dd:
                ni = u[0] + di
                nj = u[1] + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w or a[ni][nj]:
                    continue
                uv = (ni,nj)
                if v[uv]:
                    continue
                vd = k + 1
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d = search(s)
    m = -1
    ms = (-1,-1)
    for k,v in d.items():
        if v > m:
            m = v
            ms = k
    e = search(ms)

    return max(e.values())


print(main())

Submission status: Wrong Answer

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

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for s_x, s_y in  [(i, j) for i in range(h) for j in range(w)]:
    if g[s_x][s_y] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = (-1, -1)
    cur = (s_x, s_y)
    cnt = 0
    queue = deque([(cur, pre, cnt)])
    queue_pop = queue.pop
    queue_append = queue.append
    while queue:
        cur, pre, cnt = queue_pop()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        dp_cnt = dp[c_x][c_y]
        if not dp_cnt or dp_cnt > cnt:
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = (cur[0] + x, cur[1] + y)
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue_append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
P=[[s for s in input()] for _ in range(N)]
Maze = np.zeros((N,M))
Ans = np.zeros((N,M))
List = np.zeros((N,M))
Plus = np.zeros((N,M))

for x in range(N):
    for y in range(M):
        if P[x][y]=='#':
            Maze[x][y]=-1
            List[x][y]=-1

for i in range(N):
    for j in range(M):
        if Maze[i][j]==0:
            List = np.zeros((N,M))
            List[i][j]=1
            for k in range(N*M):
                count =0
                Plus = np.zeros((N,M))
                for a in range(N):
                    for b in range(M):
                        if List[a][b]==k+1 and Maze[a][b]==0:
                            if a-1 >=0 and List[a-1][b]==0 and Maze[a-1][b]==0:
                                Plus[a-1][b]=k+2
                            if b-1 >=0 and List[a][b-1]==0 and Maze[a][b-1]==0:
                                Plus[a][b-1]=k+2
                            if a+1 <N and List[a+1][b]==0 and Maze[a+1][b]==0:
                                Plus[a+1][b]=k+2
                            if b+1 <M and List[a][b+1]==0 and Maze[a][b+1]==0:
                                Plus[a][b+1]=k+2
                List = List+Plus

        Ans[i][j]=np.amax(List)
print(np.amax(Ans)-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
#P = [input().split() for i in range(N)]
P=[[s for s in input()] for _ in range(N)]
print(P)
Maze = np.zeros((N,M))
Ans = np.zeros((N,M))
List = np.zeros((N,M))
Plus = np.zeros((N,M))

for x in range(N):
    for y in range(M):
        if P[x][y]=='#':
            Maze[x][y]=-1
            List[x][y]=-1

for i in range(N):
    for j in range(M):
        if Maze[i][j]==0:
            List = np.zeros((N,M))
            List[i][j]=1
            for k in range(N*M):
                count =0
                Plus = np.zeros((N,M))
                for a in range(N):
                    for b in range(M):
                        if List[a][b]==k+1 and Maze[a][b]==0:
                            if a-1 >=0 and List[a-1][b]==0 and Maze[a-1][b]==0:
                                print("A")
                                Plus[a-1][b]=k+2
                                count = count+1
                            if b-1 >=0 and List[a][b-1]==0 and Maze[a][b-1]==0:
                                print("B")
                                Plus[a][b-1]=k+2
                                count= count+1
                            if a+1 <N and List[a+1][b]==0 and Maze[a+1][b]==0:
                                print("C")
                                Plus[a+1][b]=k+2
                                count= count+1
                            if b+1 <M and List[a][b+1]==0 and Maze[a][b+1]==0:
                                print("D")
                                Plus[a][b+1]=k+2
                                count= count+1
                List = List+Plus
                print(List)
                print(count)

        Ans[i][j]=np.amax(List)
print(Ans)
print(np.amax(Ans)-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

H, W = list(map(int, input().split()))

tbl = np.zeros([H, W], dtype=np.uint8)
for col in tbl:
	x = input().replace('.', '1').replace('#', '0')
	col[:] = list(x)

def func(start, goal):
    dp = np.ones([H, W]) * np.inf
    data = tbl.copy()
    data[start[0], start[1]] = 0
    dp[start[0], start[1]] = 0

    que = [start]

    flag = False
    def move(i, j, m, n):
        if m<0 or n<0 or m>=H or n>=W:
            return

        if data[m, n] == 1:
            data[m, n] = 0
            dp[m, n] = min(dp[i, j] + 1, dp[m, n])
            if [m, n] != goal:
                que.append([m, n])
            else:
                flag = True

    while len(que) > 0:
        i, j = que.pop(0)
        move(i,j,i-1,j)
        move(i,j,i+1,j)
        move(i,j,i,j-1)
        move(i,j,i,j+1)
        if flag:
            break
       
    return dp[goal[0], goal[1]]

ans = 0
all_data = [i for i in range(H*W)]
for start, goal in itertools.combinations(all_data, 2):
    start = [start%H, start//H]
    goal = [goal%H, goal//H]
    if tbl[start[0], start[1]] == 0 or tbl[goal[0], goal[1]] == 0:
        continue
    
    num = func(start, goal)    
    if num != np.inf:
    	ans = max(ans, num)
    	if ans == H + W - 2:
    		break

if ans == np.inf:
	ans = 0
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

H, W = list(map(int, input().split()))

tbl = np.zeros([H, W], dtype=np.uint8)
for col in tbl:
	x = input().replace('.', '1').replace('#', '0')
	col[:] = list(x)

def func(start, goal):
    dp = np.ones([H, W]) * np.inf
    data = tbl.copy()
    data[start[0], start[1]] = 0
    dp[start[0], start[1]] = 0

    que = [start]

    def move(i, j, m, n):
        if m<0 or n<0 or m>=H or n>=W:
            return

        if data[m, n] == 1:
            data[m, n] = 0
            dp[m, n] = min(dp[i, j] + 1, dp[m, n])
            if [m, n] != goal:
                que.append([m, n])

    while len(que) > 0:
        i, j = que.pop(0)
        move(i,j,i-1,j)
        move(i,j,i+1,j)
        move(i,j,i,j-1)
        move(i,j,i,j+1)
       
    return dp[goal[0], goal[1]]

ans = 0
all_data = [i for i in range(H*W)]
for start, goal in itertools.combinations(all_data, 2):
    start = [start%H, start//H]
    goal = [goal%H, goal//H]
    if tbl[start[0], start[1]] == 0 or tbl[goal[0], goal[1]] == 0:
        continue
    
    num = func(start, goal)    
    if num != np.inf:
    	ans = max(ans, num)
    if ans == H + W - 2:
      	break
      
print(int(ans))

Submission status: Wrong Answer

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

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for start in  [[i, j] for i in range(h) for j in range(w)]:
    if g[start[0]][start[1]] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = [-1, -1]
    cur = start
    cnt = 0
    queue = deque([[cur, pre, cnt]])
    while queue:
        cur, pre, cnt = queue.popleft()
        c_x, c_y = cur
        if not dp[c_x][c_y] or (dp[c_x][c_y] and dp[c_x][c_y] > cnt):
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = [cur[0] + x, cur[1] + y]
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue.append([next, cur, cnt + 1])

    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())

#start位置を受け取り
def bfs(width, height ,ar):
  print(width,height)

#main処理
ar = []
for i in range(h):
  ar.append(list(input()))
print(ar)

for width in range(w):
  for height in range(h):
    bfs(width, height, ar)

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
s=[None]*h*w
for i in range(h*w):
    s[i]=[int(1e6)]*h*w
for i in range(h):
    l=input()
    for j,x in enumerate(l):
        if x == '#':
            continue
        pos=w*i+j
        s[pos][pos]=0
        if pos % w != 0:
            s[pos][pos-1]=1
            s[pos-1][pos]=1
        if 0 <= pos-w:
            s[pos][pos-w]=1
            s[pos-w][pos]=1
for k in range(h*w):
    for i in range(h*w):
        for j in range(h*w):
            s[i][j] = min(s[i][j], s[i][k] + s[k][j])
m = 0
for x in s:
    m = max(m, max(x))
print(m)

Submission status: Wrong Answer

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

def debug_print(maze):
    for xx in maze:
        for yy in xx:
            print(yy,end='')
        print ("")


def clear_maze(sx, sy, gx, gy, maze):


    INF = 100000000

    distance = [[INF for i in range(W)] for j in range(H)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx and nx < H and 0 <= ny and ny < W:
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.insert(0, (nx, ny))
                        distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()

print(clear_maze(H-1, 0, 0, W-1, maze))

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w = (int(x) for x in input().split())
a = np.arange(h)

for i in range(h):
  for x in input().split():
    np.append(a, x)

print(a)

Submission status: Wrong Answer

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

def route(l):
  routeout = []
  if l[0] > 0:
    if sc[l[1]][l[0]-1] == '.':
      routeout.append([l[0]-1, l[1]])
  if l[0] < w-1:
    if sc[l[1]][l[0]+1] == '.':
      routeout.append([l[0]+1, l[1]])
  if l[1] > 0:
    if sc[l[1]-1][l[0]] == '.':
      routeout.append([l[0], l[1]-1])
  if l[1] < h-1:
    if sc[l[1]+1][l[0]] == '.':
      routeout.append([l[0], l[1]+1])
  return routeout

def f(linl, out):
  nextxy = []
  for l in linl:
    nextxy += route(l)
    for ll in route(l):
      sc[ll[1]][ll[0]] = '#'
  if len(nextxy)>0:
    return f(nextxy, out+1)
  else:
    return out
  
r = set()
for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      sc = [[l for l in ll] for ll in s]
      sc[i][j] = '#'
      r.add(f([[j, i]], 0))
print(r)
print(max(r))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ar = []
for i in range(n):
    ar.append(list(input()))

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


res  = 0

for i in range(n):
    for j in range(m):
        if ar[i][j] == '.':
            vis = [[-1] * m for k in range(n)]
            queue = [i, j]
            vis[i][j] = 0
            while len(queue):
                x = queue.pop(0)
                y = queue.pop(0)
                for k in range(4):
                    x1 = x + dx[k]
                    y1 = y + dy[k]
                    if 0 <= x1 < n and 0 <= y1 < m and ar[x1][y1] == '.' and vis[x1][y1] == -1:
                        vis[x1][y1] = vis[x][y] + 1
                        res = max(res, vis[x1][y1])
                        queue.append(x1)
                        queue.append(y1)

print(res)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ar = []
for i in range(n):
    ar.append(list(input()))

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


def recursion(x, y, vis):
    ans = 0
    for k in range(4):
        x1 = x + dx[k]
        y1 = y + dy[k]

        if 0 <= x1 < n and 0 <= y1 < m and ar[x1][y1] == '.' and vis[x1][y1] == 0:
            vis[x1][y1] = 1
            ans = max(ans, 1 + recursion(x1, y1, vis))
    return ans


res = 0
for i in range(n):
    for j in range(m):
        if ar[i][j] == '.':
            vis = [[0] * m for k in range(n)]
            res = max(res, recursion(i, j, vis))

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  ma=-1
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    if d[u[0],u[1]]>ma:
      ma=d[u[0],u[1]]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  return ma
        
def main():
  ma=-1
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)-1
        c=deepcopy(color)
        ma=max(BFS((sx,sy),c,d),ma)
  print(ma)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  ma=0
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    if d[u[0],u[1]]>ma:
      ma=d[u[0],u[1]]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  return ma
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        ma=max(BFS((sx,sy),c,d),ma)
  print(ma)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
        
def main():
  ma=-1
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        BFS((sx,sy),c,d)
        if np.max(d)>ma:
          ma=np.max(d)
  print(ma)
  
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)-1
        c=deepcopy(color)
        BFS((sx,sy),c,d)
        if np.max(d)>ma:
          ma=np.max(d)
  print(ma)
  
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from copy import deepcopy
from queue import Queue
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  Q=Queue()
  Q.put(s)
  while not Q.empty():
    u=Q.get()
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.put(v)
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        BFS((sx,sy),c,d)
        if np.max(d)>ma:
          ma=np.max(d)
  print(ma)
  
main()

Submission status: Wrong Answer

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

# start, goal の候補
reps = []
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            reps.append([i, j])
ans = 0
for k in range(len(reps) - 1):
    for l in range((k + 1), len(reps), 1):
        # unvisited: -1, visited: 0, goal: 1
        start = reps[k]
        goal = reps[l]
        visits = [[-1 for i in range(w)] for j in range(h)]
        visits[goal[0]][goal[1]] = 1
        queue = [reps[k]]
        depth = 0

        while 0 < len(queue):
            # 1. まず、ゴールに到着しているか確認する
            # 2-1. していれば、その start, goal の組における最短経路が計算できたので、depths に追加する
            # 2-2. していなければ、自分のいるマスを訪問済みにし、次に進む道の候補を挙げて、それらを queue に突っ込む
            now = queue.pop(0)

            if visits[now[0]][now[1]] == 1:
                break
            else:
                visits[now[0]][now[1]] = 0
            if (now[0] <= (h - 2)):
                if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                    queue.append([(now[0] + 1), now[1]])
            if (now[1] <= (w - 2)):
                if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                    queue.append([now[0], (now[1] + 1)])
            if (1 <= now[0]):
                if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                    queue.append([(now[0] - 1), now[1]])
            if (1 <= now[1]):
                if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                    queue.append([now[0], (now[1] - 1)])
            depth += 1
        if ans <= depth:
            ans = depth
print(ans)

Submission status: Wrong Answer

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

reps = []
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            reps.append([i, j])
ans = 0
for k in range(len(reps) - 1):
    for l in range((k + 1), len(reps), 1):
        start = reps[k]
        goal = reps[l]
        visits = [[-1 for i in range(w)] for j in range(h)]
        visits[goal[0]][goal[1]] = 1
        queue = [reps[k]]
        depth = 0

        while 0 < len(queue):
            now = queue.pop(0)

            if visits[now[0]][now[1]] == 1:
                break
            else:
                visits[now[0]][now[1]] = 0
            if (now[0] <= (h - 2)):
                if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                    queue.append([(now[0] + 1), now[1]])
            if (now[1] <= (w - 2)):
                if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                    queue.append([now[0], (now[1] + 1)])
            if (1 <= now[0]):
                if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                    queue.append([(now[0] - 1), now[1]])
            if (1 <= now[1]):
                if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                    queue.append([now[0], (now[1] - 1)])
            depth += 1
        if ans <= depth:
            ans = depth
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))
s = []
s.append("".join(["#" for i in range(w + 2)]))
for i in range(h):
    s.append("#" + input().strip() + "#")
s.append("".join(["#" for i in range(w + 2)]))

reps = []
for i in range(h + 2):
    for j in range(w + 2):
        if s[i][j] == ".":
            reps.append([i, j])
depths = []
for start in reps:
    for goal in reps:
        visits = [[-1 for i in range(w + 2)] for j in range(h + 2)]
        visits[goal[0]][goal[1]] = 1
        queue = [start]
        depth = 0

        while True:
            flg = False
            tmp_queue = []
            for now in queue:
                if visits[now[0]][now[1]] == 1:
                    clear = True
                    break
                else:
                    visits[now[0]][now[1]] = 0
                if (s[now[0] + 1][now[1]] == ".") and (visits[now[0] + 1][now[1]] != 0):
                    tmp_queue.append([(now[0] + 1), now[1]])
                if (s[now[0]][now[1] + 1] == ".") and (visits[now[0]][now[1] + 1] != 0):
                    tmp_queue.append([now[0], (now[1] + 1)])
                if (s[now[0] - 1][now[1]] == ".") and (visits[now[0] - 1][now[1]] != 0):
                    tmp_queue.append([(now[0] - 1), now[1]])
                if (s[now[0]][now[1] - 1] == ".") and (visits[now[0]][now[1] - 1] != 0):
                    tmp_queue.append([now[0], (now[1] - 1)])
            if clear:
                break
            else:
                depth += 1
                queue = tmp_queue
        depths.append(depth)
print(max(depths))

Submission status: Wrong Answer

Solution code:
from queue import Queue

def bfs(HW, q):
    num = 0
    mem = [[0]*(W+1) for i in range(H+1)]
    max_dist = 0
    while not q.empty():
        current = q.get()
        if current[0] >= H or current[0] < 0 or current[1] >= W or current[1] < 0:
            continue
        if HW[current[0]][current[1]] == '#':
            continue

        dist = mem[current[0]][current[1]]
        max_dist = max(max_dist, dist)
        if mem[current[0]+1][current[1]] == 0:
            mem[current[0]+1][current[1]] = dist+1
            q.put([current[0]+1,current[1]])
        if mem[current[0]][current[1]+1] == 0:
            mem[current[0]][current[1]+1] = dist+1
            q.put([current[0],current[1]+1])
        if mem[current[0]-1][current[1]] == 0:
            mem[current[0]-1][current[1]] = dist+1
            q.put([current[0]-1,current[1]])
        if mem[current[0]][current[1]-1] == 0:
            mem[current[0]][current[1]-1] = dist+1
            q.put([current[0],current[1]-1])
    return max_dist


H,W = map(int, input().split())

HW = [[''] * W for i in range(H)]
for i in range(H):
    h = str(input())
    HW[i] = h

ans = 0
for si in range(H):
    for sj in range(W):
        if HW[si][sj] == '#':
            continue
        q = Queue()
        q.put([si,sj,0])
        ans = max(ans, bfs(HW, q))
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue

def bfs(HW, q):
    num = 0
    mem = [[0]*(W+1) for i in range(H+1)]
    max_dist = 0
    while not q.empty():
        current = q.get()
        if current[0] >= H or current[0] < 0 or current[1] >= W or current[1] < 0:
            continue
        if HW[current[0]][current[1]] == '#':
            continue

        dist = mem[current[0]][current[1]]
        max_dist = max(max_dist, dist)
        dist += 1
        if mem[current[0]+1][current[1]] == 0:
            mem[current[0]+1][current[1]] = dist
            q.put([current[0]+1,current[1]])
        if mem[current[0]][current[1]+1] == 0:
            mem[current[0]][current[1]+1] = dist
            q.put([current[0],current[1]+1])
        if mem[current[0]-1][current[1]] == 0:
            mem[current[0]-1][current[1]] = dist
            q.put([current[0]-1,current[1]])
        if mem[current[0]][current[1]-1] == 0:
            mem[current[0]][current[1]-1] = dist
            q.put([current[0],current[1]-1])
    return max_dist


H,W = map(int, input().split())

HW = [[''] * W for i in range(H)]
for i in range(H):
    h = str(input())
    HW[i] = h

ans = 0
for si in range(H):
    for sj in range(W):
        if HW[si][sj] == '#':
            continue
        q = Queue()
        q.put([si,sj,0])
        ans = max(ans, bfs(HW, q))
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue

def bfs(HW, q):
    num = 0
    mem = [[0]*(W+1) for i in range(H+1)]
    max_dist = 0
    while not q.empty():
        current = q.get()
        if current[0] >= H or current[0] < 0 or current[1] >= W or current[1] < 0:
            continue
        if HW[current[0]][current[1]] == '#':
            continue

        dist = mem[current[0]][current[1]]+1
        if mem[current[0]+1][current[1]] == 0:
            mem[current[0]+1][current[1]] = dist
            q.put([current[0]+1,current[1]])
            max_dist = max(max_dist, dist)
        if mem[current[0]][current[1]+1] == 0:
            mem[current[0]][current[1]+1] = dist
            q.put([current[0],current[1]+1])
            max_dist = max(max_dist, dist)
        if mem[current[0]-1][current[1]] == 0:
            mem[current[0]-1][current[1]] = dist
            q.put([current[0]-1,current[1]])
            max_dist = max(max_dist, dist)
        if mem[current[0]][current[1]-1] == 0:
            mem[current[0]][current[1]-1] = dist
            q.put([current[0],current[1]-1])
            max_dist = max(max_dist, dist)
    return max_dist


H,W = map(int, input().split())

HW = [[''] * W for i in range(H)]
for i in range(H):
    h = str(input())
    HW[i] = h

ans = 0
for si in range(H):
    for sj in range(W):
        if HW[si][sj] == '#':
            continue
        q = Queue()
        q.put([si,sj,0])
        ans = max(ans, bfs(HW, q))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

def resolve():
    H, W = map(int, input().split())

    maze = []
    for i in range(H):
        maze.append(input())

    def bfs(st):

        INF = -1
        d = np.full((H, W), INF)

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

        que = deque()
        que.append(st)
        d[st[1]][st[0]] = 0

        while len(que):
            p = que.popleft()
            # print(p)

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

                if nx >= 0 and nx < W and ny >= 0 and ny < H and maze[ny][nx] != "#" and d[ny][nx] == INF:
                    # print("next is ", nx, ny)
                    que.append([nx, ny])
                    d[ny][nx] = d[p[1]][p[0]] + 1
                    # print(d)
                    # print(que)

        cost = np.max(d)
        # idx = np.unravel_index(np.argmax(d), d.shape)
        # print(idx)
        # print(cost)
        return cost

    max_cost = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == '.':
                st = [x, y]
                cost = bfs(st)
                if cost > max_cost:
                    max_cost = cost 
        break
    
    # print(maze[1])
    # idx, cost = bfs(st)
    # idx, cost = bfs((idx[1], idx[0]))
    print(int(max_cost))

if __name__ == "__main__":
    resolve()