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:
from collections import deque
h, w = map(int, input().split())
s = []
longest = 0

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

ans = 0
for x in range(h):
    for y in range(w):
        q = deque()
        q.append((0, (x, y)))
        done = set()
        temp = 0

        while q:
            dis, tup = q.popleft()
            i, j = tup[0], tup[1]
            temp = max(temp, dis)

            # Right
            if j < w - 1 and s[i][j + 1] == '.':
                if str(i) + str(j + 1) not in done:
                    done.add(str(i) + str(j + 1))
                    q.append((dis + 1, (i, j + 1)))

            # Left
            if j > 0 and s[i][j - 1] == '.':
                if str(i) + str(j - 1) not in done:
                    done.add(str(i) + str(j - 1))
                    q.append((dis + 1, (i, j - 1)))

            # Up
            if i > 0 and s[i - 1][j] == '.':
                if str(i - 1) + str(j) not in done:
                    done.add(str(i - 1) + str(j))
                    q.append((dis + 1, (i - 1, j)))

            # Down
            if i < h - 1 and s[i + 1][j] == '.':
                if str(i + 1) + str(j) not in done:
                    done.add(str(i + 1) + str(j))
                    q.append((dis + 1, (i + 1, j)))

        ans = max(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:
#いい加減深さ優先探索, 幅優先探索をスムーズに実装してえなおい

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

S = ["#"] * (H+2)
S[0] = ["#"] * (W+2)
S[H+1] = ["#"] * (W+2)
for i in range(1,H+1):
    S[i] = ["#"]+ list(input()) + ["#"]

inf = 10 ** 3
m = 0
mi = -1
mj = -1
mk = -1
ml = -1
  
for i in range(1,H+1):
    for j in range(1,W+1):
        data = [[inf]*(W+2) for k in range(H+2)]
        data[i][j] = 0
        stack = [[i,j,0]]
        while stack:
            x = stack.pop()
            if S[x[0]+1][x[1]] == "." and data[x[0]+1][x[1]]>x[2]+1:
                data[x[0]+1][x[1]] = x[2]+1
                stack.append([x[0]+1,x[1],x[2]+1])
            if S[x[0]][x[1]+1] == "." and data[x[0]][x[1]+1]>x[2]+1:
                data[x[0]][x[1]+1] = x[2]+1
                stack.append([x[0],x[1]+1,x[2]+1])
            if S[x[0]-1][x[1]] == "." and data[x[0]-1][x[1]]>x[2]+1:
                data[x[0]-1][x[1]] = x[2]+1
                stack.append([x[0]-1,x[1],x[2]+1])
            if S[x[0]][x[1]-1] == "." and data[x[0]][x[1]-1]>x[2]+1:
                data[x[0]][x[1]-1] = x[2]+1
                stack.append([x[0],x[1]-1,x[2]+1])
            #print(i,j,stack)

        for k in range(1,H+1):
            for l in range(1,W+1):
                if data[k][l] > m and data[k][l] != inf:
                    m = data[k][l]
                    mi = i
                    mj = j
                    mk = k
                    ml = l

#print(mi,mj,mk,ml)
print(m)

#DFSならワイの実装力でも割とスムーズにできそう？
#なんで昨日これやらなかったんや

Submission status: Wrong Answer

Solution code:
# D
from collections import deque
import numpy as np
INF = float('inf')
h, w = map(int, input().split())
maps = []

for _ in range(h):
    lst = list(input())
    maps.append(lst)
maps = np.array(maps)

def bfs(start, maps, distance, height, width):
    d = deque()
    d.append(start)
    sx, sy = start
    distance[sx,sy] = 0
    
    while d:
        now = d.popleft()
        nowx, nowy = now
        
        for i in range(0, 4):
            nx, ny = nowx + [1, 0, -1, 0][i], nowy + [0, 1, 0, -1][i]
            if (0<=nx<height)and(0<=ny<width):
                if (maps[nx,ny] == '.'):
                    if (distance[nx,ny] == -1):
                        #(distance[nowx,nowy]+1<distance[nx,ny]):
                        d.append((nx, ny))
                        distance[nx,ny] = distance[nowx,nowy] + 1
    return distance.max()

cand = []
for sx in range(h):
    for sy in range(w):
        if maps[sx,sy] == '#':
            continue
        distance = np.full((h, w), -1)
        cand.append(bfs((sx, sy), maps, distance, h, w))
print(max(cand))

Submission status: Wrong Answer

Solution code:
from queue import Queue

def bfs(HW, q):
    num = 0
    mem = []
    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

        if [current[0]+1,current[1]]  not in mem:
            mem.append([current[0]+1,current[1]])
            q.put([current[0]+1,current[1],current[2]+1])
        if [current[0],current[1]+1]  not in mem:
            mem.append([current[0],current[1]+1])
            q.put([current[0],current[1]+1,current[2]+1])
        if [current[0]-1,current[1]]  not in mem:
            mem.append([current[0]-1,current[1]])
            q.put([current[0]-1,current[1],current[2]+1])
        if [current[0],current[1]-1]  not in mem:
            mem.append([current[0],current[1]-1])
            q.put([current[0],current[1]-1,current[2]+1])
    return (current[2]-1)


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

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

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 sys


def walk(y, x, cost, costs):
    if not (0 <= y < len(costs) and 0 <= x < len(costs[0])):
        return -1
    if costs[y][x] != 0:
        return -1
    costs[y][x] = cost
    max_cost = cost
    for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
        cost1 = walk(next_y, next_x, cost + 1, costs)
        if cost1 > max_cost:
            max_cost = cost1
    return max_cost


def get_costs(S):
    costs = [[0 for w in range(len(S[0]))] for h in range(len(S))]
    for h in range(len(S)):
        for w in range(len(S[0])):
            if S[h][w] == '#':
                costs[h][w] = -1
    return costs


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_h in range(H):
        for start_w in range(W):
            costs = get_costs(S)
            cost = walk(start_h, start_w, 1, costs)
            if cost > max_cost:
                max_cost = cost

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
EMP = -1 
BLOCK = -2

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

# 迷路情報
maze_map = [[EMP for i in range(w)] for j in range(h)]

# 迷路取得
for i in range(h):
    input_data = input()
    char_data = list(input_data)

    for j in range(len(char_data)):
        # 壁は-1
        if(char_data[j] == "#"):
            maze_map[i][j] = BLOCK

# 最大値取得
max_mass = 0

# 探索
for i in range(h):
    for j in range(w):

        # 迷路、キューを初期化
        tmp_maze_map = deepcopy(maze_map)
        queue_list = []

        # 自身の位置を開始位置とする
        tmp_maze_map[i][j] = 0
        # キューに自身を入れる
        queue_list.append([i,j])

        while(len(queue_list) > 0):
            get_x = queue_list[0][0]
            get_y = queue_list[0][1]

            # チェック(上) 範囲を超える、自身が壁、上が空でないのときは処理しない
            if((get_x == 0) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x-1][get_y] != EMP)):
                pass
            else:
                tmp_maze_map[get_x-1][get_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x-1,get_y])

            # チェック(左)
            if((get_y == 0) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x][get_y-1] != EMP)):
                pass
            else:
                tmp_maze_map[get_x][get_y-1] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x, get_y-1])

            # チェック(右)
            if((get_y == w-1) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x][get_y+1] != EMP)):
                pass
            else:
                tmp_maze_map[get_x][get_y+1] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x, get_y+1])
            # チェック(下)
            if((get_x == h-1) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x+1][get_y] != EMP)):
                pass
            else:
                tmp_maze_map[get_x+1][get_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x+1,get_y])

            # チェックしたマスを取り除く
            queue_list.pop(0)

        # 最大値を取得
        for k in tmp_maze_map:
            t_sum_list = deepcopy(k)
            t_sum_list += [max_mass]
            max_mass = max(t_sum_list)
            t_sum_list.clear()
        
        # 迷路リセット
        tmp_maze_map.clear()

print(max_mass)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '))
table = [[c for c in input()] for _ in range(H)]

def dfs(i, j):
    dists = [[-1 for _ in range(W)] for _ in range(H)]
    nexts = ((-1,0), (1,0), (0,-1), (0,1))

    buf = [(i, j)]
    dists[i][j] = 0
    while buf:
        i, j = buf.pop(0)

        for x, y in nexts:
            next_i = i + x
            next_j = j + y
            if 0 <= next_i < H and 0 <= next_j < W:
                if table[next_i][next_j] == '.' and dists[next_i][next_j] == -1:
                    dists[next_i][next_j] = dists[i][j] + 1
                    buf.append((next_i, next_j))




    # for d in dists:
    #     print(d)

    return max(max(dists))

# print(table)

ans = 0
for i in range(H):
    for j in range(W):
        if table[i][j] == '.':
            n = dfs(i, j)
            ans = max(ans, n)


print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
h, w = map(int, input().split())
S = [input() for _ in range(h)]

INF = 100

maze = np.zeros((h*w, h*w))
for i in range(h*w-1):
    for j in range(i+1, h*w):
        i_h, i_w = divmod(i, w)
        j_h, j_w = divmod(j, w)

        if (S[i_h][i_w] == "." and
            S[j_h][j_w] == "." and
            abs(i_h-j_h) + abs(i_w-j_w) == 1):
            maze[i][j] = 1
            maze[j][i] = 1
        else:
            maze[i][j] = INF
            maze[j][i] = INF

# print(maze)

# for i in range(h*w):
#     for j in range(h*w):
#         for k in range(h*w):
#             maze[j][k] = min(maze[j][k], maze[j][i] + maze[i][k])

maze = floyd_warshall(maze)

# print(maze)
# print(maze[maze < INF])
print(int(max(maze[maze<INF])))

Submission status: Wrong Answer

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

queue = []
visited = [] 
ans = 0
for i in range(h):
    T = [0]*w
    visited.append(T) 
    
for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            while len(queue) > 0:
              now = queue.pop(0)
              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] = visited[now[0]][now[1]]+1
                    queue.append([y,x])
                    
        for i in range(h):
          for j in range(w):
            ans = max(ans,visited[i][j])
            
        queue = []
        visited = [] 
        for i in range(h):
            T = [0]*w
            visited.append(T) 
            
       
            
        
print(ans-1)

Submission status: Wrong Answer

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

queue = []
visited = [] 
ans = 0
for i in range(h):
    T = [0]*w
    visited.append(T) 
    
for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            count = 0
            p = 0
            while len(queue) > 0:
              now = queue.pop(0)
              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] = visited[now[0]][now[1]]+1
                    queue.append([y,x])
                    if p == 0:
                      count += 1
                      p += 1
              p = 0
        for i in range(h):
          for j in range(w):
            ans = max(ans,visited[i][j])
        queue = []
        visited = []  
        for i in range(h):
            T = [0]*w
            visited.append(T) 
       
            
        
print(ans-1)

Submission status: Wrong Answer

Solution code:
M=450
e=enumerate
_,*s=open(0)
r=s+['#'*20]
d=eval('[M]*M,'*M)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    if u>'#'<t[j+1]:
      d[k][k+1]=1
      d[k+1][k]=1
    if u>'#'<r[i+1][j]:
      d[k][k+20]=1
      d[k+20][k]=1
r=range(M)
for k in r:
  for i in r:
    for j in r:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(max(u for t in d for u in t if u<M))

Submission status: Wrong Answer

Solution code:
M=410
e=enumerate
_,*s=open(0)
r=s+['#'*20]
d=eval('[M]*M,'*M)
d[0][0]=0
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    if u>'#'<t[j+1]:
      d[k][k+1]=1
      d[k+1][k]=1
    if u>'#'<r[i+1][j]:
      d[k][k+20]=1
      d[k+20][k]=1
r=range(M)
for k in r:
  for i in r:
    for j in r:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(max(u for t in d for u in t if u<M))

Submission status: Wrong Answer

Solution code:
M=410
e=enumerate
_,*s=open(0)
r=s+['#'*20]
d=eval('[M]*M,'*M)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    if u>'#'<t[j+1]:
      d[k][k+1]=1
      d[k+1][k]=1
    if u>'#'<r[i+1][j]:
      d[k][k+20]=1
      d[k+20][k]=1
r=range(M)
for k in r:
  for i in r:
    for j in r:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(max(u for t in d for u in t if u<M))

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
e=enumerate
b,*s=open(0)
r=s+[b*20]
*g,=eval('[0]*500,'*500)
for i,t in e(s):
 for j,u in e(t):k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<r[i+1][j]  
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
e=enumerate
h,*s=open(0)
h,w=map(int,h.split())
*g,=eval('[0]*500,'*500)
for i,t in e(s):
  for j,u in e(t):
    k=i*w+j
    g[k][k+1]=u>'#'<t[j+1]
    g[k][k+w]=(i<h-1)*u>'#'<s[i+1][j]  
a=csgraph.johnson(csr_matrix(g),0)
print(a[a<999].max())

Submission status: Wrong Answer

Solution code:
H,W = (int(x) for x in input().split())
a = []
que = []
dis =[]
longDis = 0

for i in range(H):
    a += list(input().split())

h = -1
w = 0

for _ in range(H*W):
    com = [[0 for i in range(W)] for j in range(H)]
    k = 0
    dis = [k]
    l = 0

    if h < H-1:
        h += 1
    else:
        h = 0
        w += 1

    if a[h][w] != '.':
        continue

    que += [[h,w]]
    i = h
    j = w
    
    while True:
        k = dis[l] + 1

        #上
        if i-1 >= 0 and a[i-1][j] == '.':
            if com[i-1][j] == 0:
                que += [[i-1,j]]
                dis += [k]
                com[i-1][j] = 1

        #下
        if i+1 < H and a[i+1][j] == '.':
            if com[i+1][j] == 0:
                que += [[i+1,j]]
                dis += [k]
                com[i+1][j] = 1

        #左
        if j-1 >= 0 and a[i][j-1] == '.':
            if com[i][j-1] == 0:
                que += [[i,j-1]]
                dis += [k]
                com[i][j-1] = 1 

        #右
        if j+1 < W and a[i][j+1] == '.':
            if com[i][j+1] == 0:
                que += [[i,j+1]]
                dis += [k]
                com[i][j+1] = 1

        l += 1

        if l == len(que):
            break
        
        i = que[l][0]
        j = que[l][1]

    for i in range(len(dis)):
        if dis[i] > longDis:
            longDis = dis[i]

    dis.clear()
    que.clear()

print(longDis)

Submission status: Wrong Answer

Solution code:
H,W = (int(x) for x in input().split())
a = []
que = []
dis =[]
longDis = 0

for i in range(H):
    a += list(input().split())

h = -1
w = 0

for _ in range(H*W):
    k = 0
    dis = [k]
    l = 0

    if h < H-1:
        h += 1
    else:
        h = 0
        w += 1

    if a[h][w] != '.':
        continue

    que += [[h,w]]
    i = h
    j = w
    
    while True:
        k = dis[l] + 1

        #上
        if i-1 >= 0 and a[i-1][j] =='.':
            if [i-1,j] not in que:
                que += [[i-1,j]]
                dis += [k]

        #下
        if i+1 < H and a[i+1][j] == '.':
            if [i+1,j] not in que:
                que += [[i+1,j]]
                dis += [k]

        #左
        if j-1 >= 0 and a[i][j-1] == '.':
            if [i,j-1] not in que:
                que += [[i,j-1]]
                dis += [k]

        #右
        if j+1 < W and a[i][j+1] == '.':
            if [i,j+1] not in que:
                que += [[i,j+1]]
                dis += [k]

        l += 1

        if l == len(que):
            break
        
        i = que[l][0]
        j = que[l][1]

        if k > longDis:
            longDis = k

    dis.clear()
    que.clear()

print(longDis)

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from collections import deque


def main():
    H,W = map(int,input().split())
    S = [input().split()[0] for _ in range(H)]

    INF = 1001001001
    res = 0

    di = [-1,0,1,0]
    dj = [0,-1,0,1]

    path = np.full((H,W,H,W),INF)

    for si in range(H):
        for sj in range(W):
            for k in range(4):
                gi = si + di[k]
                gj = sj + dj[k]
                if (gi<0)|(gi>=H)|(gj<0)|(gj>=W):
                    continue
                if S[gi][gj] == '#':
                    continue
                if (si==gi)&(sj==gj):
                    path[si,sj,gi,gj] = 0
                else:
                    path[si,sj,gi,gj] = 1

    for mi in range(H):
        for mj in range(W):
            for si in range(H):
                for sj in range(W):
                    for gi in range(H):
                        for gj in range(W):
                            temp = min(path[si,sj,gi,gj],path[si,sj,mi,mj]+path[mi,mj,gi,gj])
                            path[si,sj,gi,gj] = temp

    res = np.max(path[path<INF])


    print(res)


main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(s, start):
    if s[start[0]][start[1]] == "#":
        return -1 
    q = deque([start])
    distance = [[-1] * w for _ in range(h)]
    distance[start[0]][start[1]] = 0

    while q:
        y, x = q.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + i, x + j
            if not(0 <= new_y < h and 0 <= new_x < w): continue
            if s[new_y][new_x] == "#": continue
            if distance[new_y][new_x] == -1:
                distance[new_y][new_x] = distance[y][x] + 1
                q.append([new_y, new_x])

    print(distance)
    return max(map(max, distance))


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

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, solve(s, [i, j]))

print(ans)

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import math
# import copy
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from collections import deque


def main():
    H,W = map(int,input().split())
    S = [input().split()[0] for _ in range(H)]

    INF = 1001001001
    res = 0

    di = [-1,0,1,0]
    dj = [0,-1,0,1]

    path = [[[[INF for i in range(W)] for j in range(H)] for k in range(W)] for l in range(H)]

    for si in range(H):
        for sj in range(W):
            for k in range(4):
                gi = si + di[k]
                gj = sj + dj[k]
                if (gi<0)|(gi>=H)|(gj<0)|(gj>=W):
                    continue
                if S[gi][gj] == '#':
                    continue
                if (si==gi)&(sj==gj):
                    path[si][sj][gi][gj] = 0
                else:
                    path[si][sj][gi][gj] = 1

    for mi in range(H):
        for mj in range(W):
            for si in range(H):
                for sj in range(W):
                    for gi in range(H):
                        for gj in range(W):
                            temp = min(path[si][sj][gi][gj],path[si][sj][mi][mj]+path[mi][mj][gi][gj])
                            path[si][sj][gi][gj] = temp

    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    temp = path[si][sj][gi][gj]
                    if temp == INF:
                        continue
                    res = max(res,temp)


    print(res)


main()

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import math
# import copy
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from collections import deque


def main():
    H,W = map(int,input().split())
    S = [input().split()[0] for _ in range(H)]

    INF = 1001001001
    res = 0

    di = [-1,0,1,0]
    dj = [0,-1,0,1]

    path = [[[[INF for i in range(W)] for j in range(H)] for k in range(W)] for l in range(H)]

    for si in range(H):
        for sj in range(W):
            for k in range(4):
                gi = si + di[k]
                gj = sj + dj[k]
                if (gi<0)|(gi>=H)|(gj<0)|(gj>=W):
                    continue
                if S[gi][gj] == '#':
                    continue
                if (si==gi)&(sj==gj):
                    path[si][sj][gi][gj] = 0
                else:
                    path[si][sj][gi][gj] = 1

    for mi in range(H):
        for mj in range(W):
            for si in range(H):
                for sj in range(W):
                    for gi in range(H):
                        for gj in range(W):
                            temp = min(path[si][sj][gi][gj],path[si][sj][mi][mj]+path[mi][mj][gi][gj])
                            path[si][sj][gi][gj] = temp

    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    temp = path[si][sj][gi][gj]
                    if temp == INF:
                        continue
                    res = max(res,temp)


    print(res)


main()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0
for y1 in range(H-1):
  for x1 in range(W-1):
    for y2 in range(y1,H):
      for x2 in range(x1,W):
        if grid[y2][x2]=="#" or grid[y1][x1]=="#":
          continue
        q=deque()
        q.append([y1,x1,0])
        seen=[[False for j in range(W)] for i in range(H)]
        while q:
          node=q.popleft()
          y=node[0]
          x=node[1]
          dist=node[2]
          if seen[y][x]:
            continue
          if grid[y][x]=="#":
            continue
          if y==y2 and x==x2:
            if ans<dist:
              ans=dist
          seen[y][x]=True
          if y-1>=0:
            q.append([y-1,x,dist+1])
          if y+1<H:
            q.append([y+1,x,dist+1])
          if x-1>=0:
            q.append([y,x-1,dist+1])
          if x+1<W:
            q.append([y,x+1,dist+1])
            
print(ans)

Submission status: Wrong Answer

Solution code:
'''input
3 2
..
..
..
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0:
				if maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n:
				if maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0:
				if maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m:
				if maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(n):
	state = list(input().strip())
	maze.append(state)

# from random import randint
# for _ in range(1000):
# maze = []
# n = randint(1, 20)
# m = randint(1, 20)
# for i in range(n):
# 	temp = []
# 	for j in range(m):
# 		k = randint(1, 2)
# 		if k == 1:
# 			temp.append('.')
# 		else:
# 			temp.append('#')
# 	maze.append(temp)

ans = 0
done = set()
for i in range(n):
	for j in range(m):
		first = [i, j]
		ans = max(ans, bfs(first))	
print(ans)

Submission status: Wrong Answer

Solution code:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                         for _ in range(H)] + [['#'] * (W + 2)]
ans = 0


def bfs(x, y, S):
    s = copy.deepcopy(S)
    s[x][y] = '#'
    q = collections.deque([(x, y, 0)])
    while q:
        x, y, d = q.popleft()
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == '.':
                q += [[nx, ny, d + 1]]
                s[nx][ny] = '#'
    return x, y, d


for x, y in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S[x][y] == '.':
        break
x, y, d = bfs(x, y, S)
x, y, d = bfs(x, y, S)
print(d)

Submission status: Wrong Answer

Solution code:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
def bfs(x, y, S):
    s = copy.deepcopy(S)
    q = collections.deque([(x, y, 0)])
    while q:
        x, y, d = q.popleft()
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == '.':
                q += [[nx, ny, d + 1]]
                s[nx][ny] = '#'
    return x, y, d
for x,y in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S[x][y] == '.':
        S[x][y] = '#'
        break
x, y, d = bfs(x, y, S)
x, y, d = bfs(x, y, S)
print(d)

Submission status: Wrong Answer

Solution code:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
def bfs(x, y, S):
    s = copy.deepcopy(S)
    q = collections.deque([(x, y, 0)])
    while q:
        x, y, d = q.popleft()
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == '.':
                q += [[nx, ny, d + 1]]
                s[nx][ny] = '#'
    return x, y, d
for x,y in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S[x][y] == '.':
        break
x, y, d = bfs(x, y, S)
x, y, d = bfs(x, y, S)
print(d)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
#-------------------------------------------------------------------
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
H,W = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

S=[ "" for _ in range(H+2) ]
#p(S)

S[0]="#"*(W+2)
S[H+1]="#"*(W+2)
for h in range(1,H+1):
	s = input()
	S[h] = "#" + s + "#"

#p(S)

XY=[[1,0],[-1,0],[0,1],[0,-1]]

INF=float("inf") # 正の無限大
ans=0

from collections import deque

for h in range(1,H+1):
	for w in range(1,W+1):

		if S[h][w]=="#": continue

		M=[[ INF for w in range(W+2) ] for h in range(H+2)]
		M[h][w]=0

		Q = deque()
		Q.append([h,w])

		#p("Q=",Q)
		
		while Q:
			h,w=Q.pop()
			
			if S[h][w]=="#": continue
			
			m = M[h][w]
			ans=max(ans,m)
			for x,y in XY:
				if S[h+y][w+x]=="#": continue
				
				if M[h+y][w+x] > (m+1):
					M[h+y][w+x] = m+1
					Q.append([h+y,w+x])
					ans=max(ans,m+1)

			#p("h,w,Q,m=",h,w,Q,m)

#for m in M:
#	print(m)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
def bfs(x, y, S):
    s = copy.deepcopy(S)
    q = collections.deque([(x, y, 0)])
    while q:
        x, y, d = q.popleft()
        s[x][y] = '#'
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == '.':
                q += [[nx, ny, d + 1]]
    return x, y, d
for x,y in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S[x][y] == '.':
        break
x, y, d = bfs(x, y, S)
x, y, d = bfs(x, y, S)
print(d)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = -1
direc = [[1,0,-1,0],[0,1,0,-1]]
from collections import deque
def dfs(start):
  q = deque([])# スタック
  Dis[start[0]][start[1]]=0
  q.append(start)
  while len(q)!=0:
    h,w = q.popleft()# スタック取りだし（先頭）
    for i in range(4):
      hs = h+direc[0][i]
      ws = w+direc[1][i]
      if 0<=hs<H and 0<=ws<W and Dis[hs][ws]==INF:
        if Gd[hs][ws]=='.':
          q.append([hs,ws])
          Dis[hs][ws]=Dis[h][w]+1
  return max(max(Dis))
Dis = [[INF]*W for _ in range(H)]
ans = INF
for h in range(H):
  for w in range(W):
    if Gd[h][w]=='.':
      Dis = [[INF]*W for _ in range(H)]
      start = [h,w]
      ans = max(ans,dfs(start))
print(ans)