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: Runtime Error

Solution code:
ad_square = [['#' for i in range(W+2)]]
ad_square += square
ad_square += [['#' for i in range(W+2)]]
numbersquare =[]
for i in range(H):
    numbersquare.append([0 for j in range(W)])
for i in range(H):
    i2 = i+1
    for j in range(W):
        j2 = j+1
        around = 0
        if ad_square[i2][j2]=='#':
            pass
        else:
            if ad_square[i2][j2-1]=='#':
                around += 1
            if ad_square[i2][j2+1]=='#':
                around += 1
            if ad_square[i2-1][j2]=='#':
                around += 1
            if ad_square[i2+1][j2]=='#':
                around += 1
            numbersquare[i2-1][j2-1] = around
number1 = 0
number2 =0
number3 =0
for i in range(len(numbersquare)):
    number1+=numbersquare[i].count(1)//2
    number2+=numbersquare[i].count(2)
    number3+=numbersquare[i].count(3)
print(sum([number1,number2,number3])-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

graph_list = []
for i in range(H):
    temp_graph_str = str(input())
    temp_list = [1 if i == "." else 0 for i in temp_graph_str]
    graph_list.append(temp_list)

graph_tree_list = []
for i in range(H):
    for j in range(W):
        temp_list = [0 for x in range(H * W)]
        if graph_list[i][j] == 1:
            if i > 0:
                if graph_list[i - 1][j] == 1:
                    temp_list[(i - 1) * W + j] = 1
            if i < H - 1:
                if graph_list[i + 1][j] == 1:
                    temp_list[(i + 1) * W + j] = 1
            if j > 0:
                if graph_list[i][j - 1] == 1:
                    temp_list[i * W + (j - 1)] = 1
            if j < H - 1:
                if graph_list[i][j + 1] == 1:
                    temp_list[i * W + (j + 1)] = 1
        graph_tree_list.append(temp_list)

graph_tree_array = np.array(graph_tree_list)

sp = shortest_path(graph_tree_array, directed=False, unweighted=True)

# print(sp)
sp[np.isinf(sp)] = 0
print(int(np.max(sp)))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

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

def clear_maze(sx, sy, maze):

    INF = 0

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

    def bfs():
        queue = []

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

        distance[sy][sx] = 0

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

            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_y_length and 0 <= ny and ny < field_x_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
        return max(distance)

    return bfs()

ans = [0 for i in range(h*w)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            sx = j
            sy = i
            ans[i*w+j]=clear_maze(sx,sy,maze)
temp = 0
t1 = 0
for i in ans:
    temp = max(ans)
    t1 = max(temp,t)
print(t1)

Submission status: Runtime Error

Solution code:
# D
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_x_length)] for j in range(field_y_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 and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()
ans = []
for i in range(H):
  for j in range(W):
    for k in range(H):
      for w in range(W):
        if (maze[i][j] != '#' and maze[k][w] != '#'):
          ans.append(clear_maze(i, j, k, w, maze))
print(max(ans))

Submission status: Runtime Error

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 put_not_all(q, y, x, d, distances):
    if distances[y-1][x] != -1:
        q.put((y-1, x, d))
    if distances[y+1][x] != -1:
        q.put((y+1, x, d))
    if distances[y][x-1] != -1:
        q.put((y, x-1, d))
    if distances[y][x+1] != -1:
        q.put((y, x+1, d))


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, init_y, init_x]
    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] == "#":
            distances[y][x] = 0
            continue
        distance = distances[y][x]
        if distance == -1:
            distances[y][x] = d
            put_all(q, y, x, d+1)
            if d > farthest[0]:
                farthest = [d, y, x]

    return farthest


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

    flag = False
    y = 0
    x = 0
    for i in range(H):
        for j in range(W):
            initial_map = [[-1 for _ in range(W)] for _ in range(H)]
            distance, y, x = solve(maze, i, j, initial_map, H, W)
            if distance > 0:
                flag = True
                break
        if flag:
            break
    initial_map = [[-1 for _ in range(W)] for _ in range(H)]
    max_distance, y, x = solve(maze, x, y, initial_map, H, W)

    print(max_distance)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import random


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

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

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            MEIJI[i][j] = 1


def findStart():
    while(True):
        x, y = random.randint(H), random.randint(W)
        if MEIJI[x][y] == 0:
            return x, y

    return False


def bfs(H, W, sx, sy):
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

if l < 0:
    l = 0

print(l)

Submission status: Runtime Error

Solution code:
from collections import deque

n, m = map(int, input().split())
d = []

mas = []
    for i in range(n):
        mas.extend(list(map(list, input().split())))
        d.append([float("inf")] * m)


def tansaku(sx, sy, d):

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

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and d[nx][ny] == float("inf")
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
        d_max = max(list([max(d[0]), max(d[n-1]), max(d[:][0]), max(d[:][m-1])]))
    return d_max

dis = 0
for i in range(n):
    dis_i = tansaku(i, 0,d)
    if dis_i > dis:
        dis = dis_i
    dis_i = tansaku(i, m-1,d)
    if dis_i > dis:
        dis = dis_i

for i in range(m):
    dis_i = tansaku(0, i,d)
    if dis_i > dis:
        dis = dis_i
    dis_i = tansaku(n-1, i,d)
    if dis_i > dis:
        dis = dis_i

print(dis)

Submission status: Runtime Error

Solution code:
from collections import deque
import itertools
h,w=map(int,input().split())
s=["#"+input()+"#" for i in range(h)]
s.insert(0,'#'*(w+2))
s.append('#'*(w+2))
def dep(s,t,p,q,time):
    print(s)
    s[p][q]=min(time,s[p][q])
    time+=1
    if t[p+1][q]=="." :
        dep(s,t,p+1,q,time)
    if t[p-1][q]=="." :
        dep(s,t,p-1,q,time)
    if t[p][q+1]=="." :
        dep(s,t,p,q+1,time)
    if t[p][q-1]=="." :
        dep(s,t,p,q-1,time)
    return max(itertools.chain.from_iterable(s))

m=0
for i in range(h):
    for j in range(w):
        if s[i+1][j+1]=='.':
            t=[[-1 for l in range(w+2)] for l2 in range(h+2)]
            time=0
            q1=deque([])
            t[i+1][j+1]=time
            q1.appendleft([i+1,j+1])
            while len(q1)!=0:
                q=q1.pop()
                time=t[q[0]][q[1]]+1
                if s[q[0]+1][q[1]]=='.' and t[q[0]][q[1]]==-1:
                    t[q[0]+1][q[1]]=time
                    q1.appendleft([q[0]+1,q[1]])
                if s[q[0] - 1][q[1]] == '.' and t[q[0]-1][q[1]] == -1:
                    t[q[0] - 1][q[1]] = time
                    q1.appendleft([q[0] - 1, q[1]])
                if s[q[0]][q[1]+1] == '.' and t[q[0]][q[1]+1] == -1:
                    t[q[0] ][q[1]+1] = time
                    q1.appendleft([q[0] , q[1]+1])
                if s[q[0]][q[1]-1] == '.' and t[q[0]][q[1]-1] == -1:
                    t[q[0] + 1][q[1]-1] = time
                    q1.appendleft([q[0], q[1]-1])
            m=max(itertools.chain.from_iterable(t),m)
print(m)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
mss=[]
for i in range(H):
    mss.append(list(map(int,input().split())))
movable_list = []
for h in range(H):
    movable_list.append([])
    for w in range(W):
        if mss[h][w] == "#":
            movable_list[h].append(0)
        else:
            if h-1 >= 0:
                if mss[h-1][w] != "#":
                    movable_list[h].append([h-1,w])
            if h+1 <=H:
                if mss[h+1][w] != "#":
                    movable_list[h].append([h+1, w])
            if w-1 >=0:
                if mss[h][w-1] != "#":
                    movable_list[h].append([h, w-1])
            if w+1 <= W:
                if mss[h][w+1] != "#":
                    movable_list[h].append([h, w+1])

max_list = [0]*(H*W)
for h in range(H):
    for w in range(W):
        canmove = movable_list[h][w]    
        pass_list = []
        if mss[h][w] != "#":
            pass_list.append([h,w])
            judge = True
            while judge:
                judge = False
                temp=[]
                for i in canmove:
                    if i not in pass_list: 
                        judge = True
                        temp.append(canmove[i[0][i[1]]])
                if judge:
                    max_list[h*W+w] +=1
                
                        
print(max(max_list))

Submission status: Runtime Error

Solution code:
def num():
    return int(input())
def nums():
    return list(map(int,input().split()))

import itertools as iter
import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

H,W = nums()
meiro = [[1] + [int(n == "#") for n in list(input())] + [1] for _ in range(H)]
meiro.insert(0,[1 for _ in range(W+2)])
meiro.insert(len(meiro),[1 for _ in range(W+2)])



import math

class MazeNode:
    def __init__(self,x,y,st,cond):
        self.x = x
        self.y = y
        self.state = st
        self.cond = cond
        self.parent = None
        self.fs = 0
        self.hs = 0
        self.gs = 0

    def calc_hs(self,gx,gy):
        dx = self.x - gx
        dy = self.y - gy
        self.hs = math.sqrt(dx ** 2 + dy ** 2)
    
    def update_gs(self):
        self.gs = self.fs - self.hs

    def set_gs(self,val):
        self.gs = val

    def set_cond(self,cond):
        if cond == "open" or cond == "close":
            self.cond = cond
        else:
            ##print("cond set error")
            pass
    
    # debug
    def show_pos(self):
        pass
        ##print("(%d:%d) %d %s" % (self.x,self.y,self.state,self.cond))

def get_min_fs_node(maze_nodes):
    # open_nodeのうちmin_fsのものを1つreturn
    res_node = None
    for row in maze_nodes:
        for node in row:
            if node.cond != "open":
                continue
            if not res_node:
                res_node = node
            elif node.fs < res_node.fs:
                res_node = node
    return res_node

def check_next_node(target_node,maze_nodes):
    # get next nods
    tx = target_node.x
    ty = target_node.y
    next_nodes = [
            maze_nodes[ty-1][tx  ],
            maze_nodes[ty  ][tx+1],
            maze_nodes[ty+1][tx  ],
            maze_nodes[ty  ][tx-1]
            ]

    # process next nodes
    target_node.update_gs()
    for node in next_nodes:
        if node.state == 1:
            continue
        f_dash = target_node.gs + node.hs + 1
        if node.cond == "none":
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "open" and f_dash < node.fs:
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "close" and f_dash < node.fs:
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node


def make_route(fin_node):
    
    r = 0
    node = fin_node

    while node.parent:
        r += 1
        node = node.parent

    return r



def checkio(data,start,goal):
    maze = data
    maze_nodes = []

    goal_pos_x,goal_pos_y = goal

    for y in range(len(maze)):
        row = []
        for x in range(len(maze[0])):
            node = MazeNode(x,y,maze[y][x],"none")
            node.calc_hs(goal_pos_x,goal_pos_y)
            row.append(node)
        maze_nodes.append(row)

    start_node = maze_nodes[start[0]][start[1]]
    start_node.set_cond("open")
    start_node.set_gs(0)
    start_node.fs = start_node.hs

    while True: # step12:repeat
        # step3,4
        target_node = get_min_fs_node(maze_nodes)
        if not target_node:
            # step3
            #print("search fail")
            return "fail"
        elif target_node.x == goal_pos_x and target_node.y == goal_pos_y:
            #step5_finish
            #print("search finish")
            #print_route(maze,target_node)
            return make_route(target_node) #step13
        else:
            # step5_continue
            target_node.set_cond("close")
            check_next_node(target_node,maze_nodes) #step6-11



    
ans = set()
goals = [(x,y) for y in range(H+2) for x in range(W + 2)]
starts = [(x,y) for y in range(H) for x in range(W)]
for s in starts:
    for g in goals:
        try:
            if meiro[s[0]][s [1]] != 1:
                r = checkio(meiro,s,g)
                if not r == "fail":ans.add(r)
        except:pass
print(max(ans))

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque
import math
H, W = map(int,input().split())
#S=list(map(list,input().split()[6:]))
S = []
for i in range(H):
    a = list(map(str,input().split()))
    S.append(a)

#まずはスタートまたはゴールになりうるマス（外側のマス）を集める
start_or_goal = []
for i in range(H):
    a = S[i][0]
    b = S[i][W-1]
    c = []
    d = []
    if a == ".":
        c.append(i)
        c.append(0)
        if c not in start_or_goal:
            start_or_goal.append(c)
    if b == ".":
        d.append(i)
        d.append(W-1)
        if d not in start_or_goal:
            start_or_goal.append(d)
for i in range(W):
    a = S[0][i]
    b = S[H-1][i]
    c = []
    d = []
    if a == ".":
        c.append(0)
        c.append(i)
        if c not in start_or_goal:
            start_or_goal.append(c)
    if b == ".":
        d.append(H-1)
        d.append(i)
        if d not in start_or_goal:
            start_or_goal.append(d)
#スタートとゴールの組み合わせが分かった。
max_root = []
def bfs(h,w,sy,sx,gy,gx,maze):

    #maze=list(map(list,raw_input.split()[6:]))
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=math.inf


    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            dist=maze[nexty][nextx]
            if dist!='#':
                if dist>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    return maze[gy-1][gx-1]

s_to_g = list(itertools.combinations(start_or_goal,2))
for i in range(len(s_to_g)):
    sy = s_to_g[i][0][0]+1
    sx = s_to_g[i][0][1]+1
    gy = s_to_g[i][1][0]+1
    gx = s_to_g[i][1][1]+1
    ans = bfs(H,W,sy,sx,gy,gx,S)
    max_root.append(ans)
ans = max(max_root)
print(ans)

Submission status: Runtime Error

Solution code:
import copy

a = 0
def search(N, m, n, i, j, H, W):
    global a
    m[i][j] = n
    if a < n:
        a = n
    if i > 0:
        if N[i-1][j] > N[i][j]+1 and m[i-1][j] != "#":
            search(N, m, n+1, i-1, j, H, W)
    if j > 0:
        if N[i][j-1] > N[i][j]+1 and m[i-1][j] != "#":
            search(N, m, n+1, i, j-1, H, W)
    if H > i+1:
        if N[i+1][j] > N[i][j]+1 and m[i-1][j] != "#":
            search(N, m, n+1, i+1, j, H, W)
    if W > j+1:
        if N[i][j+1] > N[i][j]+1 and m[i-1][j] != "#":
            search(N, m, n+1, i, j+1, H, W)

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

for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            N = [[1000000000]*H]*W
            N[i][j] = 0
            search(N, maze, 0, i, j, H, W)
print(a)

Submission status: Runtime Error

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: Runtime Error

Solution code:
from collections import deque

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

def cand_pos(i,j):
    neighbor = []
    if i==0:
        neighbor.append(maze[i+1][j])
    elif i==h-1:
        neighbor.append(maze[i-1][j])
    else:
        neighbor.append(maze[i+1][j])
        neighbor.append(maze[i-1][j])
    
    if j==0:
        neighbor.append(maze[i][j+1])
    elif j==w-1:
        neighbor.append(maze[i][j-1])
    else:
        neighbor.append(maze[i][j+1])
        neighbor.append(maze[i][j-1])
    
    if maze[i][j]!='#' and neighbor.count('.')==1:
        return True
    else:
        return False


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx,sy,gx,gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

pos_dic = {}
for i in range(h):
    for j in range(w):
        if cand_pos(i,j):
            pos_dic[i] = j
        else:
            continue

ans = 1000000

if len(pos_dic) == 0:
    ans = h+w-2
elif len(pos_dic) == 1:
    stx,sty = 0,0
    for k,v in pos_dic.items():
        glx, gly = k,v
    ans = bfs(stx, sty, glx, gly)
else:
    for k,v in pos_dic.items():
        stx, sty = k,v
        for kk, vv in pos_dic.items():
            glx, gly = kk, vv
            if stx != glx and sty != gly:
                tmp = bfs(stx, sty, glx, gly)
                ans = min(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
lists=[]
from collections import deque
d=deque()
e=deque()
field=[]
distance=0
field.append([True for i in range(w+2)])
for i in range(h):
    sub=[True]
    s=input()
    for j in range(w):
        if s[j]=="#":
            sub.append(True)
        else:
            sub.append(False)
            lists.append((i+1,j+1))
    sub.append(True)
    field.append(sub)
field.append([True for i  in range(w+2)]  )           

fieldss=field.copy()
maxi=0
for i in range(len(lists)):
        distance=0
        fields=fieldss
        sy,sx=lists[i][0],lists[i][1]
        d=deque()
        e=deque()
        d.append((sy,sx))
        fields[sy][sx]=True
        while d:
            for some in d:
                some=d.popleft()
                index1,index2=some[0],some[1]

                if fields[index1-1][index2]==False:
                    fields[index1-1][index2]=True
                    e.append((index1-1,index2))
                    
                if fields[index1+1][index2]==False:
                    fields[index1+1][index2]=True
                    e.append((index1+1,index2))
                    
                if fields[index1][index2+1]==False:
                    fields[index1][index2+1]=True
                    e.append((index1,index2+1))
                    
                if  fields[index1][index2-1]==False:
                    fields[index1][index2-1]=True
                    e.append((index1,index2-1))
        distance+=1
        d=e
        e=deque()
        maxi=max(maxi,distance)
print(maxi)

Submission status: Runtime Error

Solution code:
import copy
def dfs(x,y,z,grid,H,W):
    if(x-1>=0):
        if(grid[y][x-1]>z or grid[y][x-1]==0):
            grid[y][x-1]=z+1
            dfs(x-1,y,z+1,grid,H,W)
    if(x+1<W):
        if(grid[y][x+1]>z or grid[y][x+1]==0):
            grid[y][x+1]=z+1
            dfs(x+1,y,z+1,grid,H,W)
    if(y-1>=0):
        if(grid[y-1][x]>z or grid[y-1][x]==0):
            grid[y-1][x]=z+1
            dfs(x,y-1,z+1,grid,H,W)
    if(y+1<H):
        if(grid[y+1][x]>z or grid[y+1][x]==0):
            grid[y+1][x]=z+1
            dfs(x,y+1,z+1,grid,H,W)
    return 0


H,W=map(int,input().split())
grid=[]
tmp=[]
for i in range(H):
    S=str(input())
    tmp=[]
    for j in range(W):
        if(S[j]=="."):
            tmp.append(0)
        else:
            tmp.append(-1)
    grid.append(tmp)
ans=0
result=0
for i in range(W):
    for j in range(H):
        if(grid[j][i]==0):
            if(j-1>=0 and j+1<H and i-1>=0 and i+1<W):
                if(grid[j-1][i]+grid[j+1][i]+grid[j][i-1]+grod[i+1]<(-1)):
                        dataset=copy.deepcopy(grid)
                        dfs(i,j,1,dataset,H,W)
                        ans=max(dataset)
                        ans=max(ans)
                        result=max(result,ans)
            else:
                dataset=copy.deepcopy(grid)
                dfs(i,j,1,dataset,H,W)
                ans=max(dataset)
                ans=max(ans)
                result=max(result,ans)
print(result-1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
H,W=map(int,input().rstrip().split())
maze=[list(input().rstrip().split()) for i in range(H)]
def resolve():
    seen=[[0 for i in range(W)] for j in range(H)]
    ans=0
    for i in range(H):
        for j in range(W):
            buf=dfs(maze,seen,i,j)
            ans=max(ans,buf)

def testdfs(sx,sy,ex,ey,nowx,nowy):
    if(sx==nowx and sy==nowy):
        count=0
    if(nowx==ex and nowy==ey):
        return count
    dx=[0,0,-1,1]#上下左右
    dy=[1,-1,0,0]
    for dir in range(4):
        nx=nowx+dx[dir]
        ny=nowy+dy[dir]

        if(nx<0 or nx>=W):
            continue
        if(ny<0 or ny>=H):
            continue
        if(S[nx][S[ny]=="#"]):
            continue
        nowx=nx
        nowy=ny
        count+=1

def dfs(maze, seen, sh, sw):
    stack = deque([[sh, sw]])
    seen[sh][sw] = 1
    count=0
    while stack:
        h, w = stack.popleft()
        count+=1
        if maze[h][w] == "1":
            return count
        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  seen[new_h][new_w] == 0:#未発見
                seen[new_h][new_w] = 1#発見済みにする
                stack.append([new_h, new_w])#隣接を探索予定に
    
    return "000"

    
"""
    for i in range(H):
        for j in range(W):
            if(S[i][j]=="#"):
                for dir in range(4):
                    nx=j+dx[dir]
                    ny=i+dy[dir]

                    if(nx<0 or nx>=W):
                        continue
                    if(ny<0 or ny>=H):
                        continue

                    if(S[i][j]==S[ny][nx]):
                        break
                else:
                    print("No")
                    return
    print("Yes")
"""
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
...
..."""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 5
...#.
.#.#.
.#..."""
        output = """10"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()