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 = [input() for _ in range(H)]

INF = 10**15
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)]
      dist[i][j] = 0
      stack = deque([(i, j)])
      
      while stack:
        s = stack.popleft()
        si, sj = s
        for di, dj in d:
          if 0 <= si + di <= H - 1 and 0 <= sj + dj <= W - 1 and S[si + di][sj + dj] != "#":
            if dist[si + di][sj + dj] > dist[si][sj] + 1:
              dist[si + di][sj + dj] = dist[si][sj] + 1
              stack.append((si + di, sj + dj))
      #print(dist)

      max_dist = 0
      for i in range(H):
        for j in range(W):
          if dist[i][j] != INF:
            max_dist = max(max_dist, dist[i][j])
      answer = max(max_dist, answer)
      
print(answer)

Submission status: Wrong Answer

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

maze = [list(input()) for _ in range(h)]
#print(maze)
ans = 0
def solve(sx, sy):
    reached = [[0 for _ in range(w)] for _ in range(h)]
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]    
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "#":
                continue
            if reached[next_x][next_y] != 0:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            gl = max(gl, reached[i][j])
    return gl

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            res = solve(i, j)
            ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

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

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
mx = 0 
for i in range(H//2 + 1): 
        for j in range(W):
                if S[i][j] == ".":
                        q = queue.Queue()
                        q.put([i, j, 0]) 
                        checked = [[0 for l in range(W)] for k in range(H)]
                        while not q.empty():
                                di = q.get()    
                                if mx < di[2]:
                                        mx = di[2]
                                checked[di[0]][di[1]] = -1
                                for k in range(4):
                                        nh = di[0] + dy[k]
                                        nx = di[1] + dx[k]
                                        if 0 <= nx < W and 0 <= nh < H and checked[nh][nx] == 0:
                                                if S[nh][nx] == ".":
                                                        q.put([nh, nx, di[2] + 1]) 
print(mx)

Submission status: Wrong Answer

Solution code:
from collections import deque    
H,W = map(int, input().split())
maze = []
ans = 0
dist =[]
q = deque([])
tmp = 0

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

for i in range(H):
    for j in range(W):
        dist = [[-1]*W for i in range(H)] # 配列の初期化
        q.append([i,j]) #初期値挿入
        dist[i][j] = 0
        while(q):
            a,b = q.popleft()
            if a + 1 < H:
                if maze[a+1][b] == '.' and dist[a+1][b] == -1:
                    q.append([a+1, b])
                    dist[a+1][b] = dist[a][b] + 1
                    tmp = dist[a+1][b] 
            if a > 0:
                if maze[a-1][b] == '.' and dist[a-1][b] == -1:
                    q.append([a-1, b])
                    dist[a-1][b] = dist[a][b] + 1
                    tmp = dist[a-1][b]
            if b + 1 < W:
                if maze[a][b+1] == '.' and dist[a][b+1] == -1:
                    q.append([a, b+1])
                    dist[a][b+1] = dist[a][b] + 1
                    tmp = dist[a][b+1]
            if b > 0:
                if maze[a][b-1] == '.' and dist[a][b-1] == -1:
                    q.append([a, b-1])
                    dist[a][b-1] = dist[a][b] + 1
                    tmp = dist[a][b-1]
        ans = max(ans,tmp)


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 = [list(readline()) for i in range(H)]


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

        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 distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))


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

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

INF = 10**15
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)]
      dist[i][j] = 0
      stack = deque([(i, j)])
      
      while stack:
        s = stack.popleft()
        si, sj = s
        for di, dj in d:
          if 0 <= si + di <= H - 1 and 0 <= sj + dj <= W - 1 and S[si + di][sj + dj] != "#":
            if dist[si + di][sj + dj] > dist[si][sj] + 1:
              dist[si + di][sj + dj] = dist[si][sj] + 1
              stack.append((si + di, sj + dj))
      #print(dist)

      max_dist = -1
      for i in range(H):
        for j in range(W):
          if dist[i][j] != INF:
            max_dist = max(max_dist, dist[i][j])
      answer = max(max_dist, answer)
      
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

INF = 10**15
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

answer = -1
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)]
      dist[i][j] = 0
      stack = deque([(i, j)])
      
      while stack:
        s = stack.popleft()
        si, sj = s
        for di, dj in d:
          if 0 <= si + di <= H - 1 and 0 <= sj + dj <= W - 1 and S[si + di][sj + dj] != "#":
            if dist[si + di][sj + dj] > dist[si][sj] + 1:
              dist[si + di][sj + dj] = dist[si][sj] + 1
              stack.append((si + di, sj + dj))
      #print(dist)

      max_dist = -1
      for i in range(H):
        for j in range(W):
          if dist[i][j] != INF:
            max_dist = max(max_dist, dist[i][j])
      answer = max(max_dist, answer)
      
print(answer)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
meiro = [list(input()) for i in range(h)]
max_d = 0
from collections import deque

def bfs(sx,sy):
    que = deque([(sx,sy,0)])
    d = [[0]*w for i in range(h)]
    d[sx][sy] = 1
    max_len=0
    while que:
        x,y,tmp_len = que.popleft()
        for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
            tmp = tmp_len
            nx,ny = x+dx,y+dy
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 0 and meiro[nx][ny] =='.':
                d[nx][ny] = 1
                max_len = max(max_len, tmp+1)
                que.append((nx,ny,tmp+1))
    return max_len

for s_i in range(h):
    for s_j in range(w):
        max_d = max(bfs(s_i,s_j), max_d)
print(max_d)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(s):
    queue = deque([])
    queue.appendleft(s)
    visited = [[-1 for _ in range(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 -1 < new_x and new_x < W and -1 < new_y and new_y < 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])
    return max(max(visited))

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        if S[i][l] != ".":
            continue
        ans = max(ans, solve([i, l]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(s):
    queue = deque()
    queue.appendleft(s)
    visited = [[-1 for _ in range(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 -1 < new_x and new_x < W and -1 < new_y and new_y < 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])
    return max(max(visited))

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        if S[i][l] != ".":
            continue
        ans = max(ans, solve([i, l]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(S, s):
    queue = deque()
    queue.appendleft(s)
    visited = [[-1 for _ in range(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 -1 < new_x and new_x < W and -1 < new_y and new_y < 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])
    return max(max(visited))

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        if S[i][l] != ".":
            continue
        ans = max(ans, solve(S, [i, l]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(S, s):

    queue = deque([s])
    visited = [[-1 for _ in range(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 -1 < new_x and new_x < W and -1 < new_y and new_y < 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])
    return max(max(visited))

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        if S[i][l] != ".":
            continue
        ans = max(ans, solve(S, [i, l]))
print(ans)

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 for _ in range(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 -1 < new_x and new_x < W and -1 < new_y and new_y < 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])
    return max(max(visited))

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as dcopy
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
def mostfar(sx,sy,s):
  mx=len(s)*len(s[0])-1
  l=[[mx if s[j][i]=='.' else 0 for i in range(w)] for j in range(h)]
  step=1
  l[sy][sx]=1
  tmp=dcopy(l)
  while 1:
    step+=1
    for x in range(w):
      for y in range(h):
        if l[y][x]==step-1:
          if x!=0:
            l[y][x-1]=min(l[y][x-1],step)
          if x!=w-1:
            l[y][x+1]=min(l[y][x+1],step)
          if y!=0:
            l[y-1][x]=min(l[y-1][x],step)
          if y!=h-1:
            l[y+1][x]=min(l[y+1][x],step)
    if tmp==l:
      break
    tmp=dcopy(l)
  return max([max(r) for r in l])-1

ans=max([max([mostfar(x,y,s) for x in range(w)]) for y in range(h)])
print(ans)

Submission status: Wrong Answer

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

    def bfs(start_row, start_col):
        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 = [[-1 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] == -1:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return max(max(dist))

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '#':
                continue
            dist = bfs(start_row, start_col)
            ans = max(dist, ans)
    return ans

print(d_maze_master())

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          A[h][w]=0
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    ans = max(ans,max(max(A)))
    
print(ans)

Submission status: Wrong Answer

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

for i in range(h):
  for j in range(w):
    if l[i][j]=='.':
      if i!=0:
        if l[i-1][j]!=1:
          connection[i*w+j].append((i-1)*w+j)
      if i!=h-1:
        if l[i+1][j]!=1:
          connection[i*w+j].append((i+1)*w+j)
      if j!=0:
        if l[i][j-1]!=1:
          connection[i*w+j].append(i*w+j-1)
      if j!=w-1:
        if l[i][j+1]!=1:
          connection[i*w+j].append(i*w+j+1)

n=h*w
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(h*w):
  ans.append(max(bfs(i)))
print(max(ans))

Submission status: Wrong Answer

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

def bfs(h,w):
  checked = [[False for i in range(W)] for j in range(H)]
  q = [(h,w,0)] if maze[h][w]=="." else []
  g_n = 0
  while q:
    h_,w_,n = q.pop(0)
    g_n = max(n, g_n)
    for i,j in zip([0,0,-1,1],[-1,1,0,0]):
      if (0<=h_+i<H) and (0<=w_+j<W):
        if checked[h_+i][w_+j]: continue
        checked[h_+i][w_+j] = True
        if maze[h_+i][w_+j]==".": q.append((h_+i,w_+j,n+1))
  return g_n

n = 0
for i in range(H):
  for j in range(W):
    n = max(n, bfs(i,j))
print(n)

Submission status: Wrong Answer

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

# print(maze)
    
# 最大距離の初期値
pmax = 0
    
# 任意の点をスタートに設定
# i,jから一番遠い点の距離を幅優先探索で計算
for i in range(H):
    for j in range(W):
        # 次に調べる座標リスト
        checkplace = [[i,j]]
#         print("checkplace:",checkplace)
        # すでに通った場所を記録
        pastplace = [[i,j]]

        # 深さのカウント
        count = 0

        while len(checkplace):
            # 深さのカウント
            nextplace = []
            for place in checkplace:
                h,w = place
                if h > 0 and maze[h-1][w] != "#":
                    #すでに踏んでいるかチェック
                    if [h-1,w] not in pastplace:
                        nextplace.append([h-1,w])
                        pastplace.append([h-1,w])

                if w < W-1 and maze[h][w+1] != "#":
                    #すでに踏んでいるかチェック
                    if [h, w+1] not in pastplace:
                        nextplace.append([h,w+1])
                        pastplace.append([h,w+1])

                if h < H-1 and maze[h+1][w] != "#":
                    #すでに踏んでいるかチェック
                    if [h+1,w] not in pastplace:
                        nextplace.append([h+1,w])
                        pastplace.append([h+1,w])

                if w > 0 and maze[h][w-1] != "#":
                    #すでに踏んでいるかチェック
                    if [h,w-1] not in pastplace:
                        nextplace.append([h,w-1])
                        pastplace.append([h,w-1])
            if len(nextplace) > 0:
                count += 1
            else:
                if count > pmax:
                    pmax = count
            checkplace = nextplace
#             print("count:",count,"nextplace:\n\t",nextplace)

print(pmax)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
import numpy as np
ans = 0
for i in range(H):
  for j in range(W):
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
      
    A = np.array(A)
    ans = max(ans,max(A[A<10**5]))
    
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = list(map(int,input().split()))
s = []
for i in range(h):
    sh = list(input())
    s.append(sh)
#ki = ["n"]*(h*w)    
ki = [[] for i in range(h*w)]
def ichi(a,b):
    return a + b*h
for a in range(h):
    for b in range(w):
        if s[a][b] == ".":
            if  a+1 < h and s[a+1][b] == "." :
                ki[ichi(a+1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a+1,b))
            if  a-1 >= 0 and s[a-1][b] == ".":
                ki[ichi(a-1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a-1,b))
            if b-1 >= 0 and s[a][b-1] == ".":
                ki[ichi(a,b-1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b-1))
            if b+1 < w and s[a][b+1] == "." :
                ki[ichi(a,b+1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b+1))
        else:
            pass
for i in range(w*h):
    ki[i] = list(set(ki[i]))
#print(ki)
ans = []
for i in range(w*h):
    ikeru = [i]
    sumi = []
    kaisuu = [-1]*(w*h)
    kaisuu[i] = 0
    while len(ikeru) > 0:
        j = ikeru.pop()
        sumi.append(j)
        for k in range(len(ki[j])):
            if not ki[j][k] in sumi:
                ikeru.append(ki[j][k])
                if kaisuu[ki[j][k]] > kaisuu[j] + 1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1
                elif kaisuu[ki[j][k]] == -1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1 
#        print(i,kaisuu,ikeru)
    ans.append(max(kaisuu))
#print(ans)
print(max(ans))

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 for _ in range(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.appendleft([new_y, new_x])
    #    for v in visited:
    #        print(v)
    return max(max(visited))

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
def main():
    hw = list(map(int, input().split()))
    s = np.zeros((hw[0],hw[1]), dtype=int)
    validpoints = []
    for i in range(hw[0]):
        tmp = input()
        tm = [None]*hw[1]
        for j in range(hw[1]):
            if tmp[j] == '.':
                tm[j] = 0
                validpoints.append((i,j))
            elif tmp[j] == '#':
                tm[j] = 1
        s[i] = np.array(tm)

    ma = 0
    for i in validpoints:
        for j in validpoints:
            cost = breadth(s,i,j)
            if cost > ma:
                ma = cost
    print(ma)

    # print(breadth(s,(2,0),(0,4)))
    # print(breadth(s,(0,0),(2,2)))
    
def breadth(ss, start, goal):
    q = deque()
    visited = np.array(ss)
    visited[start] = 1
    q.append(start)
    c = 0
    while not len(q) == 0:
        v = q.pop()
        if v == goal:
            break
        down = (v[0]+1,v[1])
        up = (v[0]-1,v[1])
        right = (v[0],v[1]+1)
        left = (v[0],v[1]-1)
        child = [down,up,right,left]
        child = list(filter(lambda i: 0 <= i[0] < len(ss) and 0 <= i[1] < len(ss[0]) and visited[i[0],i[1]] == 0, child))

        for i in child:
            visited[i] = 1
            q.append(i)
        c += 1
        
    return c

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

visited = [[False] * (w + 5) for _ in range(h + 5)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue

        q = deque()
        q.append([i, j, 0])
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        while len(q) != 0:
            x, y, z = q.popleft()
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          A[h][w]=0
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    ans = max(ans,max(max(A)))
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve(maze, init_y, init_x, H, W):
    distances = [[-1 for _ in range(W)] for _ in range(H)]
    distances[init_y][init_x] = 0

    def is_inside(y, x):
        return 0 <= x < W and 0 <= y < H

    def need_to_search(y, x):
        return maze[y][x] != "#" and distances[y][x] == -1

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

    q = deque()
    for dy, dx in four_directions:
        ny, nx = init_y+dy, init_x+dx
        if not is_inside(ny, nx):
            continue
        if need_to_search(ny, nx):
            q.appendleft([ny, nx])
            distances[ny][nx] = 1

    while q:
        y, x = q.pop()
        d = distances[y][x]

        for dy, dx in four_directions:
            ny, nx = y+dy, x+dx
            if not is_inside(ny, nx):
                continue
            if need_to_search(ny, nx):
                q.appendleft([ny, nx])
                distances[ny][nx] = d+1

    return max(max(distances))


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

    farthest = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == "#":
                continue
            distance = solve(maze, i, j, H, W)
            farthest = max(distance, farthest)

    print(farthest)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import deque
H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[False for _ in range(W)] for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if maze[nx][ny] != "#" and not visited[nx][ny]:
                    q.append([nx, ny])
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
        dist = -1
        for i in range(H):
            dist = max(dist, max(visited[i]))
    return dist
ans = -1
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import copy

def bfs(maze, visited, sy, sx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 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 maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited

H, W = map(int, input().split())
MAZE = ["#" + input() + "#" for _ in range(H)]
MAZE.insert(0,"#"*(W+2))
MAZE.append("#"*(W+2))
ans = 0
visit = [[-1]*(W+2) for _ in range(H+2)]
for i in range(H + 2):
    for j in range(W + 2):
        if MAZE[i][j] == "#":
            visit[i][j] = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        visited = copy.deepcopy(visit)
        tmp = np.max(bfs(MAZE, visited, i, j))
        ans = max(ans, tmp)
print(ans)

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 for _ in range(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])
    #    for v in visited:
    #        print(v)
    return max(max(visited))

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