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())
maze = [input() for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

# BFSでは、同じステップ数のノードを先に全探索するので、訪問済みフラグはグローバル共有しても大丈夫

max_step = 0
for i in range(h):
    for j in range(w):
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        while True:
            if len(plan) == 0:
                break
            y, x, step = plan.pop()
            visited[y][x] = True
            if step > max_step:
                max_step = step
            for next_down, next_right in direction:
                next_y = y + next_down
                next_x = x + next_right
                if next_x == -1 or next_x == w or next_y == -1 or next_y == h:
                    continue
                if maze[next_y][next_x] == "#":
                    continue
                # 訪問済みでないかチェック
                if visited[next_y][next_x]:
                    continue
                plan.appendleft((next_y, next_x, step + 1))

print(max_step)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
  dist = [[-1]*W for _ in range(H)]
  dist[sy][sx] = 0
  q = deque([[sy, sx]])

  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx
      if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1 and S[ny][nx] == '.':
        dist[ny][nx] = dist[y][x] + 1
        q.append([ny, nx])

  return dist

d = bfs(0, 0)
d = np.array(d)
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] != '#':
      d = bfs(i, j)
      d = np.array(d)
  ans = max(ans, np.max(d))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy

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


def get_shortest_steps(S_inner, visited, i_inner, j_inner, l, m, steps):
    if i_inner == l and j_inner == m:
        return steps
    if i_inner == -1 or i_inner == h or j_inner == -1 or j_inner == w:
        return sys.maxsize
    if visited[i_inner * 20 + j_inner]:
        return sys.maxsize
    if S_inner[i_inner][j_inner] == "#":
        return sys.maxsize
    visited[i_inner * 20 + j_inner] = True
    if shortest_steps_map[i_inner * 20 + j_inner] > steps:
        shortest_steps_map[i_inner * 20 + j_inner] = steps
    get_shortest_steps(S_inner, copy.copy(visited), i_inner + 1, j_inner, l, m, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner + 1, l, m, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner - 1, j_inner, l, m, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner - 1, l, m, steps + 1)
    # print(returned_steps1, returned_steps2, returned_steps3, returned_steps4)
    return


result = -1
for i_outer in range(h):
    for j_outer in range(w):
        visited_outer = [False] * (h * 20 + w + 1)
        shortest_steps_map = [500] * (h * 20 + w + 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer + 1, j_outer, i_outer, j_outer, 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer + 1, i_outer, j_outer, 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer - 1, j_outer, i_outer, j_outer, 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer - 1, i_outer, j_outer, 1)

        for i in range(len(shortest_steps_map)):
            if shortest_steps_map[i] == 500:
                shortest_steps_map[i] = 0

#         print(shortest_steps_map)
#         print(max(shortest_steps_map))
        if max(shortest_steps_map) > result:
            result = max(shortest_steps_map)
print(result)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    from collections import deque

    dist = [0]*(H*W)
    for s in range(H*W):
        search_list = deque([s])
        visited_set = set([])
        d = [0] * (H*W)
        while search_list:
            now = search_list.popleft()
            visited_set.add(now)
            h = now // W
            w = now % W
            if S[h][w] == '#':
                continue
            for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                new_h = h+i
                new_w = w+j
                new_s = new_h * W + new_w
                if new_h in [-1, H] or new_w in [-1, W]:
                    continue
                elif new_s in search_list:
                    continue
                elif new_s in visited_set:
                    continue
                else:
                    d[new_s] = d[now]+1
                    search_list.append(new_s)
        dist[s] = max(d)
    print(max(dist))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
cmd = [[-1,0],[1,0],[0,1],[0,-1]]
h,w = map(int,input().split())
Map = [["#"]*(w+2)]
for _ in range(h):
    s = ["#"]+list(input())[:-1]+["#"]
    Map.append(s)
Map.append(["#"]*(w+2))
MAX = 0
for sx in range(1,w+1):
    for sy in range(1,h+1):
        p = 0
        if Map[sy][sx] == "#":
            continue
        q = deque([[sx,sy]])
        visidat = [[0]*(w+2) for _ in range(h+2)]
        while len(q) != 0:
            x,y = q.popleft()
            for cx,cy in cmd:
                newx = x + cx
                newy = y + cy
                if Map[newy][newx] == "#":
                    continue
                else:
                    if visidat[newy][newx] == 0:
                        visidat[newy][newx] += visidat[y][x] + 1
                        if p < visidat[newy][newx]:
                            p = visidat[newy][newx]
                        q.append([newx,newy])
        MAX = max(MAX,p)
print(MAX)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
cmd = [[-1,0],[1,0],[0,1],[0,-1]]
h,w = map(int,input().split())
Map = [["#"]*(w+2)]
for _ in range(h):
    s = ["#"]+list(input())[:-1]+["#"]
    Map.append(s)
Map.append(["#"]*(w+2))
MAX = 0
for sx in range(1,w+1):
    for sy in range(1,h+1):
        p = -1
        if Map[sy][sx] == "#":
            continue
        q = deque([[sx,sy]])
        visidat = [[0]*(w+2) for _ in range(h+2)]
        while len(q) != 0:
            x,y = q.popleft()
            for cx,cy in cmd:
                newx = x + cx
                newy = y + cy
                if Map[newy][newx] == "#":
                    continue
                else:
                    if visidat[newy][newx] == 0:
                        visidat[newy][newx] += visidat[y][x] + 1
                        if p < visidat[newy][newx]:
                            p = visidat[newy][newx]
                        q.append([newx,newy])
        MAX = max(MAX,p)
print(MAX)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
cmd = [[-1,0],[1,0],[0,1],[0,-1]]
h,w = map(int,input().split())
Map = [["#"]*(w+2)]
for _ in range(h):
    s = ["#"]+list(input())[:-1]+["#"]
    Map.append(s)
Map.append(["#"]*(w+2))
MAX = 0
for sx in range(1,w+1):
    for sy in range(1,h+1):
        for gx in range(1,w+1):
            for gy in range(1,h+1):
                p = -1
                if Map[sy][sx] == "#" or Map[gy][gx] == "#":
                    continue
                q = deque([[sx,sy]])
                visidat = [[0]*(w+2) for _ in range(h+2)]
                while len(q) != 0:
                    x,y = q.popleft()
                    for cx,cy in cmd:
                        newx = x + cx
                        newy = y + cy
                        if Map[newy][newx] == "#":
                            continue
                        else:
                            if visidat[newy][newx] == 0:
                                visidat[newy][newx] += visidat[y][x] + 1
                                q.append([newx,newy])
                            if newx == gx and newy == gy:
                                p = visidat[newy][newx]
                MAX = max(MAX,p)
print(MAX)

Submission status: Wrong Answer

Solution code:
from  collections import deque
H,W=list(map(int,input().split()))
S=[list(input()) for i in range(H)]
dxdy=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
for w in range(W):
    for h in range(H):
        temp=0
        stack=deque([[h,w]])
        visited=[[-1 for i in range(W)]for j in range(H)]
        visited[h][w]=0
        while stack:
            x,y=stack.popleft()
            for i in dxdy:
                nx,ny=x+i[0],y+i[1]
                if 0<=nx<H and 0<=ny<W and S[nx][ny]!='#'and visited[nx][ny]==-1:
                    stack.append([nx,ny])
                    visited[nx][ny]=visited[x][y]+1
        temp=max([j for i in visited for j in i])
        ans=max(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
import sys
sys.setrecursionlimit(1000)
a,b=map(int,input().split())
maze=[list(input()) for i in range(a)]
ans=0
for i in range(a):
  for j in range(b):
    l=copy.deepcopy(maze)
    if l[i][j]=="#":
      break
    l[i][j]=0
    q=deque([[i,j]])
    while q:
      h,w=q.popleft()
      if 0<=h-1<a and 0<=w<b:
        if l[h-1][w]==".":
          l[h-1][w]=l[h][w]+1
          q.append([h-1,w])
      if 0<=h+1<a and 0<=w<b:
        if l[h+1][w]==".":
          l[h+1][w]=l[h][w]+1
      if 0<=h<a and 0<=w-1<b:
        if l[h][w-1]==".":
          l[h][w-1]=l[h][w]+1
          q.append([h,w-1])
      if 0<=h<a and 0<=w+1<b:
        if l[h][w+1]==".":
          l[h][w+1]=l[h][w]+1
          q.append([h,w+1])
    s=0
    for x in l:
      for y in x:
        if type(y)==int:
          if y>s:
            s=y
    if ans<s:
      ans=s
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
a,b=map(int,input().split())
maze=[list(input()) for i in range(a)]
ans=0
for i in range(a):
  for j in range(b):
    l=copy.deepcopy(maze)
    l[i][j]=0
    q=deque([[i,j]])
    while q:
      h,w=q.popleft()
      if 0<=h-1<a and 0<=w<b:
        if l[h-1][w]==".":
          l[h-1][w]=l[h][w]+1
          q.append([h-1,w])
      if 0<=h+1<a and 0<=w<b:
        if l[h+1][w]==".":
          l[h+1][w]=l[h][w]+1
          q.append([h+1,w])
      if 0<=h<a and 0<=w-1<b:
        if l[h][w-1]==".":
          l[h][w-1]=l[h][w]+1
          q.append([h,w-1])
      if 0<=h<a and 0<=w+1<b:
        if l[h][w+1]==".":
          l[h][w+1]=l[h][w]+1
          q.append([h,w+1])
    s=0
    for x in l:
      for y in x:
        if type(y)==int:
          if y>s:
            s=y
    if ans<s:
      ans=s
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(meiro, start_x, start_y):

    visited = []
    for i in range(len(meiro)):
        visited.append([])
        for j in range(len(meiro[i])):
            visited[i].append(0)

    stack = deque()
    stack.append([start_x, start_y])
    visited[start_x][start_y] = 0
    max_distance = 0
    while len(stack) != 0:
        x, y = map(int, stack.popleft())
        distance = visited[x][y]
        if x > 0 and visited[x-1][y] == 0 and meiro[x-1][y] == ".":
            stack.append([x-1, y])
            visited[x-1][y] = distance+1
            if max_distance < distance+1:
                max_distance = distance+1
        if y > 0 and visited[x][y-1] == 0 and meiro[x][y-1] == ".":
            stack.append([x, y-1])
            visited[x][y-1] = distance+1
            if max_distance < distance + 1:
                max_distance = distance + 1
        if x < H-1 and visited[x+1][y] == 0 and meiro[x+1][y] == ".":
            stack.append([x+1, y])
            visited[x+1][y] = distance+1
            if max_distance < distance + 1:
                max_distance = distance + 1
        if y < W-1 and visited[x][y+1] == 0 and meiro[x][y+1] == ".":
            stack.append([x, y+1])
            visited[x][y+1] = distance+1
            if max_distance < distance + 1:
                max_distance = distance + 1
    return max_distance

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

max_distance = 0
for h in range(H):
    for w in range(W):
        if meiro[h][w] == ".":
            dis = bfs(meiro, h, w)
            if max_distance < dis:
                max_distance = dis
print(max_distance)

Submission status: Wrong Answer

Solution code:
from collections import deque

from sys import stdin, setrecursionlimit


def main():
    h, w = map(int, stdin.readline().split())
    g = [list(map(str, list(input()))) for _ in range(h)]

    ans = 0

    for i in range(h):
        for j in range(w):
            d = [[-1 for _ in range(w)] for _ in range(h)]
            q = deque()

            d[i][j] = 0
            q.append([i, j])

            while q:
                vi, vj = q.popleft()

                if vi > 0:
                    if g[vi - 1][vj] == '.' and d[vi - 1][vj] == -1:
                        d[vi - 1][vj] = d[vi][vj] + 1
                        q.append([vi - 1, vj])
                if vi < h - 1:
                    if g[vi + 1][vj] == '.' and d[vi + 1][vj] == -1:
                        d[vi + 1][vj] = d[vi][vj] + 1
                        q.append([vi + 1, vj])
                if vj > 0:
                    if g[vi][vj - 1] == '.' and d[vi][vj - 1] == -1:
                        d[vi][vj - 1] = d[vi][vj] + 1
                        q.append([vi, vj - 1])
                if vj < w - 1:
                    if g[vi][vj + 1] == '.' and d[vi][vj + 1] == -1:
                        d[vi][vj + 1] = d[vi][vj] + 1
                        q.append([vi, vj + 1])
            tmp_max = 0
            for i in range(h):
                for j in range(w):
                    tmp_max = max(tmp_max, d[i][j])
            ans = max(ans, tmp_max)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

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

mp = [ '' for j in range(w * h)]
j = 0

for i in range (h) :
    tmp1 = list(input())
    for j in range (w) :
        mp[w * i + j] = tmp1[j]

def bfs (k) :
    used = [False for i in range(h * w)]
    q = [k]
    used[k] = True
    depth = [0 for i in range (h * w)]

    while len(q) > 0 :
        tmp = q.pop(0)
        if tmp > w and mp[tmp - w] == '.' and used[tmp - w] == False:
            q.append (tmp - w)
            used[tmp - w] = True
            depth [tmp - w] = depth[tmp] + 1

        if tmp < (h - 1) * w and mp[tmp + w] == '.' and used[tmp + w] == False :
            q.append (tmp + w)
            used[tmp + w] = True
            depth [tmp + w] = depth[tmp] + 1

        if tmp % w != 0 and mp[tmp - 1] == '.' and used[tmp - 1] == False :
            q.append (tmp - 1)
            used[tmp - 1] = True
            depth [tmp - 1] = depth[tmp] + 1

        if (tmp + 1) % w != 0 and mp[tmp + 1] == '.'and used[tmp + 1] == False :
            q.append (tmp + 1)
            used[tmp + 1] = True
            depth [tmp + 1] = depth[tmp] + 1
    
    mx = max(depth)

    return mx

ans = 0 

for i in range (h * w) :
    if mp[i] == '.' :
        ans = max(ans , bfs(i))

print (ans)

Submission status: Wrong Answer

Solution code:
def main():    
    import copy
    h,w=map(int,input().split())
    maze=[list(input()) for _ in range(h)]
    df=[(1,0),(-1,0),(0,1),(0,-1)]
    ans=0
    for a in range(h):
      for b in range(w):
          if maze[a][b]=='#':
            continue
          pos=[[a,b,0]]
          meiro=copy.deepcopy(maze)
          while len(pos):
            x,y,depth=pos.pop(0)
            ans=max(ans,depth)
            meiro[x][y]='#'
            flag=False
            for dx,dy in df:
              if 0<=x+dx<h and 0<=y+dy<w and meiro[x+dx][y+dy]=='.':
                  pos.append([x+dx,y+dy,depth+1])
                  flag=True
            if flag==False:
              break
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
import copy
h,w=map(int,input().split())
maze=[list(input()) for _ in range(h)]
df=[(1,0),(-1,0),(0,1),(0,-1)]
ans=0
for a in range(h):
  for b in range(w):
      if maze[a][b]=='#':
        continue
      pos=[[a,b,0]]
      meiro=copy.deepcopy(maze)
      while len(pos):
        x,y,depth=pos.pop(0)
        ans=max(ans,depth)
        meiro[x][y]='#'
        flag=False
        for dx,dy in df:
          if 0<=x+dx<h and 0<=y+dy<w and meiro[x+dx][y+dy]=='.':
              pos.append([x+dx,y+dy,depth+1])
              flag=True
        if flag==False:
          break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
if __name__ == "__main__":
    h, w = map(int, input().split())
    s = []

    for _ in range(h):
        h_i = input()
        s.append(h_i)

    
    ans = (-1)*float('inf')
    
    
    for s_r in range(h):
        for s_c in range(w):
            visited = []
            for _ in range(h):
                w_i = [False] * w
                visited.append(w_i)
            d = deque()
            d.appendleft((s_r, s_c, 0))
            part = 0
            while d:
                now = d.pop()
                visited[now[0]][now[1]] = True
                part = max(now[2], part)
                if now[0] + 1 < h and s[now[0] + 1][now[1]] != "#" and not visited[now[0] + 1][now[1]]:
                    d.appendleft((now[0] + 1, now[1], now[2] + 1))
                if now[0] - 1 >= 0 and s[now[0] - 1][now[1]] != "#" and not visited[now[0] - 1][now[1]]:
                    d.appendleft((now[0] - 1, now[1], now[2] + 1))
                if now[1] + 1 < w and s[now[0]][now[1] + 1] != "#" and not visited[now[0]][now[1] + 1]:
                    d.appendleft((now[0], now[1]+1, now[2] + 1))
                if now[1] - 1 >= 0 and s[now[0]][now[1] - 1] != "#" and not visited[now[0]][now[1] - 1]:
                    d.appendleft((now[0], now[1] - 1, now[2] + 1))
            if ans < part:
                ans = part
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
S= [[0]* W for _ in range(H)]
for i in range(H):
  S[i] = list("".join(input()))


def BFS(i,j):
  v= deque([[i,j]])
  d= [[-1 for _ in range (W)] for _ in range(H)]
  d[i][j]=0
  
  while len(v)>0:
    a=v.popleft()
    s=a[0]
    t=a[1]
    if s>0:
      if d[s-1][t]==-1 and S[s-1][t]==".":
        d[s-1][t]= d[s][t]+1
        v.append([s-1,t])
    if s<H-1:
      if d[s+1][t]==-1 and S[s+1][t]==".":
        d[s+1][t]= d[s][t]+1
        v.append([s+1,t])
    if t>0:
      if d[s][t-1]==-1 and S[s][t-1]==".":
        d[s][t-1]= d[s][t]+1
        v.append([s,t-1])
    if t<W-1:
      if d[s][t+1]==-1 and S[s][t+1]==".":
        d[s][t+1]= d[s][t]+1
        v.append([s,t+1])
  maxi=0
  for i in range(H):
    for j in range(W):
      maxi=max(maxi,d[i][j])
  #print(d)
  return maxi

ans=0
for i in range(0,H):
  for j in range(0,W):
    #print(i,j,BFS(i,j))
    ans=max(ans,BFS(i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
S= [[0]* W for _ in range(H)]
d= [[-1 for _ in range (W)] for _ in range(H)]
for i in range(H):
  S[i] = list("".join(input()))


def BFS(i,j):
  v= deque([[i,j]])
  d[i][j]=0
  
  while len(v)>0:
    a=v.popleft()
    s=a[0]
    t=a[1]
    if s>0:
      if d[s-1][t]==-1 and S[s-1][t]==".":
        d[s-1][t]= d[s][t]+1
        v.append([s-1,t])
    if s<H-1:
      if d[s+1][t]==-1 and S[s+1][t]==".":
        d[s+1][t]= d[s][t]+1
        v.append([s+1,t])
    if t>0:
      if d[s][t-1]==-1 and S[s][t-1]==".":
        d[s][t-1]= d[s][t]+1
        v.append([s,t-1])
    if t<W-1:
      if d[s][t+1]==-1 and S[s][t+1]==".":
        d[s][t+1]= d[s][t]+1
        v.append([s,t+1])
  maxi=0
  for y in d:
    for x in y:
      maxi=max(maxi,x)
  return maxi

ans=0
for j in range(H):
  for j in range(W):
    ans=max(ans,BFS(i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(input()))
directions = [[-1,0],[1,0],[0,-1],[0,1]]
ans = []

for j in range(h):
    for k in range(w):
        if ma[j][k] == '#':
            continue

        bfs = [[-1]*w for _ in range(h)]
        bfs[j][k] = 0
        que = [[j,k]]

        while len(que)>0:
            s,t = que.pop(0)
            for x,y in directions:
                if s+x < 0 or s+x>=h or t+y<0 or t+y>=w:
                    continue
                if ma[s+x][t+y] == '#':
                    continue
                if bfs[s+x][t+y] != 0:
                    continue
                bfs[s+x][t+y] = bfs[s][t] + 1
                que.append([s+x,t+y])
        
        tmp = 0
        for bf in bfs:
            for b in bf:
                if b>tmp:
                    tmp = b
        ans.append(tmp)
print(max(ans))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(input()))
directions = [[-1,0],[1,0],[0,-1],[0,1]]
ans = []

for j in range(h):
    for k in range(w):
        if ma[j][k] == '#':
            continue

        bfs = [[-1]*w for _ in range(h)]
        bfs[j][k] = 0
        que = [[j,k]]

        while len(que)>0:
            s,t = que.pop(0)
            for x,y in directions:
                if s+x < 0 or s+x>=h or t+y<0 or t+y>=w:
                    continue
                if ma[s+x][t+y] == '#':
                    continue
                if bfs[s+x][t+y] > 0:
                    continue
                bfs[s+x][t+y] = bfs[s][t] + 1
                que.append([s+x,t+y])
        
        tmp = 0
        for bf in bfs:
            for b in bf:
                if b>tmp:
                    tmp = b
        ans.append(tmp)
print(max(ans))

Submission status: Wrong Answer

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

for i in range(h):
    maze.append(list(input()))

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


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    queue = deque([start])
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.popleft()

        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        for p in move:
            next_x = x + p[0]
            next_y = y + p[1]
            if (next_x < 0)or(next_x == h)or(next_y < 0)or(next_y == w):
                continue
            if not check[next_x][next_y]:
                check[next_x][next_y] = True
                if maze[next_x][next_y] == ".":
                    queue.append([next_x, next_y, x, y])

    return res


ans = -1

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

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
S = ["#"*(W+1)] + ["#"+input()+"#" for _ in range(H)] + ["#"*(W+1)]
adj = [[[[float("inf")] * W for _ in range(H)] for _ in range(W)] for _ in range(H)]
for h in range(H):
    for w in range(W):
        if S[h+1][w+1] != ".":
            continue
        adj[h][w][h][w] = 0
        for dh, dw in zip((0, 1, 0, -1), (1, 0, -1, 0)):
            if S[h+dh+1][w+dw+1] == ".":
                adj[h][w][h+dh][w+dw] = 1

from itertools import product
for (h1, h2, h3), (w1, w2, w3) in product(product(range(H), repeat=3), product(range(W), repeat=3)):
    adj[h1][w1][h3][w3] = min(adj[h1][w1][h3][w3], adj[h1][w1][h2][w2]+adj[h2][w2][h3][w3])

print(max(filter(lambda x: x != float('inf'), (adj[h1][w1][h2][w2] for (h1, w1), (h2, w2) in product(product(range(H), range(W)), repeat=2)))))

Submission status: Wrong Answer

Solution code:
from collections import deque


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

moves = [[-1,0], [1,0], [0,-1], [0,1]]



min_val = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        todo = deque([[i,j]])
        
        shortest = [[-10e+10 for _ in range(W)] for _ in range(H)]
        shortest[i][j] = 0
        
        while len(todo) > 0:
            print(todo)
            checking = todo.popleft()
            for move in moves:
                if checking[0] + move[0] >= 0 and checking[0] + move[0] < H and checking[1] + move[1] >= 0 and checking[1] + move[1] < W:
                    if shortest[checking[0]+move[0]][checking[1]+move[1]] == -10e+10 and S[checking[0]+move[0]][checking[1]+move[1]] == ".":
                        shortest[checking[0]+move[0]][checking[1]+move[1]] = shortest[checking[0]][checking[1]]+1
                        todo.append([checking[0]+move[0],checking[1]+move[1]])
        if min_val < max([max(row) for row in shortest]):
            min_val = max([max(row) for row in shortest])
print(min_val)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
graph = [['#'] * (W+2) for _ in range(H+2)]
for i in range(H):
  S = input()
  for j in range(W):
    graph[i+1][j+1] = S[j]

def dfs(sx, sy, gx, gy):
  q = deque([(sx, sy)])
  dist = [[-1] * (W+2) for _ in range(H+2)]
  dist[sx][sy] = 0
  while q:
    x, y = q.popleft()
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for dx, dy in dxy:
      nextx = x+dx
      nexty = y+dy
      if(dist[nextx][nexty] >= 0):
        continue
      if(graph[nextx][nexty] == '#'):
        continue
      dist[nextx][nexty] = dist[x][y] + 1
      q.append((nextx, nexty))
  return dist[gx][gy]

ans = 0  
for sx in range(1, H+1):
  for sy in range(1, W+1):
    for gx in range(sx, H+1):
      for gy in range(sy, W+1):
        if(graph[sx][sy] == '.' and graph[gx][gy] == '.'):
          tmp = dfs(sx, sy, gx, gy)
          ans = max(ans, tmp)
          
print(ans)