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 sys

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
if H==W==1:
    print(0)
    sys.exit()
inf=float("inf")
data=[[inf]*W for i in range(H)]
start=[0,0]
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            start=[i,j]
            break
    else:
        continue
    break
d=[[1,0],[0,1],[-1,0],[0,-1]]
que=[start]
data[start[0]][start[1]]=0
count=1
while que:
    h=[]
    for x,y in que:
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                h.append([nx,ny])
                data[nx][ny]=count
    que=h
    count+=1
z=[0,0]
num=0
for i in range(H):
    for j in range(W):
        if data[i][j]!=inf and data[i][j]>num:
            num=data[i][j]
            z=[i,j]
            
data=[[inf]*W for i in range(H)]
que=[z]
data[z[0]][z[1]]=0
count=1

while que:
    h=[]
    for x,y in que:
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                h.append([nx,ny])
                data[nx][ny]=count
    que=h
    count+=1
ans=0
for i in range(H):
    for j in range(W):
        if data[i][j]==inf:
            continue
        ans=max(ans,data[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
h, w = [int(v) for v in input().split()]
field = [list(input()) for i in range(h)]

def bfs(s, t):
    si, sj = s
    ti, tj = t
    if field[si][sj] == "." and field[ti][tj] == ".":

        search_field = [ [ -1 for i in range(w) ] for j in range(h) ]
        search_list = [s]
        turn = 0
        search_field[si][sj] = turn
        
        
        while search_list:
            turn += 1
            new_search_list = []
            for p in search_list:
                pi, pj = p
                
                for q in adjust_list:
                    qi, qj = q
                    if 0 <= pi+qi < h and 0 <= pj+qj < w:
                        if search_field[pi+qi][pj+qj] == -1 and field[pi+qi][pj+qj] == ".":
                            new_search_list.append((pi+qi,pj+qj))
                            search_field[pi+qi][pj+qj] = turn
            search_list = new_search_list
            if search_field[ti][tj] != -1:
                break
        return search_field[ti][tj]
    else:
        return -1

Submission status: Wrong Answer

Solution code:
import numpy as np
h,w=map(int,input().split())
meiro = [list(input()) for i in range(h)]
#meiro[y][x]
def bfs(a,b):#縦横,0<a<h-1, 0<b<w-1
    da=[1,-1,0,0]
    db=[0,0,1,-1]
    dist=[[-1]*w for i in range(h)]
    dist[a][b]=0
    stack=[(a,b)]
    while stack:
        y,x=stack.pop()
        D=dist[y][x]
        for dy,dx in zip(da,db):
            X=x+dx
            Y=y+dy
            if 0<=Y and Y<=h-1 and X<=w-1 and 0<=X:
                if meiro[Y][X]=='.':
                    if dist[Y][X]==-1:
                        dist[Y][X]=D+1
                        stack.append((Y,X))
                    elif dist[Y][X]>0:
                        dist[Y][X]=min(dist[Y][X],D+1)
                else:
                    dist[Y][X]==-100
    return dist
first=np.array(bfs(0,0))
ind=np.argmax(first)
zahyo=np.unravel_index(ind,first.shape)
second=np.array(bfs(zahyo[0],zahyo[1]))
print(second.max())

Submission status: Wrong Answer

Solution code:
from queue import Queue
h,w=map(int,input().split())
S=[input() for _ in range(h)]

def bfs(q):
  x,y,cnt=q.get()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])

ans=0
for x in range(h):
  for y in range(w):
    q=Queue()
    q.put([x,y,0])

    memo=[[-1]*w for _ in range(h)]
    while not q.empty():
      bfs(q)
    ans=max(ans,max(max(memo)))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(si, sj):
    q = deque()
    q.append([si, sj, 0])
    used = set([si,sj])
    ans = MAX_VALUE
    while len(q) > 0:
        prvi, prvj, d = q.popleft()
        for i, j in [[prvi-1, prvj], [prvi+1, prvj], [prvi, prvj-1], [prvi, prvj+1]]:
            if grid[j][i] == '#':
                ans = min(ans, d)
                continue
            elif (i,j) not in used:
                q.append([i,j,d+1])
                used.add((i,j))
    return d

H, W = map(int, input().split())
MAX_VALUE = (H+2) * (W+2) + 1
grid = ['#'*(W+2)] + [ '#' + input() + '#' for _ in range(H)] + ['#'*(W+2)]

ans = 1
for j in range(1, H + 1):
    for i in range(1, W + 1):
        if grid[j][i] == '#':
            continue
        res = bfs(i, j)
        if res != MAX_VALUE:
            ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

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

ans=0

for hh in range(h):
 for ww in range(w):
  dist=[[-1]*(w+1) for i in range(h+1)]
  c=copy.deepcopy(ss)
  xx=c[hh][ww]
  if xx=='#':
   continue
  dist[hh][ww]=0
  dq=deque()
  dq.append((hh,ww))
  while dq:
   y,x=dq.popleft()
   for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
    nx=x+dx
    ny=y+dy
    if 0<=nx<w and 0<=ny<h and c[ny][nx]!='#':
     dq.append((ny,nx))
     c[ny][nx]='#'
     dist[ny][nx]=dist[y][x]+1
  for i in dist:
   ans=max(ans,max(i))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def solve(s):
    bias = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    visited = [[-1] * W for _ in range(H)]
    visited[0][0] = 0
    
    if s[0] == W or s[1] == H or visited[s[1]][s[0]] == "#":
        return visited

    q = deque()
    q.append(s)  # x, y, c

    while q:
        x, y, c = q.popleft()
        visited[y][x] = c

        for u, v in bias:
            if not (0 <= x + u < W) or not (0 <= y + v < H):
                continue

            if visited[y + v][x + u] > -1 or S[y + v][x + u] == "#":
                continue

            q.append((x + u, y + v, c + 1))
            
    return visited

ans_1 = (0, 0, 0)
for y, v in enumerate(solve((0, 1, 1))):
    for x, c in enumerate(v):
        if c >= ans_1[2]:
            ans_1 = (x, y, c)
        
ans_2 = (0, 0, 0)
for y, v in enumerate(solve((1, 0, 1))):
    for x, c in enumerate(v):
        if c >= ans_2[2]:
            ans_2 = (x, y, c)
        
if ans_1[0] == ans_2[0] and ans_1[1] == ans_2[1]:
    print(min(ans_1[2], ans_2[2]))
else:
    print(ans_1[2] + ans_2[2])

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.pop()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == 0:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
            elif maze[new_h][new_w] != "#":
                if visited[h][w] + 1 < visited[new_h][new_w]:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h,new_w])

    return visited

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        visited = [[0]*W for _ in range(H)]
        sh = i
        sw = j
        dfs(maze, visited, sh, sw)
        MAX = 0
        for v in visited:
            for e in v:
                MAX = max(MAX,e)
        ans = max(MAX-1,ans)
print(ans)

Submission status: Wrong Answer

Solution code:

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

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

def dfs(i, j):
  colors = [[["white"] for i in range(W)] for j in range(H)]
  stack = [(i, j)]
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  while stack:
    i, j = map(int, stack.pop())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] != "black":
        distance[x][y] = min(distance[i][j] + 1, distance[x][y])
        stack.append((x, y))
  
  return distance


import itertools
ans = -1
for i in range(H):
  for j in range(W):
    L = list(itertools.chain.from_iterable(dfs(i, j)))
    m = max(list(filter(lambda x: x != inf, L)))
    ans = max(ans, m)

print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    maze = '#' * (W + 2)
    for i in range(H):
        line = f_i.readline().rstrip()
        maze += '#' + line + '#'
    maze += '#' * (W + 2)
    
    move = (1, -1, W + 2, -W - 2)
    start = maze.index('.')
    unvisited = [True] * len(maze)
    unvisited[start] = False
    
    q = deque([(start, 0)])
    while q:
        pos, cnt = q.popleft()
        
        for mv in move:
            next_pos = pos + mv
            if maze[next_pos] == '.' and unvisited[next_pos]:
                q.append((next_pos, cnt + 1))
                unvisited[next_pos] = False
    
    start = pos
    unvisited = [True] * len(maze)
    unvisited[start] = False
    
    q = deque([(start, 0)])
    while q:
        pos, cnt = q.popleft()
        
        for mv in move:
            next_pos = pos + mv
            if maze[next_pos] == '.' and unvisited[next_pos]:
                q.append((next_pos, cnt + 1))
                unvisited[next_pos] = False
    
    print(cnt)

solve()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
d=0
for i in range(h):
    if d:
        break
    for j in range(w):
        if s[i][j]==".":
            p=[i,j]
            d=1
            break
q=[p]
t=[[1for i in range(w)] for j in range(h)]
t[p[0]][p[1]]=1
while q:
    c=[]
    for i,j in q:
        a=[1,-1,0,0]
        b=[0,0,1,-1]
        for d in range(4):
            if 0<=i+a[d]<h and 0<=j+b[d]<w:
                if s[i+a[d]][j+b[d]]==".":
                    if t[i+a[d]][j+b[d]]:
                        t[i+a[d]][j+b[d]]=0
                        c.append([i+a[d],j+b[d]])
    if len(c)==0:
        p=q[0]
        break
    else:
        q=c[::]
q=[p]
t=[[1for i in range(w)] for j in range(h)]
t[p[0]][p[1]]=0
g=0
while q:
    c=[]
    for i,j in q:
        a=[1,-1,0,0]
        b=[0,0,1,-1]
        for d in range(4):
            if 0<=i+a[d]<h and 0<=j+b[d]<w:
                if s[i+a[d]][j+b[d]]==".":
                    if t[i+a[d]][j+b[d]]:
                        t[i+a[d]][j+b[d]]=0
                        c.append([i+a[d],j+b[d]])
    if len(c)==0:
        break
    else:
        g+=1
        q=c[::]
print(g)

Submission status: Wrong Answer

Solution code:
import numpy as np
import queue

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

maze = np.zeros((H, W))


for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '.':
            maze[i, j] = 1

max_run = 0


tan = [[1, 0], [-1, 0], [0, 1], [-1, 0]]

def max_route(h, w):
    g = (21, 21)
    q = queue.Queue()
    checker = maze.copy()
    q.put((h, w))
    q.put(g)

    run = 0

    while not q.empty():
        target = q.get()
        if target == g:
            if not q.empty():
                run += 1
                q.put(g)
        else:
            for t in tan:
                check = [target[0]+t[0], target[1]+t[1]]
                if 0 <= check[0] < H and 0 <= check[1] < W:
                    if checker[check[0], check[1]] == 1:
                        q.put((check[0], check[1]))
                        checker[check[0], check[1]] = 2

    return run


for h in range(H):
    for w in range(W):
        if maze[h, w] == 0:
            continue
        cur = max_route(h, w)
        if cur > max_run:
            max_run = cur

print(max_run)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = []
for h in range(H):
    S.append(input())
from collections import deque
ans = 0
for h in range(H):
    for w in range(W):
        Q = deque([[h,w]])
        count_map = [[-1 for _ in range(W)] for __ in range(H)]
        count_map[h][w] = 0
        while Q:
            q = Q.popleft()
            cnt = count_map[q[0]][q[1]] + 1
            if q[0]-1 >= 0:#上
                if S[q[0]-1][q[1]] == "." and count_map[q[0]-1][q[1]] == -1:
                    count_map[q[0]-1][q[1]] = cnt
                    Q.append([q[0]-1,q[1]])
            if q[1]-1 >= 0:#左
                if S[q[0]][q[1]-1] == "." and count_map[q[0]][q[1]-1] == -1:
                    count_map[q[0]][q[1]-1] = cnt
                    Q.append([q[0],q[1]-1])
            if q[0]+1 <= H-1:#下
                if S[q[0]+1][q[1]] == "." and count_map[q[0]+1][q[1]] == -1:
                    count_map[q[0]+1][q[1]] = cnt
                    Q.append([q[0]+1,q[1]])
            if q[1]+1 <= W-1:#右
                if S[q[0]][q[1]+1] == "." and count_map[q[0]][q[1]+1] == -1:
                    count_map[q[0]][q[1]+1] = cnt
                    Q.append([q[0],q[1]+1])
        temp_max = 0
        for cm in count_map:
            temp_max = max(temp_max,max(cm))
        ans = max(ans,temp_max)
print(ans)

Submission status: Wrong Answer

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


def clear_maze(sx, sy, maze):

    # debug_print(maze)

    INF = 100000000

    field_x_length = len(maze[0])
    field_y_length = len(maze)
    distance = [[INF for i in range(field_x_length)]
                for j in range(field_y_length)]
    #    distance = [[None]*field_x_length]*field_y_length
    for i in range(field_y_length):
        for j in range(field_x_length):
            if maze[i][j] == '#':
                distance[i][j] = -100

    def bfs():
        queue = []

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

        distance[sy][sx] = 0

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

            flag = False
            for i in range(field_y_length):
                if INF in distance[i]:
                    flag  = True
                    break
                else:
                    continue
            if flag is False:
                break
                
    

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

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

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

    return bfs()


S = [list(input()) for _ in range(h)]
# print(S)

ans = 0


# def pick_max(maze):
#     field_x_length = len(maze[0])
#     field_y_length = len(maze)
#     ans = 0
#     for i in ra

for i in range(h):
    for j in range(w):
        start = S[i][j]
        if start == '#':
            continue

        # for k in range(h):
        #     for l in range(w):
            
        num = clear_maze(j, i, S)
        for i in range(h):
            ans = max(ans, max(num[i]))
        # print(an)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
grid=[None]*H
# 仮のスタート
sx,sy=-1,-1
found=False
for i in range(H):
  grid[i]=input()
  if not found:
    for j in range(len(grid[i])):
      if grid[i][j]==".":
        sy=i
        sx=j
        found=True
        
from collections import deque
stack=deque()
# y,x,そこまでの距離
stack.append([sy,sx,0])
INF=10**9
seen=[[INF for j in range(W)] for i in range(H)]

longest=0
longestY=-1
longestX=-1
while stack:
  node=stack.popleft()
  y=node[0]
  x=node[1]
  dist=node[2]
  if grid[y][x]=="#":
    continue
  if seen[y][x]<=dist:
    continue
  if dist>longest:
    longest=dist
    longestY=y
    longestX=x
  seen[y][x]=dist
  if y-1>=0:
    stack.append([y-1,x,dist+1])
  if y+1<H:
    stack.append([y+1,x,dist+1])
  if x-1>=0:
    stack.append([y,x-1,dist+1])
  if x+1<W:
    stack.append([y,x+1,dist+1])

longest=0
longestY=-1
longestX=-1
for i in range(H):
  for j in range(W):
    if grid[i][j]==".":
      if seen[i][j]>longest:
        longest=seen[i][j]
        longestY=i
        longestX=j
        
stack=deque()
stack.append([longestY,longestX,0])
seen=[[INF for j in range(W)] for i in range(H)]
longest=0
while stack:
  node=stack.popleft()
  y=node[0]
  x=node[1]
  dist=node[2]
  if grid[y][x]=="#":
    continue
  if seen[y][x]<=dist:
    continue
  if dist>longest:
    longest=dist
  seen[y][x]=dist
  if y-1>=0:
    stack.append([y-1,x,dist+1])
  if y+1<H:
    stack.append([y+1,x,dist+1])
  if x-1>=0:
    stack.append([y,x-1,dist+1])
  if x+1<W:
    stack.append([y,x+1,dist+1])

ans=0
for i in range(H):
  for j in range(W):
    if grid[i][j]==".":
      if seen[i][j]>ans:
        ans=seen[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
S = tuple(read().split())


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = set()
    while queue:
        x, y = queue.popleft()
        visited.add((x, y))

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and (new_x, new_y) not in visited:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = W * (H // 2) + H // 2
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        tmp = max(map(max, bfs(S, (i, j))))
        if tmp == limit:
            print(limit)
            exit()
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve(S, s):
    if S[s[0]][s[1]] == "#":
        return -1
    queue = deque([s])
    visited = [[-1]*W for _ in range(H)]
    visited[s[0]][s[1]] = 0
    while queue:
        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 new_x in range(W) and new_y in range(H) and S[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])
#    print(visited)
    return max(max(visited))


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

Submission status: Wrong Answer

Solution code:
def main():
    H,W = [int(n) for n in input().split()]
    grid = [[0 if n=="." else 1 for n in input()] for _ in range(H)]
    INF = 10**10
    graph = [[INF]*H*W for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == 0:
                graph[i*W+j][i*W+j]=0
                if i<H-1 and grid[i+1][j]==0:
                    graph[i*W+j][(i+1)*W+(j)] = 1
                    graph[(i+1)*W+(j)][i*W+j] = 1
                if j>0 and grid[i][j-1] == 0:
                    graph[i*W+j][(i)*W+j-1] = 1
                    graph[(i)*W+j-1][i*W+j] = 1
                if j<W-1 and grid[i][j+1] == 0:
                    graph[i*W+j][(i)*W+(j+1)] = 1
                    graph[(i)*W+(j+1)][i*W+j] = 1
                if i>0 and grid[i-1][j] == 0:
                    graph[i*W+j][(i-1)*W+(j)] = 1
                    graph[(i-1)*W+(j)][i*W+j] = 1
    
    
    for k in range(H*W):
        for i in range(H*W):
            for k in range(H*W):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    # for i in range(H*W):
    #     for j in range(W*H):
    #         print(graph[i][j], end="\t")
    #     print()
    m = 0
    for i in range(H*W):
        for j in range(H*W):
            if graph[i][j] == INF:
                continue
            m = max(m,graph[i][j])
    print(m)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]=='.':
      sheet[i+1][j+1] = 1

ans = -1
for i in range(1, H+1):
  for j in range(1, W+1):
    m = -1
    if sheet[i][j]==0:
      continue
    stuck = deque([(j, i, 0)])
    log = [[0]*(W+2) for i in range(H+2)]
    while stuck:
      x, y, c = stuck.popleft()
      if c>m:
        m = c
      for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
        if sheet[y+dy][x+dx]==1 and log[y+dy][x+dx]==0:
          log[y+dy][x+dx] = 1
          stuck += [(x+dx, y+dy, c+1)]
    if ans<m:
      ans = m
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

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

d = [[10**9] * (w*h) for _ in range(w*h)]

for i in range(h):
    for j in range(w):
        if(s[i][j] == '.'):
            if(i != h-1):
                if(s[i+1][j] == '.'):
                    d[(i*w + j)][((i+1)*w + j)] = 1
                    d[((i+1)*w + j)][(i*w + j)] = 1
            if(j != w-1):
                if(s[i][j+1] == '.'):
                    d[(i*w + j)][(i*w + j + 1)] = 1
                    d[(i*w + j + 1)][(i*w + j)] = 1

G = csgraph_from_dense(d, null_value=10**9)
len = floyd_warshall(G)

ans = 0
for i in range(h*w):
    for j in range(h*w):
        if(len[i][j] < 100):
            ans = max(len[i][j], ans)

print(int(ans))

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 c in range(W)] for _ in range(H)]

    buf = [(i, j, 0)]
    while buf:
        buf2 = []
        for i, j, d in buf:
            if dists[i][j] == -1 or dists[i][j] > d:
                dists[i][j] = d
                # if dists[i][j] == -1:
                #     dists[i][j] = d
                # else:
                #     dists[i][j] = min(dists[i][j], d)

                if 0 <= i-1 < H and table[i-1][j] == '.':
                    if dists[i-1][j] == -1:
                        buf2.append((i-1, j, d+1))

                if 0 <= i+1 < H and table[i+1][j] == '.':
                    if dists[i+1][j] == -1:
                        buf2.append((i+1, j, d+1))

                if 0 <= j-1 < W and table[i][j-1] == '.':
                    if dists[i][j-1] == -1:
                        buf2.append((i, j-1, d+1))

                if 0 <= j+1 < W and table[i][j+1] == '.':
                    if dists[i][j+1] == -1:
                        buf2.append((i, j+1, d+1))

        buf = buf2
        # print(buf)

    # 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:
from collections import deque
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]=='.':
      sheet[i+1][j+1] = 1

ans = -1
for i in range(1, H+1):
  for j in range(1, W+1):
    m = -1
    if sheet[i][j]==0:
      continue
    stuck = deque([(j, i, 0)])
    log = [[0]*(W+2) for i in range(H+2)]
    while stuck:
      x, y, c = stuck.popleft()
      for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
        if sheet[y+dy][x+dx]==1 and log[y+dy][x+dx]==0:
          log[y+dy][x+dx] = 1
          stuck += [(x+dx, y+dy, c+1)]
          if c+1>m:
            m = c+1
    if ans<m:
      ans = m
print(ans)

Submission status: Wrong Answer

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

s = [input() for _ in range(h)]

def search(s_h, s_w):
    stack = []
    isuse = [[False] * w for _ in range(h)]
    def add(a, b,score):
        nonlocal stack, isuse
        if not (0 <= a < h and 0 <= b < w):
            return 0
        if s[a][b] == "#":
            return 0
        if isuse[a][b]:
            return 0
        isuse[a][b] = True
        stack.append((a,b,score+1))
        
    add(s_h, s_w, 0)
    c=0
    while stack:
        a,b,c = stack.pop(0)
        add(a + 1, b, c)
        add(a , b + 1, c)
        add(a, b - 1, c)
        add(a - 1, b, c)
    return c

search(0,0)

ans = 0
for s_h in range(h):
    for s_w in range(w):
        ans = max(search(s_h, s_w), ans)
        print(s_h,s_w,search(s_h, s_w))
print(ans)

Submission status: Wrong Answer

Solution code:
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    start_row, start_col = None, None
    for row in range(H):
        for col in range(W):
            if Maze[row][col] == '.':
                start_row, start_col = row, col
                break
        else:
            continue
        break

    diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

    def is_inside(row, col):
        return 0 <= row < H and 0 <= col < W

    queue = deque([(start_row, start_col)])
    dist = [[INF for _ in range(W)] for _ in range(H)]
    dist[start_row][start_col] = 0
    while queue:
        row, col = queue.pop()
        for dr, dc in diff:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                queue.appendleft((nr, nc))
                dist[nr][nc] = dist[row][col] + 1

    start_row, start_col = None, None
    maximum = 0
    for row in range(H):
        for col in range(W):
            if Maze[row][col] != '#' and dist[row][col] > maximum:
                maximum = dist[row][col]
                start_row, start_col = row, col

    queue = deque([(start_row, start_col)])
    dist = [[INF for _ in range(W)] for _ in range(H)]
    dist[start_row][start_col] = 0
    while queue:
        row, col = queue.pop()
        for dr, dc in diff:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                queue.appendleft((nr, nc))
                dist[nr][nc] = dist[row][col] + 1

    ans = 0
    for row in range(H):
        for col in range(W):
            if Maze[row][col] != '#' and dist[row][col] > ans:
                ans = dist[row][col]
    return ans

print(d_maze_master())

Submission status: Wrong Answer

Solution code:
def dfs(i, V, E):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        for j in E[vi]:
            if V[j] == 0:
                V[j] += V[vi] + 1
                S.append(j)
    return V


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
p = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            p += 1
            s[i][j] = p
        else:
            s[i][j] = 0

E = [[] for _ in range(p + 1)]
for i in range(h):
    for j in range(w):
        p = s[i][j]
        if p > 0:
            if j < w - 1:
                p1 = s[i][j + 1]
                if p1 > 0:
                    E[p].append(p1)
                    E[p1].append(p)
            if i < h - 1:
                p2 = s[i + 1][j]
                if p2 > 0:
                    E[p].append(p2)
                    E[p2].append(p)

ans = 0
for i in range(1, len(E)):
    V = [0 for _ in range(len(E))]
    V_res = dfs(i, V, E)
    ans = max(ans, *V_res)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(si, sj):
    q = deque()
    q.append([si, sj, 0])
    used = set([])
    ans = MAX_VALUE
    while len(q) > 0:
        prvi, prvj, d = q.popleft()
        for i, j in [[prvi-1, prvj], [prvi+1, prvj], [prvi, prvj-1], [prvi, prvj+1]]:
            if grid[j][i] == '#':
                ans = min(ans, d)
                continue
            elif (i,j) not in used:
                q.append([i,j,d+1])
                used.add((i,j))
    return d

H, W = map(int, input().split())
MAX_VALUE = (H+2) * (W+2) + 1
grid = ['#'*(W+2)] + [ '#' + input() + '#' for _ in range(H)] + ['#'*(W+2)]

ans = 0
for j in range(1, H + 1):
    for i in range(1, W + 1):
        if grid[j][i] == '#':
            continue
        res = bfs(i, j)
        if res != MAX_VALUE:
            ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = set()
E = defaultdict(list)
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V |= {(i, j)}
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.': E[(i, j)].append((x, y)); E[(x, y)].append((i, j))
start = list(V)[0]

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

D1 = bfs(start)
v, d = sorted(D1.items(), reverse=True, key=lambda x: x[1])[0]
D2 = bfs(v)
print(max(D2.values()))