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 copy
H,W=map(int,input().split())

maze=[]
for h in range(H):
    maze_e=input()
    lis=[]
    for e in maze_e:
        if e=="#":
            lis.append(999)
        else:
            lis.append(-1)

    maze.append(lis)

maze_ori=copy.deepcopy(maze)

maxd=0

for h in range(H):
    for w in range(W):
        maze=copy.deepcopy(maze_ori)
        if maze[h][w]==-1:
            maze[h][w]=0
            while min(min(maze))==-1:
                for hi in range(H):
                    for wi in range(W):
                        if maze[hi][wi]==-1:
                            e_list=[]
                            if hi>0:
                                a=maze[hi-1][wi]
                                if a!=-1 and a!=999:
                                    e_list.append(a)

                            if hi<H-1:
                                a=maze[hi+1][wi]
                                if a!=-1 and a!=999:
                                    e_list.append(a)

                            if wi>0:
                                a=maze[hi][wi-1]
                                if a!=-1 and a!=999:
                                    e_list.append(a)

                            if wi<W-1:
                                a=maze[hi][wi+1]
                                if a!=-1 and a!=999:
                                    e_list.append(a)

                            if len(e_list) >0:
                                maze[hi][wi]=min(e_list)+1
        

            for hi in range(H):
                for wi in range(W):
                    if maze[hi][wi]!=999:
                        maxd=max(maxd,maze[hi][wi])
        
print(maxd)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S=[['' for i in range(W)] for j in range(H)]
index=[[0 for i in range(W)] for j in range(H)]
LUT = list(range(1))
LUT[0] = 0

for i in range(H):
  column=list(input())
  for j in range(W):
    S[i][j]=column[j]

for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      up=S[i][j-1]
      left=S[i-1][j]
      leftIndex=index[i-1][j]
      upIndex=index[i][j-1]

      #上と左どちらも#の場合
      if up=="#" or j-1<0:
        if left == "#" or i-1<0:
          newIndex = len(LUT)
          LUT.append(newIndex)
          index[i][j] = newIndex
          continue
      #左が白の場合
      if up=="#" or j-1<0:
        if left == ".":
          index[i][j] = leftIndex
          continue

      #上が白の場合
      if up==".":
        if left == "#" or i-1<0:
          index[i][j] = upIndex
          continue

      #上と左どちらも白の場合
      if up=="." and left==".":
        if LUT[upIndex]<LUT[leftIndex]:
          index[i][j] = LUT[upIndex]
          keyLUT = LUT[leftIndex]
          for k in range(len(LUT)):
            if LUT[k]==keyLUT:
              LUT[k] = LUT[upIndex]
        else:
          index[i][j] = LUT[leftIndex]
          keyLUT = LUT[upIndex]
          for k in range(len(LUT)):
            if LUT[k]==keyLUT:
              LUT[k] = LUT[leftIndex]

indexCount = 0;
for i in range(len(LUT)):
  if LUT[i]>indexCount:
    keyLUT = LUT[i]
    indexCount += 1
    for j in range(len(LUT)):
      if LUT[j]==keyLUT:
        LUT[j]=indexCount

for i in range(H):
  for j in range(W):
    index[i][j] = LUT[index[i][j]]

LUTcount=[0 for i in range(len(LUT))]
for i in range(H):
  for j in range(W):
    LUTcount[index[i][j]]+=1
maxIndex=LUTcount.index(max(LUTcount[1:]))
rectLUT=[0,0,0,0]
for i in range(H):
  for j in range(W):
    if index[i][j]==maxIndex:
      rectLUT[0] = i;
      rectLUT[1] = j;
      rectLUT[2] = i;
      rectLUT[3] = j;
for i in range(H):
  for j in range(W):
    if i<rectLUT[0]: rectLUT[0] = i
    if j<rectLUT[1]: rectLUT[1] = j
    if i>rectLUT[2]: rectLUT[2] = i
    if j>rectLUT[3]: rectLUT[3] = j

print((rectLUT[2]-rectLUT[0])+(rectLUT[3]-rectLUT[1]))

Submission status: Wrong Answer

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

vec = [(-1,0),(1,0),(0,1),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        stack = [(i,j)]
        visited = [[0]*w for i in range(h)]
        a[i][j] = 0
        
        while stack:
            next = []
            for x,y in stack:
                
                if visited[x][y]:continue

                visited[x][y] = 1
                

                for tx,ty in vec:
                    nx = x+tx
                    ny = y+ty
                    if nx < 0 or ny <0 or nx >=h or ny >=w:continue
                    if field[nx][ny] == "#" :continue
                    if visited[nx][ny]:continue
                    next.append((nx,ny))
                    a[nx][ny] = min(a[x][y] + 1,a[nx][ny])
                    
                    
            stack = next
   
        for i in range(h):
            ans = max(ans,max(a[i]))
            a[i] = [10**4]*w
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S=[['' for i in range(W)] for j in range(H)]
index=[[0 for i in range(W)] for j in range(H)]
LUT = list(range(1))
LUT[0] = 0

for i in range(H):
  column=list(input())
  for j in range(W):
    S[i][j]=column[j]

for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      up=S[i][j-1]
      left=S[i-1][j]
      leftIndex=index[i-1][j]
      upIndex=index[i][j-1]

      #上と左どちらも#の場合
      if up=="#" or j-1<0:
        if left == "#" or i-1<0:
          newIndex = len(LUT)
          LUT.append(newIndex)
          index[i][j] = newIndex
          continue
      #左が白の場合
      if up=="#" or j-1<0:
        if left == ".":
          index[i][j] = leftIndex
          continue

      #上が白の場合
      if up==".":
        if left == "#" or i-1<0:
          index[i][j] = upIndex
          continue

      #上と左どちらも白の場合
      if up=="." and left==".":
        if LUT[upIndex]<LUT[leftIndex]:
          index[i][j] = LUT[upIndex]
          keyLUT = LUT[leftIndex]
          for k in range(len(LUT)):
            if LUT[k]==keyLUT:
              LUT[k] = LUT[upIndex]
        else:
          index[i][j] = LUT[leftIndex]
          keyLUT = LUT[upIndex]
          for k in range(len(LUT)):
            if LUT[k]==keyLUT:
              LUT[k] = LUT[leftIndex]

indexCount = 0;
for i in range(len(LUT)):
  if LUT[i]>indexCount:
    keyLUT = LUT[i]
    indexCount += 1
    for j in range(len(LUT)):
      if LUT[j]==keyLUT:
        LUT[j]=indexCount

for i in range(H):
  for j in range(W):
    index[i][j] = LUT[index[i][j]]

LUTcount=[0 for i in range(len(LUT))]
for i in range(H):
  for j in range(W):
    LUTcount[index[i][j]]+=1
maxIndex=LUTcount.index(max(LUTcount[1:]))
rectLUT=[0,0,0,0]
for i in range(H):
  for j in range(W):
    if index[i][j]==maxIndex:
      rectLUT[0] = i;
      rectLUT[1] = j;
      rectLUT[2] = i;
      rectLUT[3] = j;
for i in range(H):
  for j in range(W):
    if i<rectLUT[0]: rectLUT[0] = i
    if j<rectLUT[1]: rectLUT[1] = j
    if i>rectLUT[2]: rectLUT[2] = i
    if j>rectLUT[3]: rectLUT[3] = j
print(rectLUT)
print((rectLUT[2]-rectLUT[0])+(rectLUT[3]-rectLUT[1]))

Submission status: Wrong Answer

Solution code:
import copy


def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    for start_i in range(len(points) - 1):
        for goal_i in range(start_i + 1, len(points)):
            max_step = max(max_step, count_step(MAP, points[start_i], points[goal_i]))

    print(max_step)


def count_step(MAP, start, goal):
    MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    candidates = [(start, get_distance(start, goal), 0)]

    checked = {}
    while True:
        pos, _, step = candidates.pop(0)
        for m in MOVES:
            next_pos = move(pos, m)
            if not is_valid(MAP, next_pos):
                continue
            if next_pos in checked:
                continue
            checked[next_pos] = True
            distance = get_distance(next_pos, goal)
            if distance == 0:
                return step + 1
            candidates.append((next_pos, distance, step + 1))
        candidates.sort(key=lambda x: x[1])


def move(pos, move):
    return (pos[0] + move[0], pos[1] + move[1])


def get_distance(p, goal):
    return abs(p[0] - goal[0]) + abs(p[1] - goal[1])


def is_valid(MAP, pos):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= len(MAP) or pos[1] >= len(MAP[0]):
        return False

    if MAP[pos[0]][pos[1]] == '#':
        return False
    return True


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
for i in range(h):
    for j in range(w):
        if l[i][j]=='.':
            s=[i,j]
v=[[0 for i in range(w)] for j in range(h)]       
v[s[0]][s[1]]=1
mc=0
ms=s
q=[[s,0]]
while len(q):
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            if mc<c+1:
                mc=c+1
                ms=[nx,ny]
v=[[0 for i in range(w)] for j in range(h)]       
v[ms[0]][ms[1]]=1
ans=0
q=[[ms,0]]
while len(q):
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            ans=max(ans,c+1)
                #ms=[nx,ny]
print(ans)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
from collections import deque
import sys
import copy
input = sys.stdin.readline

sys.setrecursionlimit(10000)

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


maze = []
for i in range(H):
    w_maze = list(input().replace('\n', ''))
    maze.append(w_maze)

# print(maze)


def solve_maze(maze, start, goal):
    q = deque()

    q.append((0, start[0], start[1]))

    # pprint(q)

    while q:
        count, y, x = q.popleft()
        # print(count, y, x)
        for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            # print('now_position:{} {}, next_direction:{} {}, next_position:{} {}'.format(y, x, dy, dx, y + dy, x + dx))
            # print('y+dy, x+dx, maze[y+dy][x+dx])
            if y + dy < 0 or y + dy > H - 1 or x + dx < 0 or x + dx > W - 1:
                continue
            elif maze[y + dy][x + dx] == "#":
                # 壁に対しても何もしない
                continue
            elif maze[y + dy][x + dx] == "x":
                # 探索済みは何もしない
                continue
            elif y + dy == goal[0] and x + dx == goal[1]:
                return count + 1

            maze[y + dy][x + dx] = 'x'
            # print(maze)

            q.append((count + 1, y + dy, x + dx))
    return -1


max_move_count = 0

# startのループ
for y in range(H):
    for x in range(W):
        if maze[y][x] != '.':
            continue
        else:
            # goalのループ
            for goal_y in range(H):
                for goal_x in range(W):
                    if maze[goal_y][goal_x] != '.':
                        continue
                    else:
                        move_count = solve_maze(copy.deepcopy(maze), [y, x], [goal_y, goal_x])
                        max_move_count = max(max_move_count, move_count)

print(max_move_count)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
memo = [[False]*(W+2) for _ in range(H+2)]
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#" or memo[sy][sx]:
      continue
    for ey in range(sy, H+1):
      for ex in range(1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]
INF = 10**9
def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]

ans = []
can = []
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                sx, sy = i, j
                gx, gy = k, l
                # if c[sx][sy] == '#' or c[gx][gy] == '#':
                #     continue
                can.append((sx, sy, gx, gy))

for sx, sy, gx, gy in can:
    ans.append(bfs())
                
ans = [i for i in ans if i != INF]
print(max(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

maze = []
for i in range(h):
  ip = input()
  new_ip = list(ip)
  maze.append(new_ip)
ans_li = []
for i in range(h):
  for j in range(w):
    li = [[-1 for p in range(w)] for q in range(h)]
    li[i][j] = 0
    for k in range(20):
      for p in range(h):
        for q in range(w):
          if li[p][q] != -1 and p + 1 <= h - 1:
            if (li[p + 1][q] >= li[p][q] or li[p + 1][q] == -1) and maze[p+1][q] == ".":
              li[p + 1][q] = li[p][q] + 1
          if li[p][q] != -1 and p - 1 >= 0:
            if (li[p - 1][q] >= li[p][q] or li[p - 1][q] == -1) and maze[p-1][q] == ".":
              li[p - 1][q] = li[p][q] + 1
          if li[p][q] != -1 and q + 1  <= w - 1:
            if (li[p][q + 1] >= li[p][q] or li[p][q + 1] == -1) and maze[p][q+1] == ".":
              li[p][q + 1] = li[p][q] + 1
          if li[p][q] != -1 and q - 1 >= 0:
            if (li[p][q - 1] >= li[p][q] or li[p][q - 1] == -1) and maze[p][q-1] == ".":
              li[p][q - 1] = li[p][q] + 1
          
    ans_li.append(np.max(li))

print(max(ans_li))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

LOAD = '.'
WALL = '#'
NOT_REACHED = -1

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

s = [0] * h
for i in range(h):
    s[i] = input().strip()

def bfs(graph, queue, div):
    _max = 0
    while queue:
        current = queue.pop(0)

        top = (current[0] - 1, current[1])
        bottom = (current[0] + 1, current[1])
        left = (current[0], current[1] - 1)
        right = (current[0], current[1] + 1)

        for target in (top, bottom, left, right):
            if (target[0] < 0) or (target[0] >= h) or (target[1] < 0) or (target[1] >= w):
                continue
            if div[target] != NOT_REACHED:
                continue
            if graph[target[0]][target[1]] == LOAD:
                div[target] = div[current] + 1
                _max = max(div[target], _max)
                queue.append(target)
    return _max

ans = 0
for i in range(h):
    for j in range(w):
        queue = [(i, j)]
        div = {}
        for inner_i in range(h):
            for inner_j in range(w):
                div[(inner_i, inner_j)] = -1
        div[(i, j)] = 0
        ans = max(bfs(s, queue, div), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import deque
from copy import deepcopy
def dfs(B,si,sj, H, W):
    R = [-1]*(H*W)
    R[si*W+sj] = 0
    d = deque([si*W+sj])
    while d:
        p = d.popleft()
        x = p//W
        y = p%W
        t = R[x*W+y]

        if x > 0:
            if B[(x-1)*W+y] == 0:
                if R[(x-1)*W+y] == -1:
                    R[(x-1)*W+y] = t+1
                    d.append((x-1)*W+y)
                elif R[(x-1)*W+y] > t+1:
                    R[(x-1)*W+y] = t+1
                    d.append((x-1)*W+y)
        if x < H-1:
            if B[(x+1)*W+y] == 0:
                if R[(x+1)*W+y] == -1:
                    R[(x+1)*W+y] = t+1
                    d.append((x+1)*W+y)
                elif R[(x+1)*W+y] > t+1:
                    R[(x+1)*W+y] = t+1
                d.append((x+1)*W+y)
        if y > 0:
            if B[x*W+y-1] == 0:
                if R[x*W+y-1] == -1:
                    R[x*W+y-1] = t+1
                    d.append(x*W+y-1)
                elif R[x*W+y-1] > t+1:
                    R[x*W+y-1] = t+1
                    d.append(x*W+y-1)
        if y < W-1:
            if B[x*W+y+1] == 0:
                if R[x*W+y+1] == -1:
                    R[x*W+y+1] = t+1
                    d.append(x*W+y+1)
                elif R[x*W+y+1] > t+1:
                    R[x*W+y+1] = t+1
                    d.append(x*W+y+1)

    return max(R)
    

def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    B = [0]*(H*W)
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                B[i*W+j] = 1
    ans = 0
#    print(dfs(B,i,j,H,W))

    for i in range(H):
        for j in range(W):
            t = dfs(B, i, j, H, W)
            if t > ans:
                ans = t
    print(ans)
            
if __name__ == '__main__':
    main()

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)]

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
  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)]
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
  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]
if ans==INF:
  print(0)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
def calc_distance(maze,sx,sy,gx,gy):
        # mazeをリストに変換
        # Goalまでの距離としてはあり得ない数値を設定
        INF = 100000000

        field_x_length = len(maze[0])
        field_y_length = len(maze)

        # mazeと同じ配列構造ですべての箇所がINFで埋まっている二次元配列を作る
        # startからの距離をこのdistance配列に格納していく
        distance = []
        for i in range(field_y_length):
            distance.append([])
            for j in range(field_x_length):
                distance[i].append(INF)

        # queue配列を作り、ここに座標を格納する
        queue = []

        # queueの末尾にStart座標を入れる
        queue.insert(0, (sy, sx))

        # Startの座標距離は0に設定
        distance[sy][sx] = 0

        # Goalにつくまで以下ループ
        while True:
            # 最初に入れた要素を取り出す
            y, x = queue.pop()

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

            # 新しい座標(ny, nx)に現時点の座標から
            # (0, 1)(1, 0)(0, -1)(-1, 0)移動した値を代入  
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                # 移動先ny, nxが迷路の範囲内
                # かつ壁（maze配列が#）でなく、
                # かつ未到達（distance配列がINF）であるときに
                # 現時点の距離+1をdistance配列に格納する
                # 現時点の座標をqueue配列に格納する（再ループの時にその座標から始める）
                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, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1

        # Goalについたらループを抜け、Goalまでの距離を返す
        return distance[gy][gx]
    
ans = 0
for i in range(H):
    sy = i
    for j in range(W):
        sx = j
        for k in range(H):
            gy = k
            for m in range(W):
                gx = m
        
        
            if maze[sy][sx] == "#" or maze[gy][gx] == "#":
                pass
            else:
                score = calc_distance(maze,sx,sy,gx,gy)
                ans = max(ans,score)
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue
import itertools
def solve():

    H, W = map(int, input().split())
    S = []
    for i in range(H):
        tmp = list(input())
        S.append(tmp)
    
    dw = (1,0,-1,0)
    dh = (0,1,0,-1)

    comb = itertools.combinations(tuple(range(20)), 2)
    mx = 0

    for c in comb:
        
        startH = c[0]
        startW = c[1]
        if startH >= H or startW >= W or S[startH][startW] == '#':
            continue

        q = Queue()
        cur = P(startH, startW)
        q.put(cur)

        time = [[float('inf')] * W for i in range(H)]
        time[startH][startW] = 0

        while not q.empty():
            p = q.get()
            
            for i in range(4):
                nh = p.H + dh[i]
                nw = p.W + dw[i] 
                if 0 <= nh and nh < H and 0 <= nw and nw < W and time[nh][nw] == float('inf') and S[nh][nw] != '#':
                    q.put(P(nh, nw))
                    time[nh][nw] = time[p.H][p.W] + 1
        
        flatten = list(itertools.chain.from_iterable(time))
        for i in range(len(flatten)):
            if flatten[i] == float('inf'):
                flatten[i] = -1 

        localmx = max(flatten)
        mx = max(localmx, mx)

    print(mx)

class P():
    def __init__(self, H, W):
        self.H = H
        self.W = W

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from copy import deepcopy

input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
m = [['#' for _ in range(w+2)] for _ in range(h+2)]

for hi in range(1, h+1):
    for wi, s in enumerate(input().strip(), start=1):
        m[hi][wi] = s
        if s == '.':
            hs, ws = hi, wi

def bfs(hs, ws, m):
    cost = 0
    q = deque([])
    m[hs][ws] = '#'
    for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
        if m[hs+offset[0]][ws+offset[1]] == '.':
            q.append((hs+offset[0], ws+offset[1]))
    while q:
        cost += 1
        q_ = deque(q)
        q = deque([])
        for h, w in q_:
            m[h][w] = '#'
            for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
                if m[h+offset[0]][w+offset[1]] == '.':
                    m[h+offset[0]][w+offset[1]] = '#'
                    q.append((h+offset[0], w+offset[1]))

    return cost, h, w

maxi = -1
maxi_ = 0
while maxi != maxi_:
    maxi_ = maxi
    maxi, hs, ws = bfs(hs, ws, deepcopy(m[:]))

print(maxi)

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])
#    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

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

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

cs = [[100000]*w for _ in range(h)]

q = deque([])

visited1 = [[-1]*w for _ in range(h)]
visited2 = [[-1]*w for _ in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        if visited2[i][j] == -1 and s[i][j] == ".":
            ec = 0
            visited1[i][j] = 0
            q.append((i,j))
            while q:
                now = q.pop()
                for v in vectors:
                    if now[0]+v[0] >= 0 and now[0]+v[0] < h and now[1]+v[1] >= 0 and now[1]+v[1] < w:
                        if s[now[0]+v[0]][now[1]+v[1]] == "." and visited1[now[0]+v[0]][now[1]+v[1]] == -1:
                            q.appendleft((now[0]+v[0], now[1]+v[1]))
                            visited1[now[0]+v[0]][now[1]+v[1]] = visited1[now[0]][now[1]] + 1
                            if visited1[now[0]+v[0]][now[1]+v[1]] > ec:
                                ec = visited1[now[0]+v[0]][now[1]+v[1]]
                                st = (now[0]+v[0], now[1]+v[1])

            q.append(st)
            visited2[st[0]][st[1]] = 0
            while q:
                now = q.pop()
                for v in vectors:
                    if now[0]+v[0] >= 0 and now[0]+v[0] < h and now[1]+v[1] >= 0 and now[1]+v[1] < w:
                        if s[now[0]+v[0]][now[1]+v[1]] == "." and visited2[now[0]+v[0]][now[1]+v[1]] == -1:
                            q.appendleft((now[0]+v[0], now[1]+v[1]))
                            visited2[now[0]+v[0]][now[1]+v[1]] = visited2[now[0]][now[1]] + 1
                            if visited2[now[0]+v[0]][now[1]+v[1]] > ans:
                                ans = visited2[now[0]+v[0]][now[1]+v[1]]

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)]

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
  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 and seen[i][j]!=INF:
        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)]
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
  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 and seen[i][j]!=INF:
        ans=seen[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
for i in range(h):
    for j in range(w):
        if l[i][j]=='.':
            s=[i,j]
v=[[0 for i in range(w)] for j in range(h)]       
v[s[0]][s[1]]=1
mc=0
ms=s
q=[[s,0]]
while q:
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            if mc<c+1:
                mc=c+1
                ms=[nx,ny]
v=[[0 for i in range(w)] for j in range(h)]       
v[ms[0]][ms[1]]=1
ans=0
q=[[ms,0]]
while q:
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            ans=max(ans,c+1)
                #ms=[nx,ny]
print(ans)