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:
#!/usr/bin/env python3
def main():
    from collections import deque
    import numpy as np

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

    move = ((0, 1), (0, -1), (1, 0), (-1, 0))
    seen = [[False] * W for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if S[sh][sw] == '#' or seen[sh][sw]:
                continue
            seen[sh][sw] = True
            queue = deque([(sh, sw)])
            distance = np.zeros((H, W), dtype=np.int16)
            while queue:
                h, w = queue.popleft()
                for dh, dw in move:
                    nh = h + dh
                    nw = w + dw
                    if (1
                            and 0 <= nh < H
                            and 0 <= nw < W
                            and S[nh][nw] == '.'
                            and distance[nh][nw] == 0):
                        distance[nh][nw] = distance[h][w] + 1
                        queue.append((nh, nw))
            ans = max(ans, distance.max())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int,input().split())
maze = [[i for i in input()] for _ in range(h)] # h * w
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def bfs(i, j):
  dist = [[-1] * w for _ in range(h)]
  d = deque()
  d.append((i, j))
  dist[i][j] = 0
  ret = 0
  while d:
    x, y = d.popleft()
    for m in move:
      i = x + m[0]
      j = y + m[1]
      if i >=0 and i < h and j >= 0 and j < w:
        if maze[i][j] == "#":
          continue
        if dist[i][j] != -1:
          continue
        dist[i][j] = dist[x][y] + 1
        d.append((i, j))
  for i in range(h):
    for j in range(w):
      if ret < dist[i][j]:
        ret = dist[i][j]
  return ret

ans = 0
for i in range(h):
  for j in range(w):
    d = bfs(i, j)
    if ans < d:
      ans = d

print(ans)

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int,input().split())
maze = [[i for i in input()] for _ in range(h)] # h * w
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def bfs(i, j):
  dist = [[-1] * w for _ in range(h)]
  d = deque()
  d.append((i, j))
  dist[i][j] = 0
  ret = 0
  while d:
    x, y = d.popleft()
    for m in move:
      i = x + m[0]
      j = y + m[1]
      if i >=0 and i < h and j >= 0 and j < w:
        if maze[i][j] == "#":
          continue
        if dist[i][j] != -1:
          continue
        dist[i][j] = dist[x][y] + 1
        if ret < dist[i][j]:
          ret = dist[i][j]
        d.append((i, j))
  return ret

ans = 0
for i in range(h):
  for j in range(w):
    d = bfs(i, j)
    if ans < d:
      ans = d

print(ans)

Submission status: Wrong Answer

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

for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            startls.append([i,j])
            
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
ans = 0
for start in startls:
    visited = [[0 for i in range(w)] for i in range(h)]
    cost = 0
    queue = [start]
    while len(queue) > 0:
        now = queue.pop(0)
        cost = visited[now[0]][now[1]]+1
        for i in range(4):
            y = now[0]+dy_dx[i][0]
            x = now[1]+dy_dx[i][1]
            if 0 <= y < h and 0 <= x < w:
                if C[y][x] != '#' and visited[y][x] == 0:
                    visited[y][x] = cost
                    queue.append([y,x])
                    ans = max(ans,cost)
print(ans)

Submission status: Wrong Answer

Solution code:
import math , sys

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

di = [(-1,0),(1,0),(0,1),(0,-1)]
def sol(s,g):
    h = s[0] ; w = s[1]
    d = [[math.inf for _ in range(W)] for _ in range(H)]
    cand = []
    dis = 0
    while True:
        for each in di:
            dh , dw = each
            if h + dh>=0 and h + dh<H and w + dw>=0 and w + dw<W and maze[h+dh][w+dw]=="." and d[h+dh][w+dw]>dis+1:
                cand.append((h+dh, w+dw))
                d[h+dh][w+dw] = dis +1
        if len(cand)==0:
            break
        h , w =cand.pop(0)
        dis = d[h][w]
    return d[g[0]][g[1]]

ans = 0

for sh in range(H):
    for sw in range(W):
        for gh in range(H):
            for gw in range(W):
                if maze[sh][sw]=="#" or maze[gh][gw]=="#":
                    continue
                ans = max(ans, sol((sh,sw),(gh,gw)))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d+1
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
maze=[]

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [[999999]*w for _ in range(h)]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                dist[y][x]=d
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h)):
                        if(dist[y+m[1]][x+m[0]] > d+1):
                            if(maze[y+m[1]][x+m[0]] == "."):
                                dq.append((y+m[1],x+m[0],d+1))
                                
            # ans = max(ans,d)
            print(d,i,j)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import *
H,W = map(int,input().split())
S = [(W+2)*["#"]]+[["#"]+list(input())+["#"] for h in range(H)]+[(W+2)*["#"]]
D = [[1,0],[-1,0],[0,1],[0,-1]]
start = []
ans = 0

for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=="." and 2<=(S[h-1][w]+S[h+1][w]+S[h][w-1]+S[h][w+1]).count("#")<=3:
      start+=[[h,w]]

for sx,sy in start:
  T = S[:]
  T[sx-1][sy-1] = 1
  Q = deque([[sx-1,sy-1]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if S[x+dx][y+dy]==".":
        S[x+dx][y+dy] = S[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,S[x+dx][y+dy])

print(ans)

Submission status: Wrong Answer

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

direction = [
    (0, 1),
    (1, 0),
    (-1, 0),
    (0, -1)
]


def bfs(sy, sx):
    reached = [[-1] * W for _ in range(H)]
    reached[sy][sx] = 0
    from collections import deque
    que = deque([[sy, sx]])
    d_max = 0
    while que:
        iy, ix = que.popleft()
        for d in direction:
            tx, ty = ix + d[0], iy + d[1]
            if tx >= W or ty >= H or tx < 0 or ty < 0:
                continue
            if reached[ty][tx] != -1 or maze[ty][tx] == '#':
                continue
            reached[ty][tx] = reached[iy][ix] + 1
            d_max = max(reached[ty][tx], d_max)
            que.append([ty, tx])

    return d_max


ans = 0

for i in range(H):
    for j in range(i, W):
        if maze[i][j] == '.':
            ans = max(ans, bfs(i, j))

# for i in range(H):
#     for j in range(i, W):
#         for k in range(H):
#             for l in range(k, W):
#                 if maze[i][j] == '#' or maze[k][l] == '#':
#                     continue
#                 else:
#                     ans = max(ans, bfs(i, j, k, l))
print(ans)

Submission status: Wrong Answer

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    mod=10**9+7
    H,W=MI()
    S=[]
    S.append("#"*(W+2))
    for i in range(H):
        s="#"+input()+"#"
        S.append(s)
    S.append("#"*(W+2))
    
    djk=Dijkstra((H+2)*(W+2))
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    for i in range(1,H+1):
        for j in range(1,W+1):
            if S[i][j]==".":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]==".":
                        v= (W+2)*i + j
                        nv=(W+2)*ii+jj
                        djk.add2(v,nv,1)
                        
    ans=0
    for i in range((H+2)*(W+2)):
        d=djk.shortest_path(i)
        for di in d:
            if di<=100:
                ans=max(ans,di)
                
    print(ans)
            
            
    


main()

Submission status: Wrong Answer

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

def bfs(maze, sy, sx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        ans=0
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
                    
    for l in range(H):
        for m in range(W):
            ans = max(ans,visited[l][m])
            
            return ans
        
ma=0
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == ".":
            if bfs(maze,sy,sx) is not None:
                ma = max(bfs(maze, sy, sx),ma)
print(ma)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [input() for i in range(H)]
def bfs(maze, sy, sx, gy, gx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
ma=0
for sy in range(H):
    for sx in range(W):
        gy=H-sy-1
        gx=W-sx-1
        if maze[sy][sx] == "." and maze[gy][gx] == "." and bfs(maze,sy,sx,gy,gx) is not None:
            ma = max(bfs(maze, sy, sx, gy, gx),ma)
print(ma)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [input() for i in range(H)]
def bfs(maze, sy, sx, gy, gx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
ma=0
for sy in range(H):
    for sx in range(W):
        gy=H-sy-1
        gx=W-sx-1
        if bfs(maze,sy,sx,gy,gx) is not None:
            ma = max(bfs(maze, sy, sx, gy, gx),ma)
print(ma)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [input() for i in range(H)]
def bfs(maze, sy, sx, gy, gx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
ma=0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if bfs(maze,sy,sx,gy,gx) is not None:
                    ma = max(bfs(maze, sy, sx, gy, gx),ma)
print(ma)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1e9)+7
INF = float('inf')


def solve():
    n, m = [int(x) for x in input().split()]
    a = []
    start = None
    for i in range(n):
        a.append(input())
        for j in range(m):
            if a[i][j] == '.':
                start = (i, j)

    def bfs(v):
        q = deque([(v, 0)])
        mx = 0
        mv = v
        w = defaultdict(int)
        w[v] = 1
        while q:
            v, d = q.popleft()
            if d > mx:
                mv = v
                mx = d
            i, j = v
            for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if 0 <= i + x < n and 0 <= j + y < m and not w[(i+x,j+y)] and a[i+x][j+y] == '.':
                    w[(i+x,j+y)] = 1
                    q.append(((i+x, j+y), d + 1))
            

        return mx, mv

    _, start = bfs(start)
    ans, start = bfs(start)
    print(ans)


    

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
1
4
-1 1 1 -1

"""

Submission status: Wrong Answer

Solution code:


#◆◆◆◆◆◆◆◆おそらくpypyで出したほうがいいと思う◆◆◆◆◆◆◆◆


#5 8  #R行C列
#2 2  #スタート地点
#2 4  #ゴール地点

########
#?#????#
#?###??#
#??????#
########
#↑盤面


import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R,C = NMI()
    board = [list(input()) for _ in range(R)]
    
    ans = 0
    
    for r in range(R):
        for c in range(C):
            if board[r][c] == ".":
                
                #座標
                sx = c
                sy = r


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

                #すべての点をINFで初期化
                INF = -1
                distance = [[INF for _ in range(C)] for _ in range(R)]

                #地点を保存するqueを作成、スタート地点を入れる
                que = deque([])
                que.append((sy,sx))

                #スタート地点の距離は0
                distance[sy][sx] = 0

                #queが空になるまでループ
                while len(que) != 0:
                    #取り出してきた状態がゴールなら探索をやめる
                    pop = que.popleft()

                    #移動4方向をループ
                    for i in range(len(dx)):
                        #移動した後の点をny,nxとする
                        ny = pop[0]+dy[i]
                        nx = pop[1]+dx[i]

            #パターン1
                        #nyが0以上R未満   nxが0以上C未満     盤上で壁ではない        まだ訪れたことがない
                        if 0<= ny < R and 0 <= nx < C and board[ny][nx]!='#' and distance[ny][nx] == INF:
                            #つまり移動可能でまだ行ったことがなければqueへ入れる
                            que.append((ny,nx))
                            #その距離をもとのpopの最短距離+1でdistanceに記録
                            distance[ny][nx] = distance[pop[0]][pop[1]]+1
                
                for r in range(R):
                    ans = max(ans,max(distance[r]))
                
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	H, W = [int(x) for x in input().split(" ")]
	S = []
	S.append(["X"] * (W + 2))
	h = 0
	w = 0
	for i in range(H):
		row = list(input())
		S.append(["X"] + row + ["X"])
		if not h and not w and row.count(".") > 0:
			h = i + 1
			w = row.index(".") + 1
	S.append(["X"] * (W + 2))

	m = BFS(S, h, w, H + 2, W + 2)
	tmp = {"row": -1, "col": -1, "max": 0}
	for i in range(len(m)):
		for j in range(len(m[i])):
			if m[i][j] > tmp["max"]:
				tmp["row"] = i
				tmp["col"] = j
				tmp["max"] = m[i][j]
	q = BFS(S, tmp["row"], tmp["col"], H + 2, W + 2)
	ans = []
	for i in range(len(q)):
		ans += q[i]
	print(max(ans))

def BFS(M, i, j, H, W):
	to_visit = [{"row": i, "col": j, "step": 0}]
	checked = [[0] * W for x in range(H)]
	checked[i][j] = 1
	ret = [[0] * W for x in range(H)]
	while len(to_visit):
		visiting = to_visit.pop(0)
		r0 = visiting["row"]
		c0 = visiting["col"]
		s0 = visiting["step"]
		ret[r0][c0] = s0
		for d in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
			r = r0 + d[0]
			c = c0 + d[1]
			s = s0 + 1
			if checked[r][c] == 0 and M[r][c] == ".":
				to_visit.append({"row": r, "col": c, "step": s})
				checked[r][c] = 1
	return ret

main()

Submission status: Wrong Answer

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    H,W = i_map()
    dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
    rc=[input() for i in range(H)]
    ans = 0

    for sy in range(H):
        for sx in range(W):
            if rc[sy][sx] == "#":
                break
            dist=[[-1 for _ in range(W)] for _ in range(H)]
            dist[sy][sx] = 0
            d=deque()
            d.append([sx,sy])
            while d:
                nx, ny = d.popleft()
                for dy,dx in dy_dx:
                    y,x = ny+dy,nx+dx
                    if 0<=y<H and 0<=x<W and rc[y][x] != "#" and dist[y][x] == -1:
                        dist[y][x] = dist[ny][nx] + 1
                        d.append([x,y])
            ans = max(ans, max(list(itertools.chain.from_iterable(dist))))
    print(ans)


if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    H,W = i_map()
    dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
    rc=[input() for i in range(H)]

    ans = 0

    for sy in range(H):
        for sx in range(W):
            dist=[[-1 for _ in range(W)] for _ in range(H)]
            dist[sy][sx] = 0
            d=deque()
            d.append([sx,sy])
            while d:
                nx, ny = d.popleft()
                for dy,dx in dy_dx:
                    y,x = ny+dy,nx+dx
                    if 0<=y<H and 0<=x<W and rc[y][x] != "#" and dist[y][x] == -1:
                        dist[y][x] = dist[ny][nx] + 1
                        d.append([x,y])
            ans = max(ans, max(list(itertools.chain.from_iterable(dist))))
    print(ans)





if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

flag = False
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            th, tw = i, j
            flag = True
            break
    if flag:
        break

dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
c = [[0]*w for _ in range(h)]
q = deque()
q.append((th, tw, 0))
start = 0
while q:
    ph, pw, k = q.pop()
    if c[ph][pw] == 0:
        if k >= start:
            sh, sw = ph, pw
        c[ph][pw] = 1
        for dh, dw in dire:
            hdh, wdw = ph+dh, pw+dw
            if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                if s[hdh][wdw] == '.':
                    q.appendleft((hdh, wdw, k+1))

c = [[0]*w for _ in range(h)]
q.append((sh, sw, 0))
ans = 0
while q:
    ph, pw, k = q.pop()
    if c[ph][pw] == 0:
        ans = max(ans, k)
        c[ph][pw] = 1
        for dh, dw in dire:
            hdh, wdw = ph+dh, pw+dw
            if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                if s[hdh][wdw] == '.':
                    q.appendleft((hdh, wdw, k+1))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

flag = False
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            th, tw = i, j
            flag = True
            break
    if flag:
        break

dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
c = [[0]*w for _ in range(h)]
q = deque()
q.append((th, tw, 0))
start = 0
while q:
    ph, pw, k = q.pop()
    if k >= start:
        sh, sw = ph, pw
    if c[ph][pw] == 0:
        c[ph][pw] = 1
        for dh, dw in dire:
            hdh, wdw = ph+dh, pw+dw
            if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                if s[hdh][wdw] == '.':
                    q.appendleft((hdh, wdw, k+1))

c = [[0]*w for _ in range(h)]
q.append((sh, sw, 0))
ans = 0
while q:
    ph, pw, k = q.pop()
    ans = max(ans, k)
    if c[ph][pw] == 0:
        c[ph][pw] = 1
        for dh, dw in dire:
            hdh, wdw = ph+dh, pw+dw
            if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                if s[hdh][wdw] == '.':
                    q.appendleft((hdh, wdw, k+1))

print(ans)

Submission status: Wrong Answer

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

def bfs(start):
    already = {}
    queue = []
    counter = 0
    queue.append((start[0], start[1], 0))
    max_depth = 0
    while counter < len(queue):
        y, x, depth = queue[counter]
        if depth > max_depth:
            max_depth = depth
        for move in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            new_y = y + move[0]
            new_x = x + move[1]
            if new_y >= 0 \
            and new_y < H \
            and new_x >= 0 \
            and new_x < W \
            and S[new_y][new_x] == '.' \
            and (new_y, new_x) not in already:
                already[(new_y, new_x)] = True
                queue.append((new_y, new_x, depth+1))
        counter += 1
    return max_depth

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        depth = bfs((i, j))
        if answer < depth:
            answer = depth
print(answer)

Submission status: Wrong Answer

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

def bfs(start):
    already = {}
    queue = []
    counter = 0
    queue.append((start[0], start[1], 0))
    max_depth = 0
    while counter < len(queue):
        y, x, depth = queue[counter]
        if depth > max_depth:
            max_depth = depth
        for move in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            new_y = y + move[0]
            new_x = x + move[1]
            if new_y >= 0 \
            and new_y < H \
            and new_x >= 0 \
            and new_x < W \
            and S[new_y][new_x] == '.' \
            and (new_y, new_x) not in already:
                already[(new_y, new_x)] = True
                queue.append((new_y, new_x, depth+1))
        counter += 1
    return max_depth

answer = 0
for i in range(H):
    for j in range(W):
        depth = bfs((i, j))
        if answer < depth:
            answer = depth
print(answer)