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, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
inf = -9999999999
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    h, w = nm()
    s = s = [['#'] * (w+1)]
    for _ in range(h):
        temp = ['#']
        temp.extend(list(ns()))
        temp.extend(['#'])
        s.append(temp)
    s.append(['#'] * (w+1))
        
    def bfs(arr, x, y):
        que = deque([[x, y]])
        cost = 0
        dist = [[0]*(w+2) for _ in range(h+2)]
        for i in range(h+2):
            for j in range(w+2):
                if i == 0 or i == h + 1 or j == 0 or j == w + 1:
                    dist[i][j] = inf
        visited = set((x, y))
        while True:
            #print(x, y, que)
            now = que.popleft()
            if arr[now[0]][now[1]] == '.':
                if (now[0]+1, now[1]) not in visited:
                    que.append([now[0]+1, now[1]])
                    visited.add((now[0]+1, now[1]))
                    dist[now[0]+1][now[1]] = cost
                if (now[0], now[1]+1) not in visited:
                    que.append([now[0], now[1]+1])
                    visited.add((now[0], now[1]+1))
                    dist[now[0]][now[1]+1] = cost
                if (now[0]-1, now[1]) not in visited:
                    que.append([now[0]-1, now[1]])
                    visited.add((now[0]-1, now[1]))
                    dist[now[0]-1][now[1]] = cost
                if (now[0], now[1]-1) not in visited:
                    que.append([now[0], now[1]-1])
                    visited.add((now[0], now[1]-1))
                    dist[now[0]][now[1]-1] = cost
                cost += 1
            elif arr[now[0]][now[1]] == '#':
                dist[now[0]][now[1]] = inf
            if que == deque():
                break 
        mx = []
        for i in range(h+2):
            mx.append(max(dist[i]))       
        return max(mx)

    ans = []
    for i in range(1, h+1):
        for j in range(1, w+1):
            ans.append(bfs(s, i, j))

    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy):
  dmap=[[h*w+1]*w for _ in range(h)]
  dmap[sx][sy]=0
  cand=[]
  visited=set()
  cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.pop()
    visited.add((x,y))
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.':
        dmap[next_x][next_y]=min(dmap[x][y]+1,dmap[next_x][next_y])
        if not (next_x,next_y) in visited:
          cand.append([next_x,next_y])
  return max([dmap[i][j] for i in range(h) for j in range(w) if dmap[i][j]<=h*w])
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      d=maze(l,ix,iy)
      if c<d:
        c=d
print(c)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy):
  dmap=[[h*w+1]*w for _ in range(h)]
  dmap[sx][sy]=0
  cand=[]
  visited=set()
  cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.pop()
    visited.add((x,y))
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.' and not (next_x,next_y) in visited:
        cand.append([next_x,next_y])
        dmap[next_x][next_y]=min(dmap[x][y]+1,dmap[next_x][next_y])
  return max([dmap[i][j] for i in range(h) for j in range(w) if dmap[i][j]<=h*w])
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      d=maze(l,ix,iy)
      if c<d:
        c=d
print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = []
for i in range(H):
    G.append(list(input()))


move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
saidai = 0
for sy in range(H):
    for sx in range(W):
        if G[sy][sx] == ".":
            queue = deque([[sy, sx]])
            visited = [[0]*W for i in range(H)]
            while queue:
                y, x = queue.popleft()
                for i in move:
                    iy, ix = i[0], i[1]
                    if 0<=iy+y<H and 0<=ix+x<W and G[iy+y][ix+x] =="." and visited[iy+y][ix+x] == 0:
                        visited[iy+y][ix+x] = visited[y][x] + 1
                        queue.append([iy+y, ix+x])
        
            for i in range(H):
                for j in range(W):
                        saidai = max(saidai, visited[i][j])
            queue = []
            visited = [[0]*W for i in range(H)]
print(saidai)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = []
for i in range(H):
    G.append(list(input()))


move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
saidai = 0
for sy in range(H):
    for sx in range(W):
        if G[sy][sx] == ".":
            queue = deque([[sy, sx]])
            visited = [[0]*W for i in range(H)]
            while queue:
                y, x = queue.popleft()
                for i in move:
                    iy, ix = i[0], i[1]
                    if 0<=iy+y<H and 0<=ix+x<W and G[iy+y][ix+x] =="." and visited[iy+y][ix+x] == 0:
                        visited[iy+y][ix+x] = visited[y][x] + 1
                        queue.append([iy+y, ix+x])
        
            for i in range(H):
                for j in range(W):
                        saidai = max(saidai, visited[i][j])

print(saidai)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = []
for i in range(H):
    G.append(list(input()))


move = [[0, 1], [0, -1], [0, 1], [1, 0]]
saidai = 0
for sy in range(H):
    for sx in range(W):
        if G[sy][sx] == ".":
            continue
        queue = deque([[sy, sx]])
        visited = [[0]*W for i in range(H)]
        while queue:
            y, x = queue.popleft()
            for i in move:
                iy, ix = i[0], i[1]
                if 0<=iy+y<H and 0<=ix+x<W and G[iy+y][ix+x] =="." and visited[iy+y][ix+x] == 0:
                    visited[iy+y][ix+x] = visited[y][x] + 1
                    queue.append([iy+y, ix+x])
 
        for i in range(H):
            for j in range(W):
                    saidai = max(saidai, visited[i][j])

print(saidai)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

G = []
for i in range(H):
    G.append(list(input()))


move = [[0, 1], [0, -1], [0, 1], [1, 0]]
saidai = 0
for sy in range(H):
    for sx in range(W):
        if G[sy][sx] == "#":
            break
        queue = deque([[sy, sx]])
        visited = [[0]*W for i in range(H)]
        while queue:
            y, x = queue.popleft()
            for i in move:
                iy, ix = i[0], i[1]
                if 0<=iy+y<H and 0<=ix+x<W and G[iy+y][ix+x] =="." and visited[iy+y][ix+x] == 0:
                    visited[iy+y][ix+x] = visited[y][x] + 1
                    queue.append([iy+y, ix+x])
 
        for i in range(H):
            for j in range(W):
                    saidai = max(saidai, visited[i][j])

print(saidai)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

H, W = rl()
M = []
for i in range(H):
    row = rs()
    M.append(row)

import collections
def get_dist(i, j):
    visited = {}
    queue = collections.deque()
    queue.append((i,j,0)) 
    max_l = 0
    while queue:
        i, j, l = queue.popleft()
        if (i,j) in visited: continue
        max_l = max(max_l, l)
        visited[(i,j)] = 1
        for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
            ni, nj = i+di, j+dj
            if 0 <= ni < H and 0<= nj < W and M[ni][nj] != '#':
                queue.append((ni,nj,l+1))
    return max_l

max_move = 0
for i in range(H):
    for j in range(W):
        d = get_dist(i, j)
        max_move = max(max_move, d)
print(max_move)

Submission status: Wrong Answer

Solution code:
#頂点の数をN、変の数をMとするとO(N+M)
#queueは遅いからdequeを使う
from collections import deque
from copy import deepcopy

q = deque()
h,w = map(int,input().split())
c = [['#' for _ in range(w+2)]]
for _ in range(h):
	c.append(list('#'+input()+'#'))
c.append(['#' for _ in range(w+2)])

ans = [[0 for _ in range(w+2)]for _ in range(h+2)]
c_copy = deepcopy(c)
ans_copy = deepcopy(ans)
def bfs(x,y):
	global q
	global c
	q.append([x,y])
	num = 0

	while q:
		x,y = q.popleft()
		if c[y][x-1] == '.':
			q.append([x-1,y])
			ans[y][x-1] = ans[y][x] + 1
			num = ans[y][x-1]
			c[y][x-1] = '#'
		if c[y][x+1] == '.':
			q.append([x+1,y])
			ans[y][x+1] = ans[y][x] + 1
			num = ans[y][x+1]
			c[y][x+1] = '#'
		if c[y-1][x] == '.':
			q.append([x,y-1])
			ans[y-1][x] = ans[y][x] + 1
			num = ans[y-1][x]
			c[y-1][x] = '#'
		if c[y+1][x] == '.':
			q.append([x,y+1])
			ans[y+1][x] = ans[y][x] + 1
			num = ans[y+1][x]
			c[y+1][x] = '#'
	return num

tmp = 0
for i in range(1,h+1):
	for j in range(1,w+1):
		c = deepcopy(c_copy)
		ans = deepcopy(ans_copy)
		if c[i][j] == '.':
			tmp = max(tmp,bfs(j,i))
print(tmp)

Submission status: Wrong Answer

Solution code:
#頂点の数をN、変の数をMとするとO(N+M)
#queueは遅いからdequeを使う
from collections import deque
from copy import deepcopy

q = deque()
h,w = map(int,input().split())
c = [['#' for _ in range(w+2)]]
for _ in range(h):
	c.append(list('#'+input()+'#'))
c.append(['#' for _ in range(w+2)])

ans = [[0 for _ in range(w+2)]for _ in range(h+2)]
c_copy = deepcopy(c)
ans_copy = deepcopy(ans)
def bfs(x,y):
	global q
	global c
	q.append([x,y])
	num = 0

	while q:
		x,y = q.popleft()
		if c[y][x-1] == '.':
			q.append([x-1,y])
			ans[y][x-1] = ans[y][x] + 1
			num = ans[y][x-1]
			c[y][x-1] = '#'
		if c[y][x+1] == '.':
			q.append([x+1,y])
			ans[y][x+1] = ans[y][x] + 1
			num = ans[y][x+1]
			c[y][x+1] = '#'
		if c[y-1][x] == '.':
			q.append([x,y-1])
			ans[y-1][x] = ans[y][x] + 1
			num = ans[y-1][x]
			c[y-1][x] = '#'
		if c[y+1][x] == '.':
			q.append([x,y+1])
			ans[y+1][x] = ans[y][x] + 1
			num = ans[y+1][x]
			c[y+1][x] = '#'
	return num

tmp = 0
for i in range(1,h+1):
	for j in range(1,w+1):
		c = deepcopy(c_copy)
		ans = deepcopy(ans_copy)
		tmp = max(tmp,bfs(j,i))
print(tmp)

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw))
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[sh][sw] = 0

    while len(que) > 0:
        h, w = que.popleft()
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#' or dist[h + dh][w + dw] != -1:
                continue
            dist[h + dh][w + dw] = dist[h][w] + 1
            que.append((h + dh, w + dw))
    return dist


ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            dist = bfs(h, w, mp)
            ans = max(ans, max(max(dist)))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = []
    heapq.heappush(que, (0, sh, sw))
    dist = [[-1 for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        d, h, w = heapq.heappop(que)
        if dist[h][w] != -1:
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#' or dist[h + dh][w + dw] != -1:
                continue
            heapq.heappush(que, (d + 1, h + dh, w + dw))
    return dist


ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            dist = bfs(h, w, mp)
            ans = max(ans, max(max(dist)))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = []
    heapq.heappush(que, (0, sh, sw))
    dist = [[-1 for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        d, h, w = heapq.heappop(que)
        if dist[h][w] != -1:
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#':
                continue
            heapq.heappush(que, (d + 1, h + dh, w + dw))
    return dist

ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            ans = max(ans, max(max(tmp_dist)))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = []
    heapq.heappush(que, (0, sh, sw))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        d, h, w = heapq.heappop(que)
        if dist[h][w] < d:
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#':
                continue
            heapq.heappush(que, (d + 1, h + dh, w + dw))
    return dist


flag = False
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            sh = h; sw = w;
            flag = True
            break
    if flag:
        break

for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h
            sw = w

dist = bfs(sh, sw, mp)
ans = 1
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        if dist[h][w] != float('inf'):
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#':
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


flag = False
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            sh = h; sw = w;
            flag = True
            break
    if flag:
        break

for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h
            sw = w

dist = bfs(sh, sw, mp)
ans = 1
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        if dist[h][w] != float('inf'):
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#' or dist[h + dh][w + dw] != float('inf'):
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


flag = False
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            sh = h; sw = w;
            flag = True
            break
    if flag:
        break

for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h
            sw = w

dist = bfs(sh, sw, mp)
ans = 1
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#' or dist[h + dh][w + dw] != float('inf'):
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


flag = False
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            sh = h; sw = w;
            flag = True
            break
    if flag:
        break

for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h
            sw = w

dist = bfs(sh, sw, mp)
ans = 1
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        if dist[h][w] != float('inf'):
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#':
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


flag = False
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            sh = h
            sw = w
            flag = True
            break
    if flag:
        break

for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h; sw = w

dist = bfs(sh, sw, mp)
ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#' or dist[h + dh][w + dw] != float('inf'):
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            break

sh, sw = (h, w)
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h; sw = w

dist = bfs(sh, sw, mp)
ans = 1
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        if dist[h][w] != float('inf'):
            continue
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#':
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            break

sh, sw = (h, w)
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h; sw = w

dist = bfs(sh, sw, mp)
ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import*
from itertools import*
from copy import*
n,m=map(int,input().split())

grid=[list("#"*(m+2))]+[list("#"+input()+"#")for i in range(n)]+[list("#"*(m+2))]

#print(grid)

start=[]
for i in range(1,n+1):
    for j in range(1,m+1):
        start.append((i,j))

ans=0
for s,g in combinations(start,2):
    G=deepcopy(grid)
    G[s[0]][s[1]]=0
    Q=deque([s])
    while Q:
        y,x=Q.pop()
        for my,mx in (-1,0),(1,0),(0,-1),(0,1):
            if G[y+my][x+mx]==".":
                G[y+my][x+mx]=G[y][x]+1
                Q.appendleft((y+my,x+mx))
    
    if type(G[g[0]][g[1]])!=str:
        if ans<G[g[0]][g[1]]:
            ans=G[g[0]][g[1]]
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
H,W = map(int,input().split())
Maze=[]
for h in range(H):
    Maze.append(input())
max_length = 0
for i in range(H):
    for j in range(W):
        Dist = [[-1 for _ in range(W)] for __ in range(H)]
        if Maze[i][j]=='#':
            continue
        Dist[i][j]=0
        q=queue.Queue()
        q.put([i,j])
        di = [1,0,-1,0]
        dj = [0,1,0,-1]
        while not q.empty():
            pos = q.get()
            for k in range(4):
                ni = di[k] + pos[0]
                nj = dj[k] + pos[1]
                if ni<0 or nj<0 or ni>H-1 or nj>W-1:
                    continue
                if Maze[ni][nj]=='#':
                    continue
                if not Dist[ni][nj]==-1:
                    continue
                Dist[ni][nj] = Dist[pos[0]][pos[1]] + 1
                q.put([ni,nj])
        max_length = max(max_length,max(max(Dist)))

print(max_length)

Submission status: Wrong Answer

Solution code:
import queue
H,W = map(int,input().split())
Maze=[]
for h in range(H):
    Maze.append(input())
max_length = 0
for i in range(H):
    for j in range(W):
        Dist = [[-1 for i in range(W)] for j in range(H)]
        if Maze[i][j]=='#':
            continue
        Dist[i][j]=0
        q=queue.Queue()
        q.put([i,j])
        di = [1,0,-1,0]
        dj = [0,1,0,-1]
        while not q.empty():
            pos = q.get()
            for k in range(4):
                ni = di[k] + pos[0]
                nj = dj[k] + pos[1]
                if ni<0 or nj<0 or ni>H-1 or nj>W-1:
                    continue
                if Maze[ni][nj]=='#':
                    continue
                if not Dist[ni][nj]==-1:
                    continue
                Dist[ni][nj] = Dist[pos[0]][pos[1]] + 1
                q.put([ni,nj])
        max_length = max(max_length,max(max(Dist)))

print(max_length)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
Maze=[]
for h in range(H):
    Maze.append(input())
# startをすべてのマスについてまわして，BFSをすればよい．
# queueを使うと，常に最小の要素が取り出せるので，うまくいく．
import queue
max_length = 0
for i in range(H*W):
    height = int(i/W)
    width = int(i%W)
    if Maze[height][width]=='.':
        Maze_distance = [[-1 for _ in range(W)] for __ in range(H)]
        # lambda update x: lambda４季には名前をつけないほうがいいらしい．多分名前をつけてもいいけどpython的には
        # 無名関数に名前つけるくらいだったらdef使って定義しとけよということらしい
        q = queue.Queue()
        q.put([height,width])
        Maze_distance[height][width] = 0
        while not q.empty():
            pos = q.get()
            if pos[0]+1 <= H-1 and Maze_distance[pos[0]+1][pos[1]]==-1 and Maze[pos[0]+1][pos[1]] == '.':
                Maze_distance[pos[0]+1][pos[1]] = Maze_distance[pos[0]][pos[1]] + 1
                q.put([pos[0]+1, pos[1]])
            if pos[0]-1 >= 0 and Maze_distance[pos[0]-1][pos[1]] == -1 and Maze[pos[0]-1][pos[1]] == '.':
                Maze_distance[pos[0]-1][pos[1]] = Maze_distance[pos[0]][pos[1]] + 1
                q.put([pos[0]-1, pos[1]])
            if pos[1]+1 <= W-1 and Maze_distance[pos[0]][pos[1]+1] == -1 and Maze[pos[0]][pos[1]+1] == '.':
                Maze_distance[pos[0]][pos[1]+1] = Maze_distance[pos[0]][pos[1]] + 1
                q.put([pos[0], pos[1]+1])
            if pos[1]-1 >= 0 and Maze_distance[pos[0]][pos[1]-1] == -1 and Maze[pos[0]][pos[1]-1] == '.':
                Maze_distance[pos[0]][pos[1]-1] = Maze_distance[pos[0]][pos[1]] + 1
                q.put([pos[0], pos[1]-1])
        # 2次元リストの最大をとるにはmaxを２回取らないといけいない．n次元に対してmaxをn回つかう．
        max_length = max(max_length,max(max(Maze_distance)))

print(max_length)

Submission status: Wrong Answer

Solution code:
import math
from queue import Queue

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

q = Queue()
#     [x, y]
q.put([0, h - 1])
li[h - 1][0] = 0

while not q.empty():
    c = q.get()
    # 上(0, -1) 右(1, 0) 下(0, 1) 左(-1, 0)
    for dr in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
        if li[c[1]][c[0]] == "#": break

        nX = c[0] + dr[0]
        nY = c[1] + dr[1]

        if not (0 <= nX <= w - 1): continue
        if not (0 <= nY <= h - 1): continue

        if li[nY][nX] == ".":
            li[nY][nX] = li[c[1]][c[0]] + 1
            q.put([nX, nY])

print(li[0][w - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def bfs(maze, visited, sh, sw, H, W):
    q = deque([(sh, sw)])
    visited[sh][sw] = 0
    M = 0
    while q:
        h, w = q.popleft()
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))
                    if visited[nh][nw] > M:
                        M = visited[nh][nw]

    return M


ans = 0
for h in range(H):
    for w in range(W):
        visited = [[-1] * W for _ in range(H)]
        tmp = bfs(maze, visited, h, w, H, W)
        if tmp > ans:
            ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def bfs(maze, visited, sh, sw, H, W):
    q = deque([(sh, sw)])
    visited[sh][sw] = 0
    M = 0
    while q:
        h, w = q.popleft()
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))
                    if (nh == 0 or nh == H - 1) or (nw == 0 or nw == W - 1):
                        if visited[nh][nw] > M:
                            M = visited[nh][nw]

    return M


ans = 0
for h in range(H):
    for w in range(W):
        visited = [[-1] * W for _ in range(H)]
        tmp = bfs(maze, visited, h, w, H, W)
        if tmp > ans:
            ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def bfs(maze, visited, sh, sw, gh, gw, H, W):
    q = deque([(sh, sw)])
    visited[sh][sw] = 0

    while q:
        h, w = q.popleft()
        if h == gh and w == gw:
            return visited[gh][gw]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))

    return -1


ans = 0
for h in range(H):
    for w in range(W):
        for gh in range(H):
            for gw in range(W):
                if h == gh and w == gw:
                    continue
                visited = [[-1] * W for _ in range(H)]
                tmp = bfs(maze, visited, h, w, gh, gw, H, W)
                if tmp > ans:
                    ans = tmp
print(ans)