Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Wrong Answer

Solution code:
from collections import deque
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)

# 左上、右上
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):
    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-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-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:
input = raw_input

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

meiro = []
coords = []
for i in range(h):
    line = list(input())
    cur_coords = [(j, i) for j in range(w) if line[j] == "."]
    coords += cur_coords
    meiro.append(line)

graphs = []
graph = {}
for cur_coord in coords:
    x, y = cur_coord
    tugi_kouhos = [(x+dx, y) for dx in [-1, 1] if 0 <= x+dx < w]
    tugi_kouhos += [(x, y+dy) for dy in [-1, 1] if 0 <= y+dy < h]
    childs = []
    for tugi_kouho in tugi_kouhos:
        if tugi_kouho in coords:
            childs.append(tugi_kouho)
    graph[cur_coord] = childs


depth_dict_org = {}
for coord in coords:
    depth_dict_org[coord] = None

def calc_depth(coord1, coord2):
    depth_dict = depth_dict_org.copy()

    cur_coord = coord1
    end_coord = coord2
    cur_depth = 0
    used_coords = [coord1]

    childs = graph[coord1]
    while len(childs) != 0:
        cur_depth += 1
        next_childs = []
        used_coords += childs
        for child in childs:
            res = get_childs(child, coord2, used_coords)
            #print("child", child, res)
            #print(used_coords)
            if res == "found":
                return cur_depth + 1
            next_childs += res

        childs = list(set(next_childs))
        #print(childs)

    return 0

def get_childs(jibun, target, used_coords):
    
    childs = []
    for child in graph[jibun]:
        if child == target:
            return "found"
        if child not in used_coords:
            childs.append(child)
    return childs
       

n_coords = len(coords)
max_depth = 0
for i in range(n_coords):
    coord1 = coords[i]
    for j in range(i+1, n_coords):
        coord2 = coords[j]
        cur_depth = calc_depth(coord1, coord2)
        #print(coord1, coord2, cur_depth)
        max_depth = max(max_depth, cur_depth)

print(max_depth)

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 (Y+i!=y or X+j!=x):
                        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(b)
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

q = queue.Queue()

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

def bfs(sx,sy,gx,gy):
    #最短距離を格納する配列
    d = [[0 for i in range(W)] for j in range(H)]
    q.put([sx,sy])
    while not q.empty():
        current_xy = q.get()
        if current_xy == [gx,gy]:
            break
        #4方向のループ
        for i in range(4):
            nx = current_xy[0] + vec_x[i]
            ny = current_xy[1] + vec_y[i]

            #移動が可能か
            if( (nx >= 0 and nx < W ) and (ny >= 0 and ny < H ) ):
                if S[ny][nx] != "#":
                    #すでにおとずれていないか
                    if d[ny][nx] == 0:
                        q.put([nx,ny])
                        d[ny][nx] = d[current_xy[1]][current_xy[0]] + 1
    return d[gy][gx]

for sx in range(W):
    for sy in range(H):
        for gx in range(W):
            for gy in range(H):
                if S[sy][sx] == "#" or S[gy][gx] == "#":
                    continue
                if sx == gx and sy == gy:
                    continue
                if ans <= bfs(sx,sy,gx,gy):
                    ans = bfs(sx,sy,gx,gy)



print(ans)

Submission status: Wrong Answer

Solution code:
# D
from collections import deque
INF = float('inf')
h, w = map(int, input().split())
maps = []

for _ in range(h):
    lst = list(input())
    maps.append(lst)

def bfs(start,goal, maps, distance, height, width):
    d = deque()
    d.append(start)
    sx, sy = start
    distance[sx][sy] = 0
    
    while d:
        now = d.pop()
        nowx, nowy = now
        
        if nowx==goal[0] and nowy==goal[1]:
            break
        
        for i in range(0, 4):
            nx, ny = nowx + [1, 0, -1, 0][i], nowy + [0, 1, 0, -1][i]
            if (0<=nx<height)and(0<=ny<width):
                if (maps[nx][ny] == '.') and (distance[nx][ny] == -1):
                    d.append((nx, ny))
                    distance[nx][ny] = distance[nowx][nowy] + 1
    return distance[goal[0]][goal[1]]

cand = []
for sx in range(h):
    for sy in range(w):
        for gx in range(h):
            for gy in range(w):
                if maps[sx][sy] == '#':
                    continue
                distance = [[-1 for _ in range(w)] for _ in range(h)]
                cand.append(bfs((sx, sy),(gx, gy), maps, distance, h, w))
print(max(cand))

Submission status: Wrong Answer

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

from collections import deque

def dfs(maze, sh, sw):
    visited = [[0]*W for _ in range(H)]
    queue = deque([[sh, sw, 0]])
    visited[sh][sw] = 1
    maxlen = 0
    while queue:
        h, w , tmplen = queue.pop()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                 visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                tmplen += 1
                maxlen = max(maxlen, tmplen)
                queue.appendleft([new_h, new_w, tmplen])
    
    return maxlen

res = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            continue
        res = max(res, dfs(s, i, j))

print(res)

Submission status: Wrong Answer

Solution code:
from queue import Queue
H, W = map(int, input().split())
S = [input() for _ in range(H)]
f = [0, 0]
seen = [[False]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            f[0] = i
            f[1] = j
            break
    else:
        continue
    break
q = Queue()
q.put((f[0], f[1], 0))
D = [[0]*(W) for _ in range(H)]
seen[f[0]][f[1]] = True
while not q.empty():
    h, w, d = q.get()
    for vh, vw in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
        if vh < 0 or vw < 0:
            continue
        try:
            if not seen[vh][vw] and S[vh][vw] == '.':
                q.put((vh, vw, d+1))
                seen[vh][vw] = True
                D[vh][vw] = d+1
        except IndexError:
            pass
m = max([max(d) for d in D])
for h in range(H):
    for w in range(W):
        if D[h][w] == m:
            f[0] = h
            f[1] = w
            break
    else:
        continue
    break
q = Queue()
q.put((f[0], f[1], 0))
D = [[0]*(W) for _ in range(H)]
seen = [[False]*W for _ in range(H)]
seen[f[0]][f[1]] = True
while not q.empty():
    h, w, d = q.get()
    for vh, vw in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
        if vh < 0 or vw < 0:
            continue
        try:
            if not seen[vh][vw] and S[vh][vw] == '.':
                q.put((vh, vw, d+1))
                seen[vh][vw] = True
                D[vh][vw] = d+1
        except IndexError:
            pass
print(max([max(d) for d in D]))

Submission status: Wrong Answer

Solution code:
import queue


def up(y, x, d):
    return y-1, x, d


def down(y, x, d):
    return y+1, x, d


def left(y, x, d):
    return y, x-1, d


def right(y, x, d):
    return y, x+1, d


def put_all(q, y, x, d):
    q.put((up(y, x, d)))
    q.put((down(y, x, d)))
    q.put((left(y, x, d)))
    q.put((right(y, x, d)))
    return


def solve(maze, init_y, init_x, distances, H, W):
    if maze[init_y][init_x] == "#":
        return 0

    distances[init_y][init_x] = 0

    q = queue.Queue()
    put_all(q, init_y, init_x, 1)

    farthest = 0
    while not q.empty():
        y, x, d = q.get()
        # print(x, y)
        if x < 0 or x >= W or y < 0 or y >= H:
            # print("continue")
            continue
        if maze[y][x] == "#":
            continue
        distance = distances[y][x]
        if distance == -1:
            distances[y][x] = d
            put_all(q, y, x, d+1)
            farthest = max(farthest, d)

    return farthest


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

    max_distance = 0
    for i in range(H):
        for j in range(W):
            initial_map = [[-1 for _ in range(W)] for _ in range(H)]
            distance = solve(maze, i, j, initial_map, H, W)
            max_distance = max(distance, max_distance)
            print(i, j, distance)
    print(max_distance)


if __name__ == '__main__':
    main()

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(200)), 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:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
 
H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
 
D=[(1,0),(-1,0),(0,1),(0,-1)]
 
def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=0
    L=defaultdict(lambda: float("-inf")) 
    L[start]=0
 
    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=max(L[(to_x,to_y)],L[(fro_x,fro_y)]+1)
                    q.append((to_x,to_y))
    return max(L.values())
 
ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,bfs((h,w)))
 
print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
import numpy as np
def solve():
    H, W = map(int, input().split())
    M = np.zeros((H,W), dtype=int)
    for h in range(H):
        M[h] = np.array(list(int(x=='.') for x in input()))

    Dist = float('inf')*np.ones((H*W, H*W))
    
    u = M&np.roll(M, 1, axis=0)&np.concatenate((np.zeros((1,W), dtype=int),np.ones((H-1,W), dtype=int)), axis=0)
    d = M&np.roll(M, -1, axis=0)&np.concatenate((np.ones((H-1,W), dtype=int),np.zeros((1,W), dtype=int)), axis=0)
    l = M&np.roll(M, 1, axis=1)&np.concatenate((np.zeros((H,1), dtype=int),np.ones((H,W-1), dtype=int)), axis=1)
    r = M&np.roll(M, -1, axis=1)&np.concatenate((np.ones((H,W-1), dtype=int),np.zeros((H,1), dtype=int)), axis=1)

    hu, wu = np.where(u)
    Dist[hu*W+wu, (hu-1)*W+wu] = 1
    hd, wd = np.where(d)
    Dist[hd*W+wd, (hd+1)*W+wd] = 1
    hl, wl = np.where(l)
    Dist[hl*W+wl, hl*W+wl-1] = 1
    hr, wr = np.where(r)
    Dist[hr*W+wr, hr*W+wr+1] = 1

    for v3 in range(H*W):
        Dist = np.minimum(Dist, Dist[:,v3:v3+1] + Dist[v3:v3+1,:])

    Dist[Dist==float('inf')] = -1

    return str(int(Dist.max()))

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7

    H,W = LMIIS()
    S = [input() for _ in range(H)]
    # print(S)

    def tansaku(S,V,y,x,length):
        
        if  x >= 1 and S[y][x-1] == '.' and V[y][x-1] > length+1:
            V[y][x-1] = length+1
            tansaku(S,V,y,x-1,length+1)


        if x < W-1 and S[y][x+1] == '.' and V[y][x+1] > length+1:
            V[y][x+1] = length+1
            tansaku(S,V,y,x+1,length+1)


        if y >= 1 and S[y-1][x] == '.' and V[y-1][x] > length+1:
            V[y-1][x] = length+1
            tansaku(S,V,y-1,x,length+1)


        if y < H-1 and S[y+1][x] == '.' and V[y+1][x]> length+1:
            V[y+1][x] = length+1
            tansaku(S,V,y+1,x,length+1)

        return
    
    def getmax():
        max_length = 0
        for h in range(H):
            for w in range(W):
                V = [[MOD] * W for _ in range(H)]
                if S[h][w] == '.':
                    tansaku(S,V,h,w,0) 
                for v in V:
                    v = list(map(lambda x:x%MOD,v))
                    max_length = max(v+[max_length])
                    # print(V)
        return max_length
    
    print(getmax())
    






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
infinity = 10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1

N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i+1][j] == 1:
            G[W*(i+1)+j].append(W*i+j)
            #G[W*i+j].append(W*(i+1)+j)

        if i>=1:
            if A[i-1][j] == 1:
                G[W*(i-1)+j].append(W*i+j)
                #G[W*i+j].append(W*(i-1)+j)            
            
        
        if A[i][j+1] == 1:
            G[W*i+(j+1)].append(W*i+j)
            #G[W*i+j].append(W*i+(j+1))
        
        if j>=1:
            if A[i][j-1] == 1:
                G[W*i+(j-1)].append(W*i+j)
                #G[W*i+j].append(W*i+(j-1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0
#print(G)
for i in range(N):
    #print(i)
   
    I = i//W
    J = i%W
    #print(I,J)
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))

print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s= [list(input()) for _ in range(h)]
 
visited = [[-1 for _ in range(w)] for _ in range(h)]

queue = []
mx = 0
for sy in range(h):
    for sx  in range(w):
        st=s[sy][sx]
        if st =="#":
            continue
        for gy  in range(h):
            for gx in range(w):
                gl = s[gy][gx]
                if gl =="#":
                    continue
                else:            
                    visited[sy][sx] = 0
                    queue.append((sy, sx))
                    while queue:
                          y, x = queue.pop(0)
                          for y_, x_ in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)]:
                                if y_<0 or y_>=h or x_<0 or x_>= w:
                                    continue
                                else:
                                    if s[y_][x_] == '.':
                                      if visited[y_][x_] == -1:
                                        visited[y_][x_] = visited[y][x] + 1
                                        queue.append((y_, x_))
                if mx <visited[gy][gx]:
                    mx = visited[gy][gx]
print(mx)

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][3])
    ans = 0
    for i in range(H * W):
        for j in range(H * W):
            ans = max(ans, fw[i][j] if fw[i][j] < float("inf") else 0)

    print(int(ans))


main()

Submission status: Wrong Answer

Solution code:
def clear_maze(sx, sy, gx, gy, maze):

    INF = float("inf")

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

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

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length:
                    try:
                        if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                            queue.insert(0, (nx, ny))
                            distance[nx][ny] = distance[x][y] + 1
                    except Exception as e:
                        print(nx, ny)
                        print(maze)
                        print(maze[nx][ny])
                        print(distance)
                        exit()

        return distance[gx][gy]

    return bfs()


H, W = map(int, input().split())
maze = []
for w in range(H):
    maze.append([x for x in input()])
ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            sx, sy = h, w
            for g in range(H):
                for l in range(w, W):
                    if maze[g][l] == ".":
                        if l+1 < W:
                            if maze[g][l+1] == ".":
                                continue
                        gx, gy = g, l
                        ans = max(clear_maze(sx,sy,gx,gy, maze),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def solve(s):
    offset = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = [[-1] * W for _ in range(H)]
    visited[0][0] = 0
    
    if s[0] <= W - 1 and s[1] <= H - 1 and S[s[1]][s[0]] != "#":
        visited[s[1]][s[0]] = 1

    if s[0] >= W - 1 or s[1] >= H - 1:
        return visited
    
    q = deque()
    q.append(s)

    while q:
        x, y = q.popleft()

        for u, v in offset:
            if not (0 <= x + u < W) or not (0 <= y + v < H):
                continue

            if visited[y + v][x + u] > -1 or S[y + v][x + u] == "#":
                continue

            visited[y + v][x + u] = visited[y][x] + 1
            q.append((x + u, y + v))
            
    return visited

ans_1 = (0, 0, 0)
for y, v in enumerate(solve((0, 1))):
    for x, c in enumerate(v):
        if c >= ans_1[2]:
            ans_1 = (x, y, c)
        
ans_2 = (0, 0, 0)
for y, v in enumerate(solve((1, 0))):
    for x, c in enumerate(v):
        if c >= ans_2[2]:
            ans_2 = (x, y, c)
        
if ans_1[0] == ans_2[0] and ans_1[1] == ans_2[1]:
    print(min(ans_1[2], ans_2[2]))
else:
    print(ans_1[2] + ans_2[2])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
 
H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
 
D=[(1,0),(-1,0),(0,1),(0,-1)]
 
def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=0
    L={}
    L[start]=0
 
    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=L[(fro_x,fro_y)]+1
                    q.append((to_x,to_y))
    return max(L.values())
 
ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,bfs((h,w)))
 
print ans

Submission status: Wrong Answer

Solution code:
import queue

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

s = list()
for l in range(0, h):
    line = input(">")
    s.append(line)

dx = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def search(start_h, start_w):
    if s[start_h][start_w] == "#":
        return -1

    cost = [[10000000 for i in range(0, w)] for j in range(0, h)]

    q = queue.Queue()
    q.put((start_h, start_w, 0))
    cost[start_h][start_w] = 0
    while not q.empty():
        current_h, current_w, current_c = q.get()
        # print("(%d, %d, %d)" % (current_h, current_w, current_c))

        # print("pos_w:%d, pos_h:%d, cost:%d" % (current_w, current_h, current_c))
        for dw, dh in dx:
            next_h = current_h + dh
            next_w = current_w + dw
            next_c = current_c + 1

            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue

            if s[next_h][next_w] == "#" or cost[next_h][next_w] <= next_c:
                continue
            else:
                q.put((next_h, next_w, next_c))
                cost[next_h][next_w] = next_c

    tmp = 0
    for a in range(0, w):
        for b in range(0, h):
            if cost[b][a] > 1000:
                continue
            else:
                tmp = max(tmp, cost[b][a])

    return tmp


ans = 0
for i in range(0, w):
    for j in range(0, h):
        # print("start_h:%d, start_w:%d" % (j, i))
        cost_tmp = search(j, i)
        ans = max(ans, cost_tmp)
        # print("start_h:%d, start_w:%d cost:%d" % (j, i, cost_tmp))


print(ans)

Submission status: Wrong Answer

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

def solve(h, w, a):
    dp = [[-1] * (h * w) for _ in range(h * w)]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    def bfs(x1, y1, x2, y2):
        s = y1 * w + x1
        t = y2 * w + x2
        visited = [[False] * w for _ in range(h)]
        cur = []
        visited[y1][x1] = True
        cur.append((x1, y1))
        cnt = 1
        while True:
            nex = []
            for x, y in cur:
                for i in range(4):
                    tx = x + dx[i]
                    ty = y + dy[i]
                    if 0 <= tx < w and 0 <= ty < h and a[ty][tx] != '#' and not visited[ty][tx]:
                        visited[ty][tx] = True
                        if tx == x2 and ty == y2:
                            return cnt
                        if dp[ty * w + tx][t] >= 0:
                            return cnt + dp[ty * w + tx][t]
                        nex.append((tx, ty))
                        dp[s][ty * w + tx] = cnt
            if len(nex) > 0:
                cur = nex
            else:
                break
            cnt += 1
        return -1

    ret = -1
    for i in range(h):
        for j in range(w):
            for i2 in range(h):
                for j2 in range(w):
                    if (i == i2 and j == j2):
                        dp[w * i + j][w * i2 + j2] = 0
                        dp[w * i2 + j2][w * i + j] = 0
                    elif a[i][j] == '.' and a[i2][j2] == '.' and dp[w * i + j][w * i2 + j2] < 0:
                        tmp = bfs(j, i, j2, i2)
                        ret = max(ret, tmp)
                        #dp[w * i + j][w * i2 + j2] = tmp
                        #dp[w * i2 + j2][w * i + j] = tmp
                        #print(i, j, i2, j2)
                        #print(tmp)
    print(ret)
    return

def main():
    h, w = map(int, input().split())
    a = []
    for i in range(h):
        a.append(input())
    solve(h, w, a)

if __name__ == '__main__':
    main()