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

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

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

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

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

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

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

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

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

                # 移動先ny, nxが迷路の範囲内
                # かつ壁（maze配列が#）でなく、
                # かつ未到達（distance配列がINF）であるときに
                # 現時点の距離+1をdistance配列に格納する
                # 現時点の座標をqueue配列に格納する（再ループの時にその座標から始める）
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1

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

Submission status: Wrong Answer

Solution code:
# import numpy as np
from itertools import combinations
import copy
from collections import deque

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

# S = np.zeros((H,W))
S = [[0]*W for i in range(H)]
# print(S)
for i in range(H):
    scan =  input()
    # print(scan)
    for j,s in enumerate(scan):
        if s == ".":
            S[i][j] = 0
        else:
            S[i][j] = 1
# print(S)
positions = []
for i in range(H):
    for j in range(W):
        positions.append((i,j))
# print(positions)
c = combinations(positions,2)
result = 0
for pat in c:
    start = pat[0]
    stop = pat[1]
    distance = 0
    S1 = copy.deepcopy(S)
    q = deque()
    # d = np.full((H,W),np.inf)
    d = [[float('inf')]*W for i in range(H)]

    q.append(start)
    d[start[0]][start[1]] = 0
    while len(q) > 0:
        p = q.popleft()
        # print(p)
        i,j = p[0],p[1]
        four = [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]
        if p == stop:
            break
        for f in four:
            i1,j1 = f[0],f[1]
            if 0 <= i1 < H and 0<= j1 < W and S1[i1][j1] == 0 and d[i1][j1] == float('inf'):
                q.append((i1,j1))
                d[i1][j1] = d[i][j] +1
    distance = d[stop[0]][stop[1]]
    # print(distance)
    if distance != float('inf') and distance > result:
        result = int(distance)

print(result)

Submission status: Wrong Answer

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

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

mx = 0 

St = []

for i in range(H):
        for j in range(W):
                for k in range(H):
                        for l in range(W):
                                if i != k or j != l:
                                        if S[i][j] == "." and S[k][l] == ".":
                                                St.append([i, j, k, l]) 
print(St)

for i in St: 
        q = queue.Queue()
        checked = [[0 for j in range(W)] for i in range(H)]
        q.put([i[0], i[1]])
        flag = False
        while not q.empty():
                c = 0 
                di = q.get()    
                checked[di[0]][di[1]] = -1
                for k in range(4):
                        nh = di[0] + dy[k]
                        nx = di[1] + dx[k]
                        if 0 <= nx < W and 0 <= nh < H and checked[nh][nx] == 0:
                                if nh == i[2] and nx == i[3]:
                                        c += 1
                                        if mx < c:
                                                mx = c 
                                        flag = True
                                        break
                                elif S[nh][nx] == ".":
                                        c += 1
                                        q.put([nh, nx])
                if flag:
                        break
print(mx)

Submission status: Wrong Answer

Solution code:
H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    s_list = list(str(input()))
    S.append(s_list)

from collections import deque
INF = 1000000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(sx, sy, gx, gy):
    d = []
    for i in range(H):
        d.append([INF] * W)
    
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while len(que):
        p = que.popleft()
        if p == (gx, 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 and S[nx][ny] != '#' and d[nx][ny] == INF:
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

def ContCheck(x, y):
    route = 0
    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] != '#':
            route += 1
    if route == 1:
        return False
    else:
        return True

ans = 0
checked = []
for _ in range(H * W):
    checked.append([0] * (H * W))
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        if ContCheck(i, j):
            continue
        for k in range(H):
            for l in range(W):
                if S[k][l] == '#':
                    continue
                if ContCheck(k, l):
                    continue
                if checked[i * W + j][k * W + l] == 1:
                    continue
                if i == k and j == l:
                    continue
                ans = max(bfs(i, j, k, l), ans)
                checked[i * W + j][k * W + l] = 1
                checked[k * W + l][i * W + j] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
def A():
    c = input()
    print(chr(ord(c)+1))

def B():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    K = temp[1]
    M = temp[2]
    A = [int(k) for k in input().split()]
    ans = M*N - sum(A)
    if ans <= K:
        print(max(0, ans))
    else:
        print(-1)

from collections import defaultdict
def C():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    M = temp[1]
    penal = defaultdict(int)
    P = []
    S = []
    for i in range(M):
        temp = input().split()
        P.append(int(temp[0]))
        S.append(temp[1])
    ac_problems = set()

    for i in range(M-1, -1, -1):
        if P[i] not in ac_problems and S[i] == 'AC':
            ac_problems.add(P[i])
        elif P[i] in ac_problems:
            if S[i] == 'WA':
                penal[P[i]] += 1
            elif S[i] == 'AC':
                penal[P[i]] = 0
    
    print(len(ac_problems), sum(penal.values()))

def D():
    temp = [int(k) for k in input().split()]
    H = temp[0]
    W = temp[1]
    S = []
    for i in range(H):
        S.append(input())
    ans = 0
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    memo = [[0 for i in range(W)] for j in range(H)]
    def bfs(x, y):
        to_visit = [(x, y, 0)]
        visited = set()
        while to_visit:
            x, y, distance = to_visit[0]
            del to_visit[0]
            visited.add((x, y))
            memo[x][y] = max(distance, memo[x][y])
            for d in directions:
                if x+d[0] < H and x+d[0] >= 0:
                    if y+d[1] < W and y+d[1] >= 0:
                        if (x+d[0], y+d[1]) not in visited:
                            if S[x+d[0]][y+d[1]] == '.':
                                if memo[x+d[0]][y+d[1]] > 0:
                                    memo[x+d[0]][y+d[1]] += distance
                                else:
                                    to_visit.append((x+d[0], y+d[1], distance+1))
        #print(memo)

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                bfs(i, j)
                
    #print(memo)
    for i in range(H):
        for j in range(W):
            if memo[i][j] < float('inf'):
                ans = max(ans, memo[i][j])

    print(ans)

D()

Submission status: Wrong Answer

Solution code:
import copy
h,w=map(int,input().split())
maze = [['#']+list(input())+['#'] for i in range(h)]
maze.insert(0,['#']*(w+2))
maze.append(['#']*(w+2))

def get_max_length_from_start(maze,x,y):
    max_length_list=[]
    tmp_maze=copy.deepcopy(maze)
    searching = [[y,x]]
    length=0
    while len(searching)!=0:
        next_searching_list=[]
        for point in searching:
            tmp_maze[point[0]][point[1]]=length
            mawari = [[point[0]+1,point[1]],[point[0]-1,point[1]],[point[0],point[1]+1],[point[0],point[1]-1]]
            next_searching = list(filter(lambda x:tmp_maze[x[0]][x[1]]==".",mawari))
            if len(next_searching)==0:
                max_length_list.append(length)
                continue
            next_searching_list += next_searching
        searching = list(map(list, set(map(tuple, next_searching_list))))
        length+=1
    return sorted(max_length_list)

true_max_length_list=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if maze[y][x]=='#':
            continue
        max_length_list=get_max_length_from_start(maze,x,y)
        if len(max_length_list)>=2:
            max_length=max_length_list[-1]+max_length_list[-2]
        else:
            max_length=max_length_list[0]
        true_max_length_list.append(max_length)

print(min(true_max_length_list))

Submission status: Wrong Answer

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

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

                visited[x][y] = 1
                

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

Submission status: Wrong Answer

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

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

def bfs(S, H, W, start, goal):
    INF = 100000000
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        if (x, y) == goal:
            break
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == INF:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return distance[goal[1]][goal[0]]

ans = 0
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if (i, j) == (k, l) or S[i][j] == "#" or S[k][l] == "#":
                    continue
                if i < H/3 or j < W/3 or k < H/3 or l < W/3:
                    continue
                start = (j, i)
                goal = (l, k)
                ans = max(ans, bfs(S, H, W, start, goal))
print(ans)

Submission status: Wrong Answer

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

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

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

    print(max_step)


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


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

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


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


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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np

H, W = [int(x) for x in input().split()]
maze = np.zeros((H, W))

for i in range(H):
    for j, way in enumerate(input()):
        if way == '.':
            maze[i, j] = 1
        else:
            maze[i, j] = 0

able_list = []

for i in range(H):
    for j in range(W):
        able = []
        if maze[i,j] == 1:
            if 0 <= i-1 < H:
                if maze[i, j] == 1:
                    able.append([i * W + j, 1])
            if 0 <= j-1 < W:
                if maze[i, j-1] == 1:
                    able.append([i * W + j - 1, 1])
            if 0 <= j+1 < W:
                if maze[i, j+1] == 1:
                    able.append([i* W + j + 1, 1])
            if 0 <= i+1 < H:
                if maze[i+1, j] == 1:
                    able.append([(i+1)*W + j, 1])
        able_list.append(able)



def Dijkstra(list_adjlist, initnode):
    # list_Dを初期化
    list_D = [-1] * len(list_adjlist)
    # 始点の距離=0
    list_D[initnode] = 0
    # list_Tを初期化
    list_T = [-1] * len(list_adjlist)
    # 最短経路・距離が確定している点のリスト
    list_check = [False] * len(list_adjlist)
    # ヒープの初期化：暫定最短距離と点の名前をペアにしたリストをヒープに格納する
    list_S = []
    heapq.heappush(list_S, (list_D[initnode], initnode))
    # ヒープが空になるまで続ける
    while(len(list_S)):
        # ヒープから暫定最短距離が小さい点を取り出す
        pair_w_node = heapq.heappop(list_S)
        if list_check[pair_w_node[1]] is False:
            list_check[pair_w_node[1]] = True
            # 点pair_w_node[1]の各隣接点について調べる
            for neighbor in list_adjlist[pair_w_node[1]]:
                if list_D[neighbor[0]] == -1 or list_D[neighbor[0]] > list_D[pair_w_node[1]] + neighbor[1]:
                    list_D[neighbor[0]] = list_D[pair_w_node[1]] + neighbor[1]
                    list_T[neighbor[0]] = pair_w_node[1]
                    heapq.heappush(list_S, (list_D[neighbor[0]], neighbor[0]))
    return list_D, list_T

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i, j] == 1:
            list_D, list_T = Dijkstra(able_list, i*W + j)
            if ans < max(list_D):
                ans = max(list_D)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

h,w = map(int,input().split())
s = []
wall = '#'
for i in range(h):
    s.append(input())
s = [list(i) for i in s]
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            s[i][j]=float("inf")
    s[i] = [wall] + s[i] + [wall]
s = [[wall for i in range(w+2)]] + s + [[wall for i in range(w+2)]]
tmp = copy.deepcopy(s)
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        tmp[i][j] = 0
        que = deque([[i,j]])
        while que:
            y, x = que.popleft()
            for a,b in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + a
                nx = x + b
                dist = tmp[ny][nx]
                if dist != '#':
                    if dist > tmp[y][x] + 1:
                        tmp[ny][nx] = tmp[y][x]+1
                        que.append([ny,nx])
        for k in range(1,h+1):
            for l in range(1,w+1):
                if tmp[k][l] != '#':
                    ans = max(ans,tmp[k][l])
        tmp = copy.deepcopy(s)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for start in  [[i, j] for i in range(h) for j in range(w)]:
    if g[start[0]][start[1]] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = [-1, -1]
    cur = start
    cnt = 0
    stack = deque([[cur, pre, cnt]])
    while stack:
        cur, pre, cnt = stack.pop()
        c_x, c_y = cur
        if not dp[c_x][c_y] or (dp[c_x][c_y] and dp[c_x][c_y] > cnt):
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = [cur[0] + x, cur[1] + y]
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    stack.append([next, cur, cnt + 1])

    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)

Submission status: Wrong Answer

Solution code:


H,W=map(int,input().split())
MAP=[0]*H
for i in range(H):
    MAP[i]=input()


def calc(x,y):
    CMAP=[[0 for i in range(W)]for i in range(H)]
    LIST=[0 for i in range (3)]*10**4
    t=1
    k=0
    c=0
    LIST[0]=[x,y,c]
    while(True):
        if(k==t):break
        x=LIST[k][0]
        y=LIST[k][1]
        c=LIST[k][2]
        if(x>0):
            if(CMAP[y][x-1]==0 and MAP[y][x-1]=="."):
                CMAP[y][x-1]=1
                LIST[t]=[x-1,y,c+1]
                t+=1
        if(y>0):
            if(CMAP[y-1][x]==0 and MAP[y-1][x]=="."):
                CMAP[y-1][x]=1
                LIST[t]=[x,y-1,c+1]
                t+=1
        if(x<W-1):
            if(CMAP[y][x+1]==0 and MAP[y][x+1]=="."):
                CMAP[y][x+1]=1
                LIST[t]=[x+1,y,c+1]
                t+=1
        if(y<H-1):    
            if(CMAP[y+1][x]==0 and MAP[y+1][x]=="."):
                CMAP[y+1][x]=1
                LIST[t]=[x,y+1,c+1]
                t+=1
        k+=1
    return LIST[k-1][2]

m=0

for i in range(H):
    for j in range(W):
        if MAP[i][j]=="." :
            m=max(m,calc(j,i))

print(m)

Submission status: Wrong Answer

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

def init_start(maze):
    for j in range(len(maze)):
        for i in range(len(maze[0])):
            if maze[j][i] == ".":
                sx = i
                sy = j
    return sx, sy

def calc_distance(maze):
    global maxd
    global sx, sy
    global nextx, nexty
    # Goalまでの距離としてはあり得ない数値を設定
    INF = 100000000

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

    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)

    queue = []

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

    distance[sy][sx] = 0

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

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


            if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
                if maxd < distance[y][x] + 1:
                    maxd = distance[y][x] + 1
                    nexty = ny
                    nextx = nx
        if len(queue) == 0: break

    # Goalについたらループを抜け、Goalまでの距離を返す
maxd = 0
sx, sy = init_start(maze)
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
print(maxd)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
longest = 0

for i in range(h):
    s.append(input())

# print(s)

def getMaxPath(i, j, done):
    if str(i) + str(j) in done:
        return -1
    else:
        done.add(str(i) + str(j))
        # done.append(str(i) + str(j))

    if s[i][j] == '#':
        return 0
        # return 10**10

    r, l, u, d = 0, 0, 0, 0
    # Right
    if j < w-1 and s[i][j+1] == '.':
        r = 1 + getMaxPath(i, j+1, done)

    # Left
    if j > 0 and s[i][j-1] == '.':
        l = 1 + getMaxPath(i, j-1, done)

    # Up
    if i > 0 and s[i-1][j] == '.':
        u = 1 + getMaxPath(i-1, j, done)

    # Down
    if i < h-1 and s[i+1][j] == '.':
        d = 1 + getMaxPath(i+1, j, done)

    # if r == max(r, l, u, d):
    #     return i, j+1, max(r, l, u, d)
    # if l == max(r, l, u, d):
    #     return i, j-1, max(r, l, u, d)
    # if u == max(r, l, u, d):
    #     return i, j+1, max(r, l, u, d)
    # if d == max(r, l, u, d):
    #     return i, j+1, max(r, l, u, d)

    return max(r, l, u, d)

si, sj, gi, gj = None, None, None, None

for i in range(h):
    for j in range(w):
        temp = getMaxPath(i, j, set())
        # temp = getMaxPath(i, j, [])
        if temp > longest:
            longest = temp
            si, sj = i, j

# print('start i, start j, longest will be..')
# print(si, sj, longest)

# q = deque()
# q.append((0, (si, sj)))
# done = set()

# Look for goal
def getGoal(i, j, done, dis):
    # print(i, j, dis)
    # if str(i) + str(j) in done:
    #     return -1
    # else:
    #     done.add(str(i) + str(j))

    if dis == longest:
        # print('Found goal!!', i, j)
        return i, j

    # Right
    if j < w - 1 and s[i][j + 1] == '.':
        if str(i) + str(j+1) not in done:
            done.add(str(i) + str(j+1))
            return getGoal(i, j + 1, done, dis+1)

    # Left
    if j > 0 and s[i][j - 1] == '.':
        if str(i) + str(j-1) not in done:
            done.add(str(i) + str(j-1))
            return getGoal(i, j - 1, done, dis+1)

    # Up
    if i > 0 and s[i - 1][j] == '.':
        if str(i-1) + str(j) not in done:
            done.add(str(i-1) + str(j))
            return getGoal(i - 1, j, done, dis+1)

    # Down
    if i < h - 1 and s[i + 1][j] == '.':
        if str(i+1) + str(j) not in done:
            done.add(str(i+1) + str(j))
            return getGoal(i + 1, j, done, dis+1)
    return i, j

done = set()
done.add(str(si)+str(sj))
gi, gj = getGoal(si, sj, done, 0)

# print('gi, gj:', gi, gj)

q = deque()
q.append((0, (si, sj)))
done = set()

# Look for shortest path
while q:
    dis, tup = q.popleft()
    i, j = tup[0], tup[1]

    if i == gi and j == gj:
        # print('ans(shortest):', dis)
        print(dis)
        break

    # if dis == longest:
    #     gi, gj = i, j
    #     break

    # Right
    if j < w - 1 and s[i][j + 1] == '.':
        if str(i) + str(j+1) not in done:
            done.add(str(i) + str(j+1))
            q.append((dis+1, (i, j+1)))

    # Left
    if j > 0 and s[i][j - 1] == '.':
        if str(i) + str(j-1) not in done:
            done.add(str(i) + str(j-1))
            q.append((dis+1, (i, j-1)))

    # Up
    if i > 0 and s[i - 1][j] == '.':
        if str(i-1) + str(j) not in done:
            done.add(str(i-1) + str(j))
            q.append((dis+1, (i-1, j)))

    # Down
    if i < h - 1 and s[i + 1][j] == '.':
        if str(i+1) + str(j) not in done:
            done.add(str(i+1) + str(j))
            q.append((dis+1, (i+1, j)))


'''
3 3
...
...
...


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

Submission status: Wrong Answer

Solution code:
import queue
import copy
import math

# 2つの入力を空白で分割し、数値化
H, W = map(int, input().split())

maze = []
for h in range(0, H):
    row = input()
    maze.append(list(row))


def no_wall(maze):
    for row in maze:
        if "#" in row:
            return False
    return True

answering_maze = copy.deepcopy(maze)


def in_range(row, col, maze):
    if 0 <= row < len(maze):
        if 0 <= col <len(maze[row]):
            return maze[row][col] == "."
    return False


def can_visit(row, col, maze):
    if 0 <= row < len(maze):
        if 0 <= col <len(maze[row]):
            return maze[row][col] != True
    return False


def find_start_and_goal(maze):
    # 右下へ。だめなら上
    right_direction = 0
    left_direction = 0

    visited_maze = copy.deepcopy(maze)

    for r, row in zip(range(0, len(maze)), maze):
        for c, cell in zip(range(0, len(row)), row):
            # 初めて見つけた点から探す
            if cell == ".":
                rr = r
                cc = c
                while True:
                    # 右
                    if in_range(rr, cc + 1, maze) and can_visit(rr, cc + 1, visited_maze):
                        right_direction += 1
                        cc += 1
                    # 下
                    elif in_range(rr + 1, cc, maze) and can_visit(rr + 1, cc, visited_maze):
                        right_direction += 1
                        rr += 1
                    # 上
                    elif in_range(rr - 1, cc, maze) and can_visit(rr - 1, cc, visited_maze):
                        right_direction += 1
                        rr -= 1
                    else:
                        break
                    visited_maze[rr][cc] = True

                rr = r
                cc = c
                visited_maze2 = copy.deepcopy(maze)
                while True:
                    # 左
                    if in_range(rr, cc - 1, maze) and can_visit(rr, cc - 1, visited_maze2):
                        left_direction += 1
                        cc -= 1
                    # 下
                    elif in_range(rr + 1, cc, maze) and can_visit(rr + 1, cc, visited_maze2):
                        left_direction += 1
                        rr += 1
                    # 上
                    elif in_range(rr - 1, cc, maze) and can_visit(rr - 1, cc, visited_maze2):
                        left_direction += 1
                        rr -= 1
                    else:
                        break
                    visited_maze2[rr][cc] = True

                return right_direction + left_direction


if no_wall(maze):
    print(H + W - 2)
else:
    print(find_start_and_goal(maze))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = list()
for i in range(H):
    S.append(str(input()))
x = [x for i in S for x in i]
s = len([ i for i in x if i=="#" ])
print(H*W-s-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

q = deque([])

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

ans = 0

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

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