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
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

h,w = get_nums_l()

grid_s = [ input() for _ in range(h) ]
grid = [ [-1] * (w+2) for _ in range(h+2) ]

log(grid_s)

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid_s[y-1][x-1] == ".":
            grid[y][x] = 999999999999999999

start_x = 1
start_y = 1
while grid[start_y][start_x] == -1:
    start_x += 1
    if start_x > w:
        start_x = 1
        start_y += 1

grid[start_y][start_x] = 0

que = deque()
que.append((start_x, start_y, 1))

while que:
    x,y,score = que.popleft()

    for nx,ny in neighbors4(x,y):
        if grid[ny][nx] != -1 and grid[ny][nx] > score:
            grid[ny][nx] = score
            que.append((nx, ny, score+1))

max_ = 0
max_x = -1
max_y = -1

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid[y][x] > max_:
            max_ = grid[y][x]
            max_x = x
            max_y = y

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid_s[y-1][x-1] == ".":
            grid[y][x] = 999999999999999999

que = deque()
que.append((max_x, max_y, 1))


grid[max_y][max_x] = 0

while que:
    x,y,score = que.popleft()

    for nx,ny in neighbors4(x,y):
        if grid[ny][nx] != -1 and grid[ny][nx] > score:
            grid[ny][nx] = score
            que.append((nx, ny, score+1))

max_ = 0
max_x = -1
max_y = -1

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid[y][x] > max_:
            max_ = grid[y][x]
            max_x = x
            max_y = y

for g in grid:
    log(g)

print(max_)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

h,w = get_nums_l()

grid_s = [ input() for _ in range(h) ]
grid = [ [-1] * (w+2) for _ in range(h+2) ]

log(grid_s)

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid_s[y-1][x-1] == ".":
            grid[y][x] = 999999999999999999

start_x = 1
start_y = 1
while grid[start_y][start_x] == -1:
    start_x += 1
    if start_x > w:
        start_x = 1
        start_y += 1

grid[start_y][start_x] = 0

que = deque()
que.append((start_x, start_y, 1))

while que:
    x,y,score = que.popleft()

    for nx,ny in neighbors4(x,y):
        if grid[ny][nx] != -1 and grid[ny][nx] > score:
            grid[ny][nx] = score
            que.append((nx, ny, score+1))

max_ = 0
max_x = -1
max_y = -1

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid[y][x] > max_:
            max_ = grid[y][x]
            max_x = x
            max_y = y

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid_s[y-1][x-1] == ".":
            grid[y][x] = 999999999999999999

que = deque()
que.append((max_x, max_y, 1))

while que:
    x,y,score = que.popleft()

    for nx,ny in neighbors4(x,y):
        if grid[ny][nx] != -1 and grid[ny][nx] > score:
            grid[ny][nx] = score
            que.append((nx, ny, score+1))

max_ = 0
max_x = -1
max_y = -1

for y in range(1,h+1):
    for x in range(1, w+1):
        if grid[y][x] > max_:
            max_ = grid[y][x]
            max_x = x
            max_y = y

print(max_)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(S,H,W,sh,sw):
    dist=[[-1]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    lo=0
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(dist[nh][nw]!=-1 or S[nh][nw]=='#'):
                continue
            dist[nh][nw]=dist[h][w]+1
            lo=max(lo,dist[nh][nw])
            S[nh][nw]=='#'
            d.append([nh,nw])
    return lo

H,W=map(int,input().split())
S=[input() for i in range(H)]
ans=-1
for i in range(H):
    for j in range(W):
        ans=max(ans,bfs(S,H,W,i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(S,H,W,sh,sw):
    dist=[[-1]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    lo=0
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(dist[nh][nw]!=-1 or S[nh][nw]=='#'):
                continue
            dist[nh][nw]=dist[h][w]+1
            lo=dist[nh][nw]
            S[nh][nw]=='#'
            d.append([nh,nw])
    return lo

H,W=map(int,input().split())
S=[input() for i in range(H)]
ans=-1
for i in range(H):
    for j in range(W):
        ans=max(ans,bfs(S,H,W,i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(S,H,W,sh,sw):
    dist=[[-1]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(dist[nh][nw]!=-1 or S[nh][nw]=='#'):
                continue
            dist[nh][nw]=dist[h][w]+1
            d.append([nh,nw])
    return dist
    

H,W=map(int,input().split())
S=[input() for i in range(H)]
dis=bfs(S,H,W,0,0)
up=-2
for i in range(H):
    for j in range(W):
        up=max(up,dis[i][j])
        if(up==dis[i][j]):
            tx=i
            ty=j
dis2=bfs(S,H,W,tx,ty)
ans=-2
for i in range(H):
    for j in range(W):
        ans=max(ans,dis2[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
maze = [input() for _ in range(h)]
check = [[-1]*w for _ in range(h)]

def BFS(maze,check,si,sj):
    queue = deque([[si,sj]])
    check[si][sj] = 0
    while queue:
        x,y = queue.popleft()
        for k,l in ([0,1], [0,-1], [1,0], [-1,0]):
            i2, j2= x+k, y+l
            if i2<0 or i2>=h or j2<0 or j2>=w:
                continue
            if maze[i2][j2] == '.' and check[i2][j2] == -1:
                check[i2][j2] = check[x][y] + 1
                queue.append([i2,j2])
    return max(max(check))

ans = 0
for i in range(h):
    for j in range(w):
        check = [[-1]*w for _ in range(h)]
        if maze[i][j] == '.':
            si , sj = i, j
            ans = max(ans,BFS(maze,check,si,sj))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
S = np.array([['' for i in range(w)] for j in range(h)])
for i in range(h):
  line = input()
  for j in range(w):
    S[i][j] = line[j]
print(S)
  
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

q = deque()

def update(vs, i, j, x, q):
  if vs[i, j] != -1 or S[i, j] == '#':
    return
  vs[i, j] = x
  q.append((i,j,x))

mx = 0
for i, j in product(range(h), range(w)):
  if S[i, j] == '#':
    continue
  vs = np.array([[-1 for i in range(w)] for j in range(h)])
  x = 0
  update(vs, i, j, x , q)
  while len(q) > 0:
    #print(q)
    #print(vs)
    # x += 1
    current_q = q.popleft()
    qi, qj, qx = current_q[0], current_q[1], current_q[2] + 1
    for k in range(4):
      ni, nj = qi + di[k], qj + dj[k]
      if not(0 <= ni < h) or not(0 <= nj < w):
        continue
      update(vs, ni, nj, qx, q)
  mx = max(vs.max(), mx)
print(mx)

Submission status: Wrong Answer

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

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

maze_array = [input().split()[0] for _ in range(H)]

ans = 0
for hh in range(H):
    for ww in range(W):
        flag = [[0 for _ in range(W)] for _ in range(H)]
        queue = deque()
        queue.append((hh,ww,0))
        flag[hh][ww] = 1
        while len(queue):
            h, w, p = queue.popleft()
            # print(h,w,p)
            if w != W - 1 and flag[h][w+1] == 0 and maze_array[h][w+1] == ".":
                flag[h][w+1] = 1
                ans = max(ans,p+1)
                queue.append((h,w+1,p+1))
            if h != H - 1 and flag[h+1][w] == 0 and maze_array[h+1][w] == ".":
                flag[h+1][w] = 1
                ans = max(ans,p+1)
                queue.append((h+1,w,p+1))
            if w != 0 and flag[h][w-1] == 0 and maze_array[h][w-1] == ".":
                flag[h][w-1] = 1
                ans = max(ans,p+1)
                queue.append((h,w-1,p+1))  
            if h != 0 and flag[h-1][w] == 0 and maze_array[h-1][w] == ".":
                flag[h-1][w] = 1
                ans = max(ans,p+1)
                queue.append((h-1,w,p+1))
print(ans)

Submission status: Wrong Answer

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

load=[]
for i in range(0,H):
    for j in range(0,W):
        if S[i][0][j]=='.':
            load.append((i,j))

ans=0
for i,j in load:
    start=(i,j)
    dp=[[500 for i in range(0,W)] for i in range(0,H)]
    dp[i][j]=0
    q=[]
    q.append((i,j))
    sub=[]
    while q!=[]:
        while q!=[]:
            x=q[0]
            q.remove(x)
            s=x[0]
            t=x[1]
            if (s+1,t) in load and dp[s+1][t]>dp[s][t]+1:
                sub.append((s+1,t))
                dp[s+1][t]=dp[s][t]+1
            if (s,t+1) in load and dp[s][t+1]>dp[s][t]+1:
                sub.append((s,t+1))
                dp[s][t+1]=dp[s][t]+1
            if (s-1,t) in load and dp[s-1][t]>dp[s][t]+1:
                sub.append((s-1,t))
                dp[s-1][t]=dp[s][t]+1
            if (s,t-1) in load and dp[s][t-1]>dp[s][t]+1:
                sub.append((s,t-1))
                dp[s][t-1]=dp[s][t]+1
            print(q)
            print(sub)
            if q==[]:
                q=sub
                sub=[]
                break
        print(q)
    test=max(dp[i][j] for i in range(0,H) for j in range(0,W) if (i,j) in load)
    if test>ans:
        ans=test
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
cost_list = [[0]*W for i in range(H)]
cost_check = [[0]*W for i in range(H)]
path_list = [] # path content
max_cost = 0 # max path cost

def path_cost(x, y):
    # cost check clear
    for i in range(H):
        for j in range(W):
            cost_check[i][j] = 0
            cost_list[i][j] = 0
    # cost calculation
    path_queue = [[x,y]]
    cost_check[x][y] = 1
    # path cost process
    while len(path_queue)>0:
        # path queue pop
        path = path_queue.pop(0)
        next_x, next_y = path[0], path[1]
        # right cost process
        if next_x+1<H:
            if path_list[next_x+1][next_y]=="." and cost_check[next_x+1][next_y]==0:
                cost_list[next_x+1][next_y] = max(cost_list[next_x+1][next_y], cost_list[next_x][next_y]+1)
                path_queue.append([next_x+1, next_y])
                cost_check[next_x+1][next_y] = 1

        # bottom cost process
        if next_y+1<W:
            if path_list[next_x][next_y+1]=="." and cost_check[next_x][next_y+1]==0:
                cost_list[next_x][next_y+1] = max(cost_list[next_x][next_y+1], cost_list[next_x][next_y]+1)
                path_queue.append([next_x, next_y+1])
                cost_check[next_x][next_y+1] = 1

        # left cost process
        if next_x-1>=0:
            if path_list[next_x-1][next_y]=="." and cost_check[next_x-1][next_y]==0:
                cost_list[next_x-1][next_y] = max(cost_list[next_x-1][next_y], cost_list[next_x][next_y]+1)
                path_queue.append([next_x-1, next_y])
                cost_check[next_x-1][next_y] = 1

        # up cost process
        if next_y-1>=0:
            if path_list[next_x][next_y-1]=="." and cost_check[next_x][next_y-1]==0:
                cost_list[next_x][next_y-1] = max(cost_list[next_x][next_y-1], cost_list[next_x][next_y]+1)
                path_queue.append([next_x, next_y-1])
                cost_check[next_x][next_y-1] = 1

    tmp_max_cost = max(sum(cost_list,[]))
    return tmp_max_cost

# input path
for i in range(H):
    path_in = input()
    path = []
    for j in range(W):
        path.append(path_in[j])
    path_list.append(path)

# cost calculation
for i in range(H):
    for j in range(W):
        max_cost = max(max_cost,path_cost(i, j))

print(max_cost)

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools

H,W = map(int,input().split())
labyrinth = [[] for i in range(H)]
points = []

for i in range(H):
  w = list(input())
  labyrinth[i] = w
  for j in range(W):
    if w[j] == ".":
      points.append([j,i])

com = list(itertools.combinations(points,2))

#移動パターン
movex = [1,0,-1,0]
movey = [0,1,0,-1]

def shortest_path(sx,sy,labyrinth):
  INF = -(10 ** 6)

  x_length = W
  y_length = H
  distance = [[INF for i in range(x_length)] for j in range(y_length)]
  
  queue = deque()
  queue.append((sx,sy))
  distance[sy][sx] = 0
  
  #幅優先探索
  def bfs():
    #探索候補がある限り
    while len(queue) > 0:
      x,y = queue.popleft()

      #上下左右を探索
      for i in range(0, 4):
        nx = x + movex[i]
        ny = y + movey[i]
        #print(nx,ny)
        #探索迷路内であり
        if (0 <= nx and ny < y_length and 0 <= ny and nx < x_length):
          #通行可能かつ未到達であれば
          if (labyrinth[ny][nx] != "#"  and distance[ny][nx] == INF):
            queue.append((nx,ny))
            distance[ny][nx] = distance[y][x] + 1
    
    return max(max(distance))

  return bfs()

path = []

for i in range(len(points)):
  sx = points[i][0]
  sy = points[i][1]
  dist = shortest_path(sx,sy,labyrinth)
  path.append(dist)
  
print(max(path))

Submission status: Wrong Answer

Solution code:
import queue

H,W=map(int,input().split())
c=["#"*(W+2)]+["#"+input()+"#" for _ in range(H)]+["#"*(W+2)]

ans=0
for i in range(1,H+1):
    for g in range(1,W+1):
        MAX=0
        s=(i,g)
        dist=[[-1]*(W+2) for _ in range(H+2)]
        que=queue.Queue()
        que.put(s)
        dist[s[0]][s[1]]=0

        while not que.empty():
            h,w=que.get()
            direction=[(0,-1),(0,1),(1,0),(-1,0)]
            for y,x in direction:
                if c[h+y][w+x]=="." and dist[h+y][w+x]==-1:
                    que.put((h+y,w+x))
                    dist[h+y][w+x]=dist[h][w]+1
                    MAX=max(MAX,dist[h+y][w+x])
        ans=max(MAX,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

H,W=map(int,input().split())
c=["#"*(W+2)]+["#"+input()+"#" for _ in range(H)]+["#"*(W+2)]

ans=0
for i in range(1,H+1):
    for g in range(1,W+1):
        MAX=0
        s=(i,g)
        dist=[[-1]*(W+2) for _ in range(H+2)]
        que=queue.Queue()
        que.put(s)
        dist[s[0]][s[1]]=0

        while not que.empty():
            h,w=que.get()
            direction=[(0,-1),(0,1),(1,0),(-1,0)]
            for y,x in direction:
                if c[h+y][w+x]=="." and dist[h+y][w+x]==-1:
                    que.put((h+y,w+x))
                    dist[h+y][w+x]=dist[h][w]+1
                    MAX=max(MAX,dist[h+y][w+x])
    ans=max(MAX,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h )]
inf=float("inf")
ans=0
for i in range(h):
    for j in range(w):
        D=[[inf for _ in range(w)]for _ in range(h)]
        D[i][j]=0
        que=deque([(i,j)])
        while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                    if D[ni][nj]>D[si][sj]+1:
                        D[ni][nj]=D[si][sj]+1
                        ans=max(ans,D[si][sj]+1)
                        que.append((ni,nj))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[1][1] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] == "#":
            break
        else:
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque, defaultdict
from functools import lru_cache

h,w=map(lambda x:int(x),input().split())
g=[[0 for j in range(w)] for i in range(h)]
s=set()
for i in range(h):
	x = input()
	for j in range(len(x)):
		if x[j] == '#':
			s.add((i,j))
		g[i][j] = x[j]

tmax=0
for i in range(h):
	for j in range(w):
		if (i,j) in s:
			continue
		vis=set()
		d=deque()
		d.append((i,j,0))
		while d:
			i,j,x=d.popleft()
			for di,dj in [(-1, 0), (1,0), (0,1), (0,-1)]:
				if (i+di,j+dj) in s:
					continue
				if i+di >=h or i+di <0 or j+dj >=w or j+dj <0:
					continue
				if (i+di,j+dj) in vis:
					continue
				vis.add((i+di,j+dj))
				d.append((i+di,j+dj, x+1))
				tmax=max(tmax, x+1)
print(tmax)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque, defaultdict
from functools import lru_cache

h,w=map(lambda x:int(x),input().split())
g=[[0 for j in range(w)] for i in range(h)]
s=set()
for i in range(h):
	x = input()
	for j in range(len(x)):
		if x[j] == '#':
			s.add((i,j))
		g[i][j] = x[j]

tmax=0
for i in range(h):
	for j in range(w):
		if (i,j) in s:
			continue
		vis=set()
		d=deque()
		d.append((i,j,0))
		while d:
			i,j,x=d.popleft()
			tmax=max(tmax, x)
			for di,dj in [(-1, 0), (1,0), (0,1), (0,-1)]:
				if (i+di,j+dj) in s:
					continue
				if i+di >=h or i+di <0 or j+dj >=w or j+dj <0:
					continue
				if (i+di,j+dj) in vis:
					continue
				vis.add((i+di,j+dj))
				d.append((i+di,j+dj, x+1))
print(tmax)

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque, defaultdict
from functools import lru_cache

h,w=map(lambda x:int(x),input().split())
g=[[0 for j in range(w)] for i in range(h)]
s=set()
for i in range(h):
	x = input()
	for j in range(len(x)):
		if x[j] == '#':
			s.add((i,j))
		g[i][j] = x[j]

tmax=0
for i in range(h):
	for j in range(w):
		vis=set()
		d=deque()
		d.append((i,j,0))
		while d:
			i,j,x=d.popleft()
			tmax=max(tmax, x)
			for di,dj in [(-1, 0), (1,0), (0,1), (0,-1)]:
				if (i+di,j+dj) in s:
					continue
				if i+di >=h or i+di <0 or j+dj >=w or j+dj <0:
					continue
				if (i+di,j+dj) in vis:
					continue
				vis.add((i+di,j+dj))
				d.append((i+di,j+dj, x+1))
print(tmax)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

H, W = map(int, input().split())
maps = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps.append(temp)
maps.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps[i][l] == "#":
            break
        else:
            check = [[10 ** 9 for _ in range(W + 2)] for k in range(H + 2)]
            for ab in range(H + 2):
                for bc in range(W + 2):
                    if maps[i][l] == "#":
                        check[i][l] = -1
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                if check[y][x] > depth:
                    check[y][x] = depth

                if maps[y + 1][x] != "#" and check[y + 1][x] > depth + 1:
                    pos.append([y + 1, x, depth + 1])
                    check[y + 1][x] = depth + 1
                if maps[y][x + 1] != "#" and check[y][x + 1] > depth + 1:
                    pos.append([y, x + 1, depth + 1])
                    check[y][x + 1] = depth + 1
                if maps[y - 1][x] != "#" and check[y - 1][x] > depth + 1:
                    pos.append([y - 1, x, depth + 1])
                    check[y - 1][x] = depth + 1
                if maps[y][x - 1] != "#" and check[y][x - 1] > depth + 1:
                    pos.append([y, x - 1, depth + 1])
                    check[y][x - 1] = depth + 1
print(MAX)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

H += 2
W += 2

grid = "#" * W
for _ in range(H - 2):
    grid += "#" + input() + "#"
grid += "#" * W


def bfs(start):
    INF = 10 * 9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            # next place
            w = v + move
            # wall or not
            if grid[w] == "#":
                continue

            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)


answer = max(bfs(v) for v in range(H * W) if grid[v] != "#")
print(answer)

Submission status: Wrong Answer

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

for i in range(w*h):
    mat[i][i] = 0

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] == '#':
            mat[i][next_idx] = 10**18
        else:
            mat[i][next_idx] = 1

for i in range(w*h):
    #print(i,i,i,i,i,i,i,i,i)
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 10**18
tmp = []

for i in range(w*h):
    for j in range(w*h):
        """
        下記4行がないからWA生やした
        """
        if s[i//w][i%w] == '#':
            continue
        if s[j//w][j%w] == '#':
            continue
        ans = max(ans,mat[i][j])
        #if ans > mat[i][j]:
        #    tmp.append(mat[i][j])
            
print(ans)

Submission status: Wrong Answer

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


if __name__ == '__main__':

    # make graph
    maze = []
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

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

    max_path = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] != '#':
                que = deque([[i, j]])
                seen = [[-1 for i in range(W)] for j in range(H)]
                seen[i][j] = 0
                while len(que) != 0:
                    h, w = que[0][0], que[0][1]
                    que.popleft()
                    for k in range(4):
                        if h + dy[k] < 0 or w + dx[k] < 0 or h + dy[k] >= H or w + dx[k] >= W:
                            continue
                        if seen[h + dy[k]][w + dx[k]] != -1 or maze[h + dy[k]][w + dx[k]] == '#':
                            continue
                        seen[h + dy[k]][w + dx[k]] = seen[h][w] + 1
                        que.append([h + dy[k], w + dx[k]])
                if max(max(seen)) > max_path:
                    max_path = max(max(seen))
    print(max_path)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())


def dfs(g, h, w, s, step):

    s[h][w] = step
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    for i in range(4):
        next_h, next_w = h + dy[i], w + dx[i]
        # boundary
        if next_h < 0 or next_w < 0 or next_h >= H or next_w >= W:
            continue
        if g[next_h][next_w] == '#':
            continue
        if s[next_h][next_w] is not False:
            if s[next_h][next_w] <= step + 1:
                continue
        dfs(g, next_h, next_w, s, step + 1)


if __name__ == '__main__':

    # make graph
    maze = []

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

    max_path = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] != '#':
                seen = [[False for i in range(W)] for j in range(H)]
                dfs(maze, i, j, seen, 0)
                if max(max(seen)) > max_path:
                    max_path = max(max(seen))

    print(max_path)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

s = ["#"*(w+2)]
for i in range(h):
    si = "#"+input()+"#"
    s.append(si)
s.append("#"*(w+2))
nb = [(-1,0),(1,0),(0,1),(0,-1)]
inf = 10000
def bfs(x_,y_):
    dist = [[inf for i in range(w+2)] for j in range(h+2)]
    Q = deque()
    dist[x_][y_] = 0
    Q.append((x_,y_))
    while Q:
        x,y = Q.popleft()
        for u,v in nb:
            if s[x+u][y+v]!="#":
                if dist[x+u][y+v]>dist[x][y]+1:
                    dist[x+u][y+v]=dist[x][y]+1
                    Q.append((x+u,y+v))
    res = -1
    for i in range(h+2):
        for j in range(w+2):
            if dist[i][j]<inf:
                res = max(res,dist[i][j])
    return res
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
       
        ans = max(ans,bfs(i,j))
print(ans)