Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Wrong Answer

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

town = []
visited = [[0 for i in range(W)] for j in range(H)]
 
for i in range(H): 
    c = input().strip()
    w = list(c)
    town.append(w)

def getpreStart(h,w):
    for i in range(h):
        for j in range(w):
            if town[i][j] == '.' :
                return i,j
            
def bfs(x,y) :
    q = deque()
    q.append([x,y,0])
    max_dist=0
    s=x
    t=y
    while q : #キューが空でない場合
        tx,ty,dist = q.popleft()
        if visited[ty][tx] == 0 :
            visited[ty][tx] = 1
            if town[ty][tx] == '#' :
                pass
            else :
                #周辺4マスを調べる
                for r in range (4):
                    nx = tx + dx[r]
                    ny = ty + dy[r]
                    count=0
                    if 0 <= nx < W and 0 <= ny < H and visited[ny][nx] == 0:
                        q.append([nx,ny,dist+1])
                        count+=1
                    if count==0 and dist>max_dist:
                        max_dist=dist
                        s=tx
                        t=ty
    return s,t,max_dist
                        
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
sy,sx=getpreStart(H,W)
sx,sy,max_dist=bfs(sx,sy)
visited = [[0 for i in range(W)] for j in range(H)]
sx,sy,max_dist=bfs(sx,sy)
visited = [[0 for i in range(W)] for j in range(H)]
sx,sy,max_dist=bfs(sx,sy)
print(max_dist)

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
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    memo = [[False]*(W+2) for _ in range(H+2)]
    for ey in range(H+1, sy, -1):
      for ex in range(sx+1 if ey == sy else 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:
def warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

h, w = map(int, input().split())
square = []

for i in range(h):
  _s = input()
  for j in range(w):
    if _s[j] == ".":
      square.append(i * w + j)

squares = len(square)
d = [[float("inf") for i in range(squares)] for j in range(squares)]

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

for i in range(squares - 1):
  for j in range(i + 1, squares):
    if (abs(square[i] - square[j]) == 1 and square[i] // w == square[j] // w)or abs(square[i] - square[j]) == w:
      d[i][j] = d[j][i] = 1

d = warshall_floyd(d, squares)
print(max(max(d)))

Submission status: Wrong Answer

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

def check():
  for y in range(H):
    for x in range(W):
      m = M[y][x]
      if m == ".":
        return x,y

st_x,st_y = check()

went = {(st_x,st_y):0}
q = [(st_x,st_y)]
idx = 0
while idx<len(q):
  x,y = q[idx]
  for dx,dy in [(0,-1),(0,1),(-1,0),(1,0)]:
    if (x+dx, y+dy) not in went.keys()  and 0<=x+dx<W and 0<= y+dy<H and M[y+dy][x+dx] == ".":
      q.append((x+dx,y+dy))
      went[(x+dx,y+dy)]=went[(x,y)]+1
  idx+=1

went = {(x,y):0}
q = [(x,y)]
idx = 0
while idx<len(q):
  x,y = q[idx]
  for dx,dy in [(0,-1),(0,1),(-1,0),(1,0)]:
    if (x+dx, y+dy) not in went.keys() and 0<=x+dx<W and 0<= y+dy<H and M[y+dy][x+dx] == ".":
      q.append((x+dx,y+dy))
      went[(x+dx,y+dy)]=went[(x,y)]+1
  idx+=1
  
went = {(x,y):0}
q = [(x,y)]
idx = 0
while idx<len(q):
  x,y = q[idx]
  for dx,dy in [(0,-1),(0,1),(-1,0),(1,0)]:
    if (x+dx, y+dy) not in went.keys() and 0<=x+dx<W and 0<= y+dy<H and M[y+dy][x+dx] == ".":
      q.append((x+dx,y+dy))
      went[(x+dx,y+dy)]=went[(x,y)]+1
  idx+=1
print(max(went.values()))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
maze = []
for i in range(N):
    maze.append(list(input()))
INF = -1
cost = [[INF]*M for _ in range(N)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
sx,sy = 0,0
gx,gy = 0,0

# 左上、右下
sf = False
gf = False
for i in range(N):
    if sf:
        break
    for j in range(M):
        if sf:
            break
        if maze[i][j] != "#":
            sx,sy = i,j
            sf = True
for i in range(N-1,-1,-1):
    if gf:
        break
    for j in range(M-1,-1,-1):
        if gf:
            break
        if maze[i][j] != "#":
            gx,gy = i,j
            gf = True
def bfs():
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.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 < N and 0 <= ny < M and maze[nx][ny] != "#" and cost[nx][ny] == INF:
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost[gx][gy]
bfs()
ans = 0
for i in cost:
    if ans < max(i):
        ans = max(i)

# 左下、右上
cost = [[INF]*M for _ in range(N)]
sf = False
gf = False
for i in range(N-1,-1,-1):
    if sf:
        break
    for j in range(M):
        if sf:
            break
        if maze[i][j] != "#":
            sx,sy = i,j
            sf = True
for i in range(N):
    if gf:
        break
    for j in range(M-1,-1,-1):
        if gf:
            break
        if maze[i][j] != "#":
            gx,gy = i,j
            gf = True
bfs()
for i in cost:
    if ans < max(i):
        ans = max(i)

# 左上、左下
cost = [[INF]*M for _ in range(N)]
sf = False
gf = False
for i in range(N):
    if sf:
        break
    for j in range(M):
        if sf:
            break
        if maze[i][j] != "#":
            sx,sy = i,j
            sf = True
for i in range(N-1,-1,-1):
    if gf:
        break
    for j in range(M):
        if gf:
            break
        if maze[i][j] != "#":
            gx,gy = i,j
            gf = True
bfs()
for i in cost:
    if ans < max(i):
        ans = max(i)

# 右上、右下
cost = [[INF]*M for _ in range(N)]
sf = False
gf = False
for i in range(N):
    if sf:
        break
    for j in range(M-1,-1,-1):
        if sf:
            break
        if maze[i][j] != "#":
            sx,sy = i,j
            sf = True
for i in range(N-1,-1,-1):
    if gf:
        break
    for j in range(M-1,-1,-1):
        if gf:
            break
        if maze[i][j] != "#":
            gx,gy = i,j
            gf = True
bfs()
for i in cost:
    if ans < max(i):
        ans = max(i)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
c = ["#"*(W+2)] + ["#" + input() + "#" for _ in range(H)] + ["#"*(W+2)]


def bfs(start):
	queue = deque([start])
	#visited = [[False for _ in range(W+2)] for _ in range(H+2)]
	tekazu = [[0 for _ in range(W+2)] for _ in range(H+2)]
	num = 0
	while queue:

		label = queue.pop()
		
			#print(visited)
		if c[label[0] + 1][label[1]] == "." and tekazu[label[0] + 1][label[1]] == 0:
			queue.appendleft([label[0] + 1, label[1]])
			tekazu[label[0] + 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] + 1][label[1]])

		if c[label[0] - 1][label[1]] == "." and tekazu[label[0] - 1][label[1]] == 0:
			queue.appendleft([label[0] - 1, label[1]])
			tekazu[label[0] - 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] - 1][label[1]])

		if c[label[0]][label[1] + 1] == "." and tekazu[label[0]][label[1] + 1] == 0:
			queue.appendleft([label[0], label[1] + 1])
			tekazu[label[0]][label[1] + 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] + 1])

		if c[label[0]][label[1] - 1] == "." and tekazu[label[0]][label[1] - 1] == 0:
			queue.appendleft([label[0], label[1] - 1])
			tekazu[label[0]][label[1] - 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] - 1])

	return num

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		if c[h][w] == ".":
			ans = max(ans, bfs([h, w]))
print(ans)

Submission status: Wrong Answer

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

start = []
for i in range(h):
    for j in range(w):
        if s[i][j:j+1] == ".":
            start.append([i,j])
#print(start)

def meiro(ss,count):
    if len(ss) == 0 or count >= 100:
  #      for i in range(h):
  #          print(jokyo[i])
  #      print()
        global ans
        ans = max(ans,count-1)
    else:
        kouho = [[0,1],[0,-1],[1,0],[-1,0]]
        next_s = []
        for hw in ss:
            for i in range(4):    
                next_w = hw[1]+kouho[i][1]
                next_h = hw[0]+kouho[i][0]
                if next_w < w and next_w >= 0:
                    if next_h < h and next_h >= 0:
                        if s[next_h][next_w:next_w+1] == "." and jokyo[next_h][next_w] == -1:
                            next_s.append([next_h,next_w])
                            jokyo[next_h][next_w] = count + 1
        meiro(next_s,count+1)

ans = 0
for i in range(len(start)):
    jokyo = [[-1 for i in range(w)] for j in range(h)]
    jokyo[start[i][0]][start[i][1]] = 0
    meiro([start[i]],0)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools
import copy

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


def tooitenn(maze, s):
    q = deque()
    q.append((s, 0))

    saigonoten = None

    maze[s[0]][s[1]] = "#"

    while len(q) > 0:
        p, depth = q.popleft()
        saigonoten = p

        # ikerutoko
        next_pos = []
        if 0 <= p[0] - 1 < H and maze[p[0] - 1][p[1]] != "#":
            next_pos.append((p[0] - 1, p[1]))
        if 0 <= p[0] + 1 < H and maze[p[0] + 1][p[1]] != "#":
            next_pos.append((p[0] + 1, p[1]))
        if 0 <= p[1] - 1 < W and maze[p[0]][p[1] - 1] != "#":
            next_pos.append((p[0], p[1] - 1))
        if 0 <= p[1] + 1 < W and maze[p[0]][p[1] + 1] != "#":
            next_pos.append((p[0], p[1] + 1))

        for pos in next_pos:
            maze[pos[0]][pos[1]] = "#"
            q.append((pos, depth + 1))

    return saigonoten


def bfs(maze, s):
    q = deque()
    q.append((s, 0))

    depth = 0

    maze[s[0]][s[1]] = "#"

    while len(q) > 0:
        p, depth = q.popleft()

        # ikerutoko
        next_pos = []
        if 0 <= p[0] - 1 < H and maze[p[0] - 1][p[1]] != "#":
            next_pos.append((p[0] - 1, p[1]))
        if 0 <= p[0] + 1 < H and maze[p[0] + 1][p[1]] != "#":
            next_pos.append((p[0] + 1, p[1]))
        if 0 <= p[1] - 1 < W and maze[p[0]][p[1] - 1] != "#":
            next_pos.append((p[0], p[1] - 1))
        if 0 <= p[1] + 1 < W and maze[p[0]][p[1] + 1] != "#":
            next_pos.append((p[0], p[1] + 1))

        for pos in next_pos:
            maze[pos[0]][pos[1]] = "#"
            q.append((pos, depth + 1))

    return depth


for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            p = tooitenn(copy.deepcopy(S), (h, w))
            print(bfs(S, p))
            exit()

Submission status: Wrong Answer

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

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

ans=0
memo=[[-1]*w for _ in range(h)]
for x in range(w):
  for y in range(h):
    if x==h//2+1 and y==w//2+1:
      break
    if memo[y][x]==1: continue
    q=Queue()
    q.put([x,y,0])
    memo=[[-1]*w for _ in range(h)]
    while not q.empty():
      bfs(q)
    ans=max(ans,max(max(memo)))
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())                                   # ノードの訪問済みフラグ
a = [['#']+[i for i in input()]+['#'] for j in range(H)]
a = [['#' for i in range(W+2)]]+a+[['#' for i in range(W+2)]]
b=[x for x in a if "." in x] # "#"が入っている行のみ抽出した2次元配列 右辺の意味合いとしては，「aの各行を代入したxについて，もしx内に#があればリストに加える」
c=zip(*[y for y in zip(*b) if "." in y]) # yは各列を示しており，"#"が入っている列のみを抽出した2次元配列
graph = []
for d in c:
  graph.append(list(d))
H = len(graph)
W = len(graph[0])
for i in range(H):
  graph[i].append('#')
  graph[i].insert(0,'#')
graph = [['#' for i in range(W+2)]] + graph + [['#' for i in range(W+2)]]
import copy
# dfs:ノードvについて、エッジで接続した未訪問のノードを浅いほうから訪問(LILO)
def dfs(r,c,goal):
    visited = [[False for i in range(W+2)] for j in range(H+2)]
    step = 0
    queue = [[r,c]]
    if graph[r][c]=='#':
      return -1
    queue_2 = []
    while len(queue) != 0:
        step += 1
        for now in queue:
          visited[now[0]][now[1]] = True
          for next in [[1,0],[0,1],[-1,0],[0,-1]]:
            if visited[now[0]+next[0]][now[1]+next[1]] == True:continue
            if graph[now[0]+next[0]][now[1]+next[1]] == '#':continue
            if [now[0]+next[0],now[1]+next[1]] == goal:return step
            if [now[0]+next[0],now[1]+next[1]] in queue_2:continue
            queue_2.append([now[0]+next[0],now[1]+next[1]])
        queue.clear()
        queue = copy.deepcopy(queue_2)
        queue_2.clear()
    return -1
  
print(max(dfs(1,1,[H,W]),dfs(H,1,[1,W])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
from collections import deque
def bfs():
    cnt = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while len(Q) > 0:
        q = Q.popleft()
        y,x =  q[0], q[1]
        if cnt >= H*W:
            for i in range(H):
                if len(box[i]) == 0:
                    continue
                else:
                    ans.append(max(box[i]))
            return
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "#" and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = -1
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "." and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = box[y][x] + 1
                Q.append([ny,nx])


H,W = map(int,input().split())
S = [ []for _ in range(H)]
for i in range(H):
    S[i] = list(input())
ans = []
INF = 50**2
Q = deque()
for i in range(H):
    for j in range(W):
        #各マス目に到達するために必要な移動回数
        box = [[0 for _ in range(W)] for __ in range(H)]
        box[i][j] = 0
        Q.append([i,j])
        bfs()
if len(ans)==0:
    print(0)
    exit()
print(max(ans))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())

S = list()
for i in range(H):
  S.append(list(map(lambda x: int(x == '.'), input())))

for i in range(H):
  S[i].append(0)
  S[i].append(0)
S.append([0 for _ in range(W + 2)])


def wfs(loc):
  moved = [
    [
      False for w in range(W + 2)
    ]
    for h in range(H + 2)
  ]
  queue = [(loc, 0)]
  ans = 0
  moved[loc[0]][loc[1]] = True
  while (queue):
    (h, w), move = queue.pop(0)
    for i, j in zip((1, -1, 0, 0), (0, 0, -1, 1)):
      _h, _w = h + i, w + j
      if not moved[_h][_w] and S[_h][_w] == 1:
        moved[_h][_w] = True
        queue.append(((_h, _w), move + 1))
    ans = max(ans, move)
  return ans

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def solve(maze, st_tuple):
    st_row, st_col = st_tuple
    W, H = len(maze[0]), len(maze)
    visited = [[0 for _ in range(W)] for __ in range(H)]
    q = deque()
    q.append((st_row, st_col, 0))
    max_count = 0
    while q:
        cur_row, cur_col, count = q.popleft()
        max_count = max(max_count, count)
        for dr, dc in zip(DR, DC):
            next_row = cur_row + dr
            next_col = cur_col + dc
            if 0 <= next_row < H and 0 <= next_col < W:
                pass
            else:
                continue
            if maze[next_row][next_col] == '#':
                continue
            if visited[next_row][next_col]:
                continue
            q.append((next_row, next_col, count + 1))
            visited[next_row][next_col] = 1
    return max_count

def main():
    H, W = LI()
    maze = []
    for _ in range(H):
        maze.append(S())
    num = 0
    axes = [(s_r, s_c) for s_r in range(H) for s_c in range(W)]
    for st_row, st_col in axes:
        if maze[st_row][st_col] == '#':
            continue
        a = solve(maze, (st_row, st_col))
        num = max(num, a)
    '''
    for st_row in range(H):
        for st_col in range(W):
            for g_row in range(H):
                for g_col in range(W):
    '''


    print(num)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
ans=0
for y in range(h):
    for x in range(w):
        b=[[0]*w for _ in range(h)]
        if a[y][x]=="#":
            break
        now=deque([(y,x)])
        while len(now)!=0:
            Y,X=now.popleft()
            for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
                if 0<=Y+i<=h-1 and 0<=X+j<=w-1:
                    if a[Y+i][X+j]=="." and b[Y+i][X+j]==0 and (x!=X+j and y!=Y+j):
                        b[Y+i][X+j]=b[Y][X]+1
                        now.append((Y+i,X+j))
        c=0                
        for i in b:
            d=max(i)
            c=max(d,c)
        ans=max(ans,c)     
print(ans)

Submission status: Wrong Answer

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

def bfs(sx,sy,t_i,t_j):
    que = deque([(sx,sy)])
    INF= float('inf')
    d = [[INF]*w for i in range(h)]
    d[sx][sy] = 0
    while que:
        x,y =que.popleft()
        for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
            nx,ny = x+dx,y+dy
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == INF and meiro[nx][ny] =='.':
                d[nx][ny] = d[x][y] +1
                que.append((nx,ny))
    return d[t_i][t_j] if d[t_i][t_j] != float('inf') else 0

for s_i in range(h):
    for s_j in range(w):
        for t_i in range(h):
            for t_j in range(w):
                if not (s_i == t_i and s_j == t_j):
                    max_d = max(bfs(s_i,s_j,t_i,t_j), max_d)
print(max_d)

Submission status: Wrong Answer

Solution code:

h, w = map(int,input().split())
grid = []
grid.append('#' * (w+2))
for _ in range(h):
    grid.append('#' + input().rstrip() + '#')
grid.append('#' * (w+2))
            
from collections import deque
import sys
sys.setrecursionlimit(1000000)


def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

maxstep = 0

step = [[-1] * (w+2) for _ in range(h+2)]
def bfs():
    global maxstep

    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    
    que = deque([])
    que.append((s_y, s_x))
    step[s_y][s_x] = 0
    
    while que:
        y, x = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if step[ny][nx] == -1 and grid[ny][nx] != "#":
                que.append((ny, nx))
                step[ny][nx] = step[y][x] + 1

    maxstep = max(max(flatten_2dim(step)), maxstep)
    
for i in range(h+2):
    for j in range(w+2):
        if grid[i][j] == ".":
            s_y, s_x = i, j
            bfs()

print(maxstep)

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

def bfs():
    dist = [[float('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] == float('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
                can.append((sx, sy, gx, gy))
                ans.append(bfs())

ans = [i for i in ans if i != float('inf')]
print(max(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

H, W = map(int, input().split())
S = []
for i in range(H):
    l = str(input())
    S.append(list(l))
# print(H, W)
# print(S)

# 迷路 S における (x1, y1) から (x2, y2) へ移動するのに要する最小 step 数
def min_steps(S, x1, y1, x2, y2):
    if x1 == x2 and y1 == y2:
        steps = 0
    else:
        steps = abs(x1 - x2) + abs(y1 - y2)
    return steps

max_steps = 0
for x1 in range(H):
    for y1 in range(W):
        if (S[x1][y1] != '#'):
            for x2 in range(H):
                for y2 in range(W):
                    if (S[x2][y2] != '#'):
                        steps = min_steps(S, x1, y1, x2, y2)
                        # print(steps)
                        if (steps > max_steps):
                            max_steps = min_steps(S, x1, y1, x2, y2)

print(max_steps)

Submission status: Wrong Answer

Solution code:
def main():

    from collections import deque
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    cost = [[600] * w for _ in range(h)]
    nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    ans = 0

    def bfs(sx, sy, gx, gy):
        q = deque([(sx, sy)])
        cost[sy][sx] = 0

        while q != deque([]):
            x, y = q.popleft()
            for dx, dy in nb:
                nx = x + dx
                ny = y + dy
                if 0 <= nx and nx < w and 0 <= ny and ny < h and s[ny][nx] == "." and cost[ny][nx] == 600:
                    q.append((nx, ny))
                    cost[ny][nx] = cost[y][x] + 1
                    if nx == gx and ny == gy:
                        return cost[gy][gx]

    ans = 0
    for i in range(h):
        for j in range(w):
            for k in range(h):
                for l in range(w):
                    cost = [[600] * w for _ in range(h)]
                    tmp = bfs(j, i, l, k)
                    if tmp != None:
                        ans = max(tmp, ans)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

for i in range(w*h):
    if s[i//w][i%w] == '#':
        mat[i][i] = 10**18
        
    mat[i][i] = 0

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] == '#':
            mat[i][next_idx] = 10**18
        else:
            mat[i][next_idx] = 1

for i in range(w*h):
    #print(i,i,i,i,i,i,i,i,i)
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 10**18
tmp = []

for i in range(w*h):
    for j in range(w*h):
        if ans > mat[i][j]:
            tmp.append(mat[i][j])
            
print(max(tmp))

Submission status: Wrong Answer

Solution code:
H,W=map(int, input().split())
S = [input() for i in range(H)]
m=H*W
l=[[None]*m for i in range(m)]
L=[0]*m
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            L[i*W+j]=1
for i in range(m):
    for j in range(m):
        if L[i] and L[j]:
            if i==j:
                l[i][j]=0
            elif abs(i-j)==W:
                l[i][j]=1
            elif abs(i-j)==1 and (i+j)%W!=W-1:
                l[i][j]=1
            else:
                l[i][j]=400
for i in range(m):
    if L[i]:
        for j in range(m):
            if L[j]:
                for k in range(m):
                    if L[k]:
                        if l[i][j]+l[i][k]<l[j][k]:
                            l[j][k]=l[i][j]+l[i][k]
M=0
for i in l:
    for j in i:
        if j:
            if M<j:
                M=j
print(M)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall


def main():
    H, W = map(int, input().split())
    S = []

    def get_index(h, w):
        return h * W + w

    for _ in range(H):
        S.append(input())

    l = [[0 for _ in range(H * W)] for _ in range(H * W)]
    for h in range(H):
        for w in range(W):
            if 0 <= h - 1 and S[h - 1][w] == ".":
                l[get_index(h, w)][get_index(h - 1, w)] = 1
            if h + 1 < H and S[h + 1][w] == ".":
                l[get_index(h, w)][get_index(h + 1, w)] = 1
            if 0 <= w - 1 and S[h][w - 1] == ".":
                l[get_index(h, w)][get_index(h, w - 1)] = 1
            if w + 1 < W and S[h][w + 1] == ".":
                l[get_index(h, w)][get_index(h, w + 1)] = 1

    fw = floyd_warshall(l)
    #print(fw[0][2])
    ans = 0
    for i in range(H * W):
        for j in range(H * W):
            ans = max(ans, fw[i][j] if not fw[i][j] == float("inf") else 0)

    print(int(ans))


main()

Submission status: Wrong Answer

Solution code:
import queue

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

s = []
for i in range(h):
	tmp = input()
	s.append(tmp)

max = 0

def next(x, y, num):
	relist = []
	if x > 0 and s[x-1][y] == '.' and map[x-1][y] == '.':
		relist.append((x-1,y,num+1))
	if y > 0 and s[x][y-1] == '.' and map[x][y-1] == '.':
		relist.append((x,y-1,num+1))
	if x < h-1 and s[x+1][y] == '.' and map[x+1][y] == '.':
		relist.append((x+1,y,num+1))
	if y < w-1 and s[x][y+1] == '.' and map[x][y+1] == '.':
		relist.append((x,y+1,num+1))
	return relist

for i in range(h):
	for j in range(w):
		map = s.copy()
		q = queue.Queue()
		q.put((i, j, 0))
		map[i] = map[i][:j] + '#' + map[i][j+1:]
		while q.empty() == False:
			x, y, num = q.get()
			if num > max:
				max = num
				xy = (i, j)
			list = next(x, y, num)
			for nx, ny, nnum in list:
				q.put((nx,ny,nnum))
				map[nx] = map[nx][:ny] + '#' + map[nx][ny+1:]

print(max)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def bfs(h,w,n):
    yoyaku=[]
    if h>0:
        if lis[h-1][w]>n+1 and mp[h-1][w]!="#":
            yoyaku.append([h-1,w,n+1])
    if w>0:
        if lis[h][w-1]>n+1 and mp[h][w-1]!="#":
            yoyaku.append([h,w-1,n+1])
    if h<H-1:
        if lis[h+1][w]>n+1 and mp[h+1][w]!="#":
            yoyaku.append([h+1,w,n+1])
    if w<W-1:
        if lis[h][w+1]>n+1 and mp[h][w+1]!="#":
            yoyaku.append([h,w+1,n+1])
    
    lis[h][w]=min(n,lis[h][w])
    return yoyaku

    

mp=[]
for _ in range(H):
    mp.append(list(input()))

ans=[]

for h in range(H):
    for w in range(W):
        lis=[[1000]*W for i in range(H)]
        que=[[[h,w,0]]] if mp[h][w]!="#" else []
        pre=0
        while True:
            if len(que)==0:
                break
            else:
                temp=que.pop(-1)
                #print(temp)
                for tem in temp:
                    pre=max(pre,tem[2])
                    que.append(bfs(tem[0],tem[1],tem[2]))
                    
        ans.append(pre)

    
print(max(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
ans=0
for y in range(h):
    for x in range(w):
        b=[[0]*w for _ in range(h)]
        if a[y][x]=="#":
            break
        now=deque([(y,x)])
        while len(now)!=0:
            Y,X=now.popleft()
            for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
                if 0<=Y+i<=h-1 and 0<=X+j<=w-1:
                    if a[Y+i][X+j]=="." and b[Y+i][X+j]==0 and (x!=x and y!=Y):
                        b[Y+i][X+j]=b[Y][X]+1
                        now.append((Y+i,X+j))
        c=0                
        for i in b:
            d=max(i)
            c=max(d,c)
        ans=max(ans,c)     
print(ans)