Problem:


Score : 400 points

Problem Statement

Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.

The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Wrong Answer

Solution code:
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            else:
                a.append(9999)
        maze.append(a)
    return maze

def maxroot(maze, x, y, w, h):
    maxx = 0
    maze = deepcopy(maze)
    if maze[y][x] is False:
        return 0
    maze[y][x] = 0

    que = deque()
    que.append((y, x))

    while que:
        xy = que.popleft()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd
        maxx = max(dd, maxx)

        for y, x in minlist:
            if maze[y][x] != 9999 and maze[y][x] > dd+1:
                que.append((y, x))
        #print(maze)

    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 1
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    #print(maxroot(maze, 0, 2, W, H))


main()

Submission status: Wrong Answer

Solution code:
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            else:
                a.append(9999)
        maze.append(a)
    return maze

def maxroot(maze, x, y, w, h):
    maxx = 0
    maze = deepcopy(maze)
    if maze[y][x] is False:
        return 0
    maze[y][x] = 0

    que = deque()
    que.append((y, x))

    while que:
        xy = que.popleft()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd
        maxx = max(dd, maxx)

        for y, x in minlist:
            if maze[y][x] != 9999 and maze[y][x] > dd+1:
                que.append((y, x))
        #print(maze)

    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 0
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    #print(maxroot(maze, 0, 2, W, H))


main()

Submission status: Wrong Answer

Solution code:
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            else:
                a.append(9999)
        maze.append(a)
    return maze

def maxroot(maze, x, y, w, h):
    maxx = 0
    maze = deepcopy(maze)
    if maze[y][x] is False:
        return 0
    maze[y][x] = 0

    que = deque()
    que.append((y, x))

    while que:
        xy = que.popleft()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd
        maxx = max(dd, maxx)

        for y, x in minlist:
            if maze[y][x] != 9999 and maze[y][x] > dd:
                que.append((y, x))
        #print(maze)

    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 0
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    #print(maxroot(maze, 0, 2, W, H))


main()

Submission status: Wrong Answer

Solution code:


def read_input():
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]
    cell = lambda x, y : x * w + y

    edges = {}
    for hi in range(h):
        for wi in range(w):
            edges[cell(hi, wi)] = []

            if 0 <= hi - 1:
                if maze[hi - 1][wi] == '.':
                    edges[cell(hi, wi)].append(cell(hi - 1, wi))
            if hi + 1 < h:
                if maze[hi + 1][wi] == '.':
                    edges[cell(hi, wi)].append(cell(hi + 1, wi))
            if 0 <= wi - 1:
                if maze[hi][wi - 1] == '.':
                    edges[cell(hi, wi)].append(cell(hi, wi - 1))
            if wi + 1 < w:
                if maze[hi][wi + 1] == '.':
                    edges[cell(hi, wi)].append(cell(hi, wi + 1))

    return h, w, edges


def warshall_floyd(h, w, edges):
    v = h * w
    d = [[float('inf') for _ in range(v)] for _ in range(v)]

    for i in range(v):
        d[i][i] = 0

    for f, tlist in edges.items():
        for t in tlist:
            d[f][t] = 1

    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d   
    

def submit():
    h, w, edges = read_input()
    dist = warshall_floyd(h, w, edges)

    max_dist = 0
    v = h * w
    for i in range(v):
        for j in range(v):
            d = dist[i][j]
            if d == float('inf'):
                continue
            if d > max_dist:
                max_dist = d
    print(max_dist)


if __name__ == "__main__":
    submit()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
f = [input() for _ in range(h)]

def next(pos):
    x, y = pos
    ret = []
    for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        i = x + dx
        j = y + dy
        if 0 <= i < h and 0 <= j < w and f[i][j] != '#':
            ret.append((i, j))
    return ret

ans = 0
for i in range(h):
    for j in range(w):
        s = {(i, j)}
        ng = set()
        dis = 0
        while s:
            t = set()
            for p in s:
                ng.add(p)
                for x, y in next(p):
                    if (x, y) not in ng:
                        t.add((x, y))
            s = t
            dis += 1
        ans = max(ans, dis - 1)
print(ans)

Submission status: Wrong Answer

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

def dfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
ans = 0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                ans = max(ans,dfs(sy,sx,gy,gx))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
buf = sys.stdin.buffer

h, w = map(int, buf.readline().split())
map = ""
for _ in range(h):
    map += input() + "#"
#print(map)

n = h * (w + 1)
periods = [[] for _ in range(n)]
dir = [-w - 1, 1, -1, w + 1]
for i in range(n):
    if map[i] == "#":
        continue
    for d in dir:
        next_i = i + d
        if next_i < 0 or next_i >= n or map[next_i] == "#":
            continue
        periods[i].append(next_i)
#print(periods)

q = deque()
def bfs(pos):
    for next_i in periods[pos]:
        if con_cnt[next_i] == -1:
            con_cnt[next_i] = con_cnt[pos] + 1
            q.append(next_i)
        #まだスタックが残っている場合、左から抜き出す
        if len(q) > 0:
            bfs(q.popleft())

start_points = [i for i, j in enumerate(periods) if len(j) > 0]
ans = 0
for start_point in start_points:
    con_cnt = [-1] * n
    con_cnt[start_point] = 0
    bfs(start_point)
    ans = max(ans, max(con_cnt))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
buf = sys.stdin.buffer

h, w = map(int, buf.readline().split())
map = ""
for _ in range(h):
    map += input() + "#"
#print(map)

n = h * (w + 1)
periods = [[] for _ in range(n)]
dir = [-w - 1, 1, -1, w + 1]
for i in range(n):
    if map[i] == "#":
        continue
    for d in dir:
        next_i = i + d
        if next_i < 0 or next_i >= n or map[next_i] == "#":
            continue
        periods[i].append(next_i)
#print(periods)

q = deque()
def bfs(pos):
    for next_i in periods[pos]:
        if con_cnt[next_i] == -1:
            con_cnt[next_i] = con_cnt[pos] + 1
            q.append(next_i)
        #まだスタックが残っている場合、左から抜き出す
        if q:
            bfs(q.popleft())

start_points = [i for i, j in enumerate(periods) if len(j) > 0]
ans = 0
for start_point in start_points:
    con_cnt = [-1] * n
    con_cnt[start_point] = 0
    bfs(start_point)
    ans = max(ans, max(con_cnt))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = [input() for _ in range(h)]
from collections import deque
D = [(0,1),(1,0),(-1,0),(0,-1)]
ans = 0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      continue
    queue  = deque([(i,j,0)])
    checked = [[0 for _ in range(w)] for _ in range(h)]
    checked[i][j] = 1
    while queue:
      j,k,d = queue.popleft()
      for dx,dy in D:
        x,y = j+dx,k+dy
        if not(0<=x<h) or not(0<=y<w):
          continue
        if maze[x][y] == '#':
          continue
        if checked[x][y]:
          continue
        checked[x][y] = d+1
        queue.append((x,y,d+1))
    for j in range(h):
      for k in range(w):
        if checked:
          ans = max(ans,checked[j][k])

print(max(2,ans))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = [input() for _ in range(h)]
from collections import deque
D = [(0,1),(1,0),(-1,0),(0,-1)]
ans = 0
for i in range(h):
  for j in range(w):
    queue  = deque([(i,j,0)])
    checked = [[0 for _ in range(w)] for _ in range(h)]
    checked[i][j] = 1
    while queue:
      j,k,d = queue.popleft()
      for dx,dy in D:
        x,y = j+dx,k+dy
        if not(0<=x<h) or not(0<=y<w):
          continue
        if maze[x][y] == '#':
          continue
        if checked[x][y]:
          continue
        checked[x][y] = d+1
        queue.append((x,y,d+1))
    for j in range(h):
      for k in range(w):
        if checked:
          ans = max(ans,checked[j][k])

print(max(2,ans))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = [input() for _ in range(h)]
from collections import deque
D = [(0,1),(1,0),(-1,0),(0,-1)]
ans = 0
for i in range(h):
  for j in range(w):
    queue  = deque([(i,j,0)])
    checked = [[0 for _ in range(w)] for _ in range(h)]
    checked[i][j] = 1
    while queue:
      j,k,d = queue.popleft()
      for dx,dy in D:
        x,y = j+dx,k+dy
        if not(0<=x<h) or not(0<=y<w):
          continue
        if maze[x][y] == '#':
          continue
        if checked[x][y]:
          continue
        checked[x][y] = d+1
        queue.append((x,y,d+1))
    for j in range(h):
      for k in range(w):
        if checked:
          ans = max(ans,checked[j][k])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "#" :
        continue
    else :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != 0 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    dist = [0 for _ in range(H*W)]
    ans = max(ans, bfs(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)]
inf=float('inf')
ans=0
for i in range(h):
      for j in range(w):
            if S[i][j]!='#':
                  dp=[[inf for _ in range(w)]for _ in range(h)]
                  dp[i][j]=0
                  que=deque([(i,j)])
                  while que:
                        si,sj=que.pop()
                        for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                              if 0<=ni<h and 0<=nj<w and S[ni][nj]!='#':
                                    if dp[ni][nj]>dp[si][sj]+1:
                                          dp[ni][nj]=dp[si][sj]+1
                                          ans=max(ans,dp[si][sj]+1)
                                          que.append((ni,nj))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 5000
vx = [-1,0,1,0]
vy = [0,-1,0,1]

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

d = [-1] * (H*W)
xy = lambda x,y: x + y*W

ds = []
for sx in range(W):
    for sy in range(H):
        q = deque([(sx,sy)])
        tmpd = d.copy()
        tmpd[xy(sx,sy)] = 0
        while(q):
            x,y = q.popleft()
            for i in range(4):
                nx = x + vx[i]
                ny = y + vy[i]
                if 0 <= nx and nx < W and 0 <= ny and ny < H and S[ny][nx] != '#' and tmpd[xy(nx,ny)] == -1:
                    q.append((nx,ny))
                    tmpd[xy(nx,ny)] = tmpd[xy(x,y)] + 1
        ds.append(max(tmpd))
print(max(ds))

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
S = list()
for i in range(H):
    S.append(list(input()))
mx = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        q = deque([(i,j,0)])
        T = [[S[k][l] for l in range(W)] for k in range(H)]
        while q:
            x,y,c = q.popleft()
            for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                nx,ny = x+dx,y+dy
                if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == ".":
                    T[nx][ny] = "#"
                    q.append((nx,ny,c+1))
        mx = max(mx,c)
print(mx)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "#" :
        continue
    else :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s, g) :
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != 0 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return dist[g]

ans = 0
for i in range(H*W) :
    for j in range(H*W) :
        dist = [0 for _ in range(H*W)]
        q = deque([i])
        ans = max(ans, bfs(i, j))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def mazesolve(h,w,maze,start):
  visit = [[False]*(w+2) for _ in range(h+2)]
  query = deque([])
  query.append((start,0,visit))
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  ret = 0
  while query:
    place,move,where = query.popleft()
    y,x = place
    if y == 1 or x == 1 or y == h or x == w:
      ret = max(ret,move)
    where[y][x] = True
    for dy,dx in d:
      if maze[y+dy][x+dx] == "#" or where[y+dy][x+dx]:
        continue
      else:
        query.append(((y+dy,x+dx),move+1,where))
     
  return ret
def solve():
  h,w = (int(i) for i in input().split())
  if h == 1 and w == 1:
    print(0)
    exit()
  maze = ["#"*(w+2)]
  for i in range(h):
    maze.append("#" + input() + "#")
  maze.append("#"*(w+2))
  startgoal = []
  for i in range(w+1):
    if maze[1][i] == ".":
      startgoal.append((1,i))
    if maze[h][i] == ".":
      startgoal.append((h,i))
  for i in range(h+1):
    if maze[i][1] == ".":
      startgoal.append((i,1))
    if maze[i][w] == ".":
      startgoal.append((i,w))
  startgoal = sorted(list(set(startgoal)))
  ans = 0
  for i in range(len(startgoal)):
      start = startgoal[i]
      ans = max(ans,(mazesolve(h,w,maze,start)))
  print(ans)


solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
def mazesolve(h,w,maze,start):
  visit = [[False]*(w+2) for _ in range(h+2)]
  query = deque([])
  query.append((start,0,visit))
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  ret = 0
  while query:
    place,move,where = query.popleft()
    y,x = place
    ret = max(ret,move)
    where[y][x] = True
    for dy,dx in d:
      if maze[y+dy][x+dx] == "#" or where[y+dy][x+dx]:
        continue
      else:
        query.append(((y+dy,x+dx),move+1,where))
     
  return ret
def solve():
  h,w = (int(i) for i in input().split())
  if h == 1 and w == 1:
    print(0)
    exit()
  maze = ["#"*(w+2)]
  for i in range(h):
    maze.append("#" + input() + "#")
  maze.append("#"*(w+2))
  startgoal = []
  for i in range(w+1):
    if maze[1][i] == ".":
      startgoal.append((1,i))
    if maze[h][i] == ".":
      startgoal.append((h,i))
  for i in range(h+1):
    if maze[i][1] == ".":
      startgoal.append((i,1))
    if maze[i][w] == ".":
      startgoal.append((i,w))
  startgoal = sorted(list(set(startgoal)))
  ans = 0
  for i in range(len(startgoal)):
      start = startgoal[i]
      ans = max(ans,(mazesolve(h,w,maze,start)))
  print(ans)


solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
def mazesolve(h,w,maze,start):
  visit = [[False]*(w+2) for _ in range(h+2)]
  query = deque([])
  query.append((start,0))
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  ret = 0
  while query:
    place,move = query.popleft()
    y,x = place
    visit[y][x] = True
    for dy,dx in d:
      if maze[y+dy][x+dx] == "#" or visit[y+dy][x+dx]:
        continue
      else:
        ret = max(ret,move+1)
        query.append(((y+dy,x+dx),move+1))
     
  return ret
def solve():
  h,w = (int(i) for i in input().split())
  if h == 1 and w == 1:
    print(0)
    exit()
  maze = ["#"*(w+2)]
  for i in range(h):
    maze.append("#" + input() + "#")
  maze.append("#"*(w+2))
  startgoal = []
  for i in range(w+1):
    if maze[1][i] == ".":
      startgoal.append((1,i))
    if maze[h][i] == ".":
      startgoal.append((h,i))
  for i in range(h+1):
    if maze[i][1] == ".":
      startgoal.append((i,1))
    if maze[i][w] == ".":
      startgoal.append((i,w))
  startgoal = sorted(list(set(startgoal)))
  ans = 0
  for i in range(len(startgoal)):
      start = startgoal[i]
      ans = max(ans,(mazesolve(h,w,maze,start)))
  print(ans)

solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
def mazesolve(h,w,maze,start,goal):
  visit = [[False]*(w+2) for _ in range(h+2)]
  query = deque([])
  query.append((start,0))
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while query:
    place,move = query.popleft()
    y,x = place
    for dy,dx in d:
      if maze[y+dy][x+dx] == "#":
        continue
      else:
        if (y+dy,x+dx) == goal:
           return move+1
        query.append(((y+dy,x+dx),move+1))
  return 0
def solve():
  h,w = (int(i) for i in input().split())
  if h == 1 and w == 1:
    print(0)
    exit()
  maze = ["#"*(w+2)]
  for i in range(h):
    maze.append("#" + input() + "#")
  maze.append("#"*(w+2))
  startgoal = []
  for i in range(w+1):
    if maze[1][i] == ".":
      startgoal.append((1,i))
    if maze[h][i] == ".":
      startgoal.append((h,i))
  for i in range(h+1):
    if maze[i][1] == ".":
      startgoal.append((i,1))
    if maze[i][w] == ".":
      startgoal.append((i,1))
  startgoal = sorted(list(set(startgoal)))
  ans = 0
  for i in range(len(startgoal)-1):
    for j in range(i+1,len(startgoal)):
      start = startgoal[i]
      goal = startgoal[j]
      ans = max(ans,(mazesolve(h,w,maze,start,goal)))
  print(ans)

solve()

Submission status: Wrong Answer

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

maze = [['#']*(W+2)]
for i in range(H):
    maze.append(list('#'+input()+'#'))
maze.append(['#']*(W+2))
ans = 0

for ii in range(1,H+1):
    for jj in range(1,W+1):
        if maze[ii][jj]=='#':continue
        temp = deque()
        temp.append([ii,jj])
        mazenum = [[0]*(W+2) for _ in range(H+2)]
        mazenum[ii][jj] = 0
        visited = [[False]*(W+2) for _ in range(H+2)]
        visited[ii][jj] = True

        while temp:
            p = temp.popleft()
            m = mazenum[p[0]][p[1]]
            for i, j in [[p[0]-1,p[1]], [p[0]+1, p[1]], [p[0],p[1]-1],[p[0],p[1]+1]]:
                if maze[i][j]=='.':
                    if not visited[i][j]:
                        temp.append([i, j])
                        mazenum[i][j] = m + 1
                        visited[i][j]= True        
        ans = max(ans, max(max(mazenum)))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = []
    dh = [0,1,0,-1]
    dw = [1,0,1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            dist = [[-1] * W for _ in range(H)]
            dist[h][w] = 0
            cnt = 0
            Q = deque()
            Q.append([h,w])
            while Q:
                y, x = Q.popleft()
                for i in range(4):
                    nh = y + dh[i]
                    nw = x + dw[i]
                    if 0 <= nh < H and 0 <= nw < W and dist[nh][nw] == -1 and S[nh][nw] == '.':
                        dist[nh][nw] = dist[y][x] + 1
                        Q.append([nh,nw])
            
            for i in range(H):
                cnt = max(cnt, max(dist[i]))

            ans.append(cnt)

    print(max(ans))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            dist = [[-1] * W for _ in range(H)]
            dist[h][w] = 0
            cnt = 0
            Q = deque()
            Q.append([h,w])
            while Q:
                x, y = Q.popleft()
                for i in range(4):
                    nh = x + dh[i]
                    nw = y + dw[i]
                    if 0 <= nh < H and 0 <= nw < W and dist[nh][nw] == -1 and S[nh][nw] == '.':
                        dist[nh][nw] = dist[x][y] + 1
                        Q.append([nh,nw])
            
            for i in range(H):
                ans = max(ans, max(dist[i]))

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            dist = [[float('inf')] * W for _ in range(H)]
            dist[h][w] = 0
            cnt = 0
            Q = deque()
            Q.append([h,w])
            while Q:
                x, y = Q.popleft()
                for i in range(4):
                    nh = x + dh[i]
                    nw = y + dw[i]
                    if 0 <= nh < H and 0 <= nw < W and dist[nh][nw] == float('inf') and S[nh][nw] == '.':
                        dist[nh][nw] = min(dist[x][y] + 1, dist[nh][nw])
                        cnt = max(cnt, dist[nh][nw])
                        Q.append([nh,nw])
            ans = max(ans, cnt)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,1,0]
    for h in range(H):
        for w in range(W):
            dist = [[float('inf')] * W for _ in range(H)]
            dist[h][w] = 0
            cnt = 0
            Q = deque()
            Q.append([h,w])
            while Q:
                x, y = Q.popleft()
                for i in range(4):
                    nh = x + dh[i]
                    nw = y + dw[i]
                    if 0 <= nh < H and 0 <= nw < W and dist[nh][nw] == float('inf') and S[nh][nw] == '.':
                        dist[nh][nw] = min(dist[x][y] + 1, dist[nh][nw])
                        cnt = max(cnt, dist[nh][nw])
                        Q.append([nh,nw])
            ans = max(ans, cnt)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

maze = [['#']*(W+2)]
for i in range(H):
    maze.append(list('#'+input()+'#'))
maze.append(['#']*(W+2))

ans = 0
for ii in range(1,H+1):
    for jj in range(1,W+1):
        if maze[ii][jj]=='#':continue
        temp = deque()
        temp.append([ii,jj])
        mazenum = [[0]*(W+2) for _ in range(H+2)]
        mazenum[ii][jj] = 0
        visited = [[False]*(W+2) for _ in range(H+2)]
        visited[ii][jj] = True

        while temp:
            p = temp.popleft()
            m = mazenum[p[0]][p[1]]
            for i, j in [[p[0]-1,p[1]], [p[0]+1, p[1]], [p[0],p[1]-1],[p[0],p[1]+1]]:
                if maze[i][j]=='.':
                    if not visited[i][j]:
                        temp.append([i, j])
                        mazenum[i][j] = m + 1
                        visited[i][j]=True        
        ans = max(ans, max(max(mazenum)))     

print(ans)

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
x = 0
y = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]


for _ in range(H):
    MAP.append(list(input()))

def bfs(S):
    que = queue.Queue()
    d = [[INF for i in range(W)] for j in range(H)]
    que.put(S)
    d[S[x]][S[y]] = 0
    
    while not que.empty():
        p = que.get()
        for i in range(4):
            nx = p[x] + dx[i]
            ny = p[y] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] != "#" and d[nx][ny] == INF:
                que.put([nx,ny])
                d[nx][ny] = d[p[x]][p[y]] + 1
    
    MAX = -1
    for i in range(H):
        for j in range(W):
            if d[i][j] != INF and MAX < d[i][j]:
                MAX = d[i][j]
                index = [i,j]
    return MAX, index

MAX, START = bfs([0,0])
while True:
    tmp, START = bfs(START)
    if tmp == MAX:
        break
    else:
        MAX = tmp

print(MAX)

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
x = 0
y = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]


for _ in range(H):
    MAP.append(list(input()))

def bfs(S):
    que = queue.Queue()
    d = [[INF for i in range(W)] for j in range(H)]
    que.put(S)
    d[S[x]][S[y]] = 0
    
    while not que.empty():
        p = que.get()
        for i in range(4):
            nx = p[x] + dx[i]
            ny = p[y] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] != "#" and d[nx][ny] == INF:
                que.put([nx,ny])
                d[nx][ny] = d[p[x]][p[y]] + 1
    
    MAX = -1
    for i in range(H):
        for j in range(W):
            if d[i][j] != INF and MAX < d[i][j]:
                MAX = d[i][j]
                index = [i,j]
    return MAX, index

MAX, START = bfs([0,0])
MAX, START = bfs(START)
MAX, GOAL = bfs(START)

print(MAX)