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:
import numpy as np
H, W = map(int, input().split())
map_lis = [input() for i in range(H)]
ans = 0

def prob(x,y,h,w):
  if 0<=x<h and 0<=y<w:
    return True
  else:
    return False

def count(x,y,lis):
  if not lis[x][y]:
    return True
  else:
    return False

def maze(x,y,lis):
  if lis[x][y] == ".":
    return True
  else:
    return False

for i in range(H):
  for j in range(W):
    k = 0
    count_lis = np.zeros((H,W))
    num_lis = [[] for i in range(H*W)]
    num_lis[0].append([i,j])
    while True:
      for l in num_lis[k]:
        if prob(l[0]-1,l[1],H,W) and count(l[0]-1,l[1],count_lis) and maze(l[0]-1,l[1],map_lis):
          num_lis[k+1].append([l[0]-1,l[1]])
          count_lis[l[0]-1][l[1]] = 1
        if prob(l[0],l[1]-1,H,W) and count(l[0],l[1]-1,count_lis) and maze(l[0],l[1]-1,map_lis):
          num_lis[k+1].append([l[0],l[1]-1])
          count_lis[l[0]][l[1]-1] = 1
        if prob(l[0]+1,l[1],H,W) and count(l[0]+1,l[1],count_lis) and maze(l[0]+1,l[1],map_lis):
          num_lis[k+1].append([l[0]+1,l[1]])
          count_lis[l[0]+1][l[1]] = 1
        if prob(l[0],l[1]+1,H,W) and count(l[0],l[1]+1,count_lis) and maze(l[0],l[1]+1,map_lis):
          num_lis[k+1].append([l[0],l[1]+1])
          count_lis[l[0]][l[1]+1] = 1
      if num_lis[k+1] == []:
        break
      new_ans = 0
      for m in num_lis[1:]:
        if m != []:
          new_ans += 1
        if m == []:
          break
      ans = max(ans, new_ans)
      k += 1
    
                                           
print(ans)

Submission status: Runtime Error

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

def prob(x,y,h,w):
  if 0<=x<h and 0<=y<w:
    return True
  else:
    return False

def count(x,y,lis):
  if not lis[x][y]:
    return True
  else:
    return False

def maze(x,y,lis):
  if lis[x][y] == ".":
    return True
  else:
    return False

for i in range(H):
  for j in range(W):
    k = 0
    count_lis = np.zeros((H,W))
    num_lis = [[] for i in range(H*W)]
    num_lis[0].append([i,j])
    while True:
      for l in num_lis[k]:
        if prob(l[0]-1,l[1],H,W) and count(l[0]-1,l[1],count_lis) and maze(l[0]-1,l[1],map_lis):
          num_lis[k+1].append([l[0]-1,l[1]])
          count_lis[l[0]-1][l[1]] = 1
        if prob(l[0],l[1]-1,H,W) and count(l[0],l[1]-1,count_lis) and maze(l[0],l[1]-1,map_lis):
          num_lis[k+1].append([l[0],l[1]-1])
          count_lis[l[0]][l[1]-1] = 1
        if prob(l[0]+1,l[1],H,W) and count(l[0]+1,l[1],count_lis) and maze(l[0]+1,l[1],map_lis):
          num_lis[k+1].append([l[0]+1,l[1]])
          count_lis[l[0]+1][l[1]] = 1
        if prob(l[0],l[1]+1,H,W) and count(l[0],l[1]+1,count_lis) and maze(l[0],l[1]+1,map_lis):
          num_lis[k+1].append([l[0],l[1]+1])
          count_lis[l[0]][l[1]+1] = 1
      if num_lis[k+1] == []:
        break
      new_ans = 0
      for m in num_lis[1:]:
        if m != []:
          new_ans += 1
        if m == []:
          break
      ans = max(ans, new_ans)
      k += 1
    
                                           
print(new_ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
s = np.array(s)
s = (s == ".") * 1
def neext(a):
    l, m = a[0], a[1]
    if l == 0:
        if m == 0:
            return [(l, m+1), (l+1, m)]
        elif m == w - 1:
            return [(l, m-1), (l+1, m)]
        else:
            return [(l, m+1), (l, m-1), (l+1, m)]
    elif m == 0:
        if l == h - 1:
            return [(l, m+1), (l-1, m)]
        else:
            return [(l, m+1), (l+1, m), (l-1, m)]
    elif l == h - 1:
        if m == w - 1:
            return [(l, m-1), (l-1, m)]
        else:
            return [(l, m+1), (l, m-1), (l-1, m)]
    elif m == w - 1:
        return [(l, m-1), (l+1, m), (l-1, m)]
    else:
        return [(l, m+1), (l, m-1), (l+1, m), (l-1, m)]
def solve(i, j):
    if s[i][j] == 0:
        return 0
    else:
        pre = 0
        p = np.full_like(s, -1)
        check = deque([((-1, -1), (i, j), 0)])#(from,now, dist)
        while check:
            From, now, d = check.popleft()
            p[now[0]][now[1]] = d
            pre = max(pre, d)
            for b, c in neext((now[0], now[1])):
                if (b == From[0] and c == From[1]) or p[b][c] != -1 or s[b][c] == 0:
                    continue
                else:
                    check.append(((i, j), (b, c), d + 1))
        return pre
ans = 0
for H in range(len(s)):
    for W in range(len(s[0])):
        ans = max(ans, solve(H, W))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
s = np.array(s)
s = (s == ".") * 1
def neext(a):
    l, m = a[0], a[1]
    if l == 0:
        if m == 0:
            return [(l, m+1), (l+1, m)]
        elif m == w - 1:
            return [(l, m-1), (l+1, m)]
        else:
            return [(l, m+1), (l, m-1), (l+1, m)]
    elif m == 0:
        if l == h - 1:
            return [(l, m+1), (l-1, m)]
        else:
            return [(l, m+1), (l+1, m), (l-1, m)]
    elif l == h - 1:
        if m == w - 1:
            return [(l, m-1), (l-1, m)]
        else:
            return [(l, m+1), (l, m-1), (l-1, m)]
    elif m == w - 1:
        return [(l, m-1), (l+1, m), (l-1, m)]
    else:
        return [(l, m+1), (l, m-1), (l+1, m), (l-1, m)]
def solve(i, j):
    if s[i][j] == 0:
        return 0
    else:
        pre = 0
        p = np.full_like(s, -1)
        check = [((-1, -1), (i, j), 0)]#(from,now, dist)
        while check:
            From, now, d = check.pop(0)
            p[now[0]][now[1]] = d
            pre = max(pre, d)
            for b, c in neext((now[0], now[1])):
                if (b == From[0] and c == From[1]) or p[b][c] != -1 or s[b][c] == 0:
                    continue
                else:
                    check.append(((i, j), (b, c), d + 1))
        return pre
ans = 0
for H in range(len(s)):
    for W in range(len(s[0])):
        ans = max(ans, solve(H, W))
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from copy import deepcopy
from collections import deque

h,w=nii()
s=[list(input()) for i in range(h)]

def dfs(cs,i,j):
  que=deque()
  que.append([i,j])

  cs[i][j]='#'

  dist=[[-1 for a in range(w)] for b in range(h)]
  dist[i][j]=0

  while que:
    y,x=que.popleft()
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and cs[ny][nx]=='.':
        que.append([ny,nx])
        cs[ny][nx]='#'
        dist[ny][nx]=dist[y][x]+1

  t_ans=0
  for a in dist:
    t_ans=max(t_ans,max(a))

  return t_ans

ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      cs=deepcopy(s)
      dist=dfs(cs,i,j)
      ans=max(ans,dist)

print(ans

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
H,W = map(int,input().split())
Maze=[list(input()) for i in range(H)]
for hi in range(0,H):
    for wi in range(0,W):
        if Maze[hi][wi]=="#":
            continue
        maze1=[[0]*W for _ in range(H)]
        stack=deque([[hi,wi]])
        while stack:
            h,w=stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h,new_w=h+i,w+j
                if new_h <0 or new_w <0 or new_h >=H or new_w >=W:
                    continue
                elif Maze[new_h][new_w]!="#" and maze1[new_h][new_w]==0:
                    maze1[new_h][new_w]=maze1[h][w]+1
                    stack.append([new_h,new_w])
        
        maze1[hi][wi]=0
        ans=max(ans,np.max(maze1))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
H,W = map(int,input().split())
Maze=[list(map(int,input().split())) for i in range(H)]
for hi in range(0,H):
    for wi in range(0,W):
        if Maze[hi][wi]=="#":
            continue
        maze1=[[0]*W for _ in range(H)]
        stack=deque([[hi,wi]])
        while stack:
            h,w=stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h,new_w=h+i,w+j
                if new_h <0 or new_w <0 or new_h >=H or new_w >=W:
                    continue
                elif Maze[new_h][new_w]!="#" and maze1[new_h][new_w]==0:
                    maze1[new_h][new_w]+=maze1[h][w]
                    stack.append([new_h,new_w])
        
        maze1[hi][wi]=0
        ans=max(ans,np.max(maze1))
print(ans)

Submission status: Runtime Error

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

import queue, itertools

dxy = ((1,0), (-1,0), (0,1), (0,-1))
ans = 0
for s, t in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '#' or S[t[0]][t[1]] == '#': continue
    
    q = queue.Queue()
    seen = [[0]*W for _ in range(H)]
    dist = [[0]*W for _ in range(H)]     

    q.put(s)
    while not q.empty():
        v = q.get()
        x, y = v[1], v[0]
        seen[y][x] = 1
        for dx, dy in dxy:
            nx, ny = x+dx, y+dy
            if nx<0 or ny<0 or nx>=W or ny>=H or S[ny][nx] == '#' or seen[ny][nx] == 1: continue
            dist[ny][nx] = dist[y][x] + 1
            q.put((ny, nx))
    
    ans = max(ans, max(map(max, dist)))

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

h, w = rm()
s = [list(rr()) for _ in range(h)]
q = collections.deque([[0, 0]])
lidx = [1, 0, 0, 1]
lidy = [0, 1, -1, 0]
cnt = [[-1]*w for _ in range(h)]
cnt[0][0] = 0
while q:
    x, y = q.popleft()
    s[x][y] = '#'
    if x == h-1 and y == w-1:
        break
    for dx, dy in zip(lidx, lidy):
        if 0 <= x+dx < w and 0 <= y+dy < h and s[x+dx][y+dy] == '.':
            q.append([x+dx, y+dy])
            cnt[x+dx][y+dy] = cnt[x][y]+1
print(cnt[h-1][w-1])

Submission status: Runtime Error

Solution code:
def MI(): return map(int, input().split())
from collections import deque
def bfs(field,s):
  q=deque([(0,s)])
  MOVE=[(-1,0),(0,-1),(1,0),(0,1)]
  dist=[[-1]*W for i in range(H)]
  d,i,j=-1,-1,-1  
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni=i+di
      nj=j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='#':
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d,i,j
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d,i,j=bfs(field,(i,j))
    ans=max(ans,d)
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
# 初期入力
import sys
input = sys.stdin.readline
H,W = (int(i) for i in input().split())
map_initial =[["#"]*(W+2) for i in range(H+2)] #周囲を壁にするため＋２
for h in range(1,H+1):
    map_initial[h] =["#"] +list(input().strip()) +["#"]

def BSF(x,y):
    dist =0
    map =deepcopy(map_initial)
    if map[x][y] =="#":
        return dist 
    dq =deque()
    dq.append((x,y))
    dq_sarch =deque()
    while len(dq) >0:
        h,w =dq.popleft()
        map[h][w] ="#" #通り済を壁にする
        if map[h+1][w]==".":
            dq_sarch.append((h+1,w))
        if map[h-1][w]==".":
            dq_sarch.append((h-1,w))
        if map[h][w+1]==".":
            dq_sarch.append((h,w+1))
        if map[h][w-1]==".":
            dq_sarch.append((h,w-1))
        if len(dq)==0:
            dq =deepcopy(dq_sarch)
            dq_sarch.clear()
            dist +=1
        #print(h,w,dist,end="\t")
    return dist-1

#スタート位置を全探索し、最長距離を探す
dist_all =[]
for i in range(1,H+1):
    for j in range(1,W+1):
        dist_all.append(BSF(i,j) )
print(max(dist_all))

Submission status: Runtime Error

Solution code:
from networkx import*
_,*s=open(i:=0)
g=[]
for t in s:
 i+=1;j=0
 for u in t:g+=[(k:=i*20+j,k+20)]*(u>'#'<(s+['#'*k])[i][j])+[(k,k+1)]*(u>'#'<t[j:=j+1])
print(max(t[i]for _,t in shortest_path_length(Graph(g))for i in t))

Submission status: Runtime Error

Solution code:
import queue
h, w = map(int, input().split())
m = []
for i in range(h):
  m.append(input())
#print(h, w)
#print(m)
q = queue.Queue()
a = []
def init():
  global a, q
  q = queue.Queue()
  a = []
  for i in range(h):
    a.append([-1] * w)

def bfs(cx, cy):
  nxs = [1, 0, -1, 0]
  nys = [0, -1, 0, 1]
  for i in range(4):
    nx = cx + nxs[i]
    ny = cy + nys[i]
    if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] == '.' and a[ny][nx] == -1:
      a[ny][nx] = a[cy][cx] + 1
      q.put([nx, ny])
  
def check(start_x, start_y, end_x, end_y):
  if m[start_y][start_x] == '#' or m[end_y][end_y] == '#':
    return 0
  if start_x == end_x and start_y == end_y:
    return 0
  
  global a, q
  init()
  q.put([start_x, start_y])
  a[start_y][start_x] = 0
  while not q.empty():
    cx, cy = q.get()
    bfs(cx, cy)
  return a[end_y][end_x]

ans = 0
for start_y in range(h):
  for start_x in range(w):
    for end_y in range(h):
      for end_x in range(w):
        ans = max(ans, check(start_x, start_y, end_x, end_y))
  
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(-(-h // 2) + 1):
    for j in range(w):
        for k in range(h // 2 - 1, h):
            for m in range(w):
                if s[i][j] == "#" or s[k][m] == "#":
                    continue
                queue = deque([[i, j, 0]])
                visited = [[0 for _ in range(w)] for _ in range(h)]
                while queue:
                    y, x, cnt = queue.popleft()
                    if y == k and x == m:
                        ans = max(ans, cnt)
                        break
                    visited[y][x] = 1
                    for p in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        y2 = y + p[0]
                        x2 = x + p[1]
                        if not (0 <= y2 < h and 0 <= x2 < w) or visited[y2][x2] == 1 or s[y2][x2] == "#":
                            continue
                        queue.append([y2, x2, cnt + 1])
# print(s)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for m in range(H):
  S.append(input())
ans=0
i,j=7,6
if S[i][j]==".":
    L=[[-1]*W for i in range(H)]
    L[i][j]=0
    q=queue.Queue()
    q.put([i,j])
    while not q.empty():
      r=q.get()
      for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
        if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==-1:
          L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
          q.put([r[0]+k,r[1]+l])
    ans=max(ans,max(list(map(lambda x: max(x),L))))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
H,W=map(int, input().split())
S=[[str(c) for c in l.strip()] for l in sys.stdin]
  
def make_a(X,i,j):
  a=[0]*4
  if (i-1)>=0:
    a[0]=X[i-1][j]
  else:
    a[0]=H*W
  if (i+1)<=H-1:
    a[1]=X[i+1][j]
  else:
    a[1]=0
  if (j-1)>0:
    a[2]=X[i][j-1]
  else:
    a[2]=0
  if (j+1)<=W-1:
    a[3]=X[i][j+1]
  else:
    a[3]=0
  return a

def len_path(i,j):
  T=[[0]*W]*H
  for c in range(H):
    for d in range(W):
      if S[c][d]=="#":
        T[c][d]=H*W
  T[i][j]=1
  for s in range(H*W):
    for T[k][l] in T:
      if T[k][l]==0:
        if not min(make_a(T,k,l))==0:
          T[k][l]=make_a(T,k,l)+1
  if max(max(T))<H*W:
    return max(max(T))-1
  else:
    return 

Q=[[0]*W]*H  
for i in range(H):
  for j in range(W):
    Q[i][j]=len_path(i,j)
print(max(max(Q)))

Submission status: Runtime Error

Solution code:
import sys
H,W=map(int, input().split())
S=[[str(c) for c in l.strip()] for l in sys.stdin]
  
def make_a(X,i,j):
  a=[0]*4
  if (i-1)>=0:
    a[0]=X[i-1][j]
  else:
    a[0]=H*W
  if (i+1)<=H-1:
    a[1]=X[i+1][j]
  else:
    a[1]=0
  if (j-1)>0:
    a[2]=X[i][j-1]
  else:
    a[2]=0
  if (j+1)<=W-1:
    a[3]=X[i][j+1]
  else:
    a[3]=0
  return a

def len_path(i,j):
  T=[[0]*W]*H
  for S[c][d] in S:
    if S[c][d]=="#":
      T[c][d]=H*W
  T[i][j]=1
  for s in range(H*W):
    for T[k][l] in T:
      if T[k][l]==0:
        if not min(make_a(T,k,l))==0:
          T[k][l]=make_a(T,k,l)+1
  if max(T)<H*W:
    return max(T)-1
  else:
    return sorted(set(T))[-2]-1

Q=[[0]*W]*H  
for i in range(H):
  for j in range(W):
    Q[i][j]=len_path(i,j)
print(max(Q))

Submission status: Runtime Error

Solution code:
H,W=map(int, input().split())
for i in range(H):
  S[i]=list(input().split())
  
def make_a(X,i,j):
  a=[0]*4
  if (i-1)>=0:
    a[0]=X[i-1][j]
  else:
    a[0]=H*W
  if (i+1)<=H-1:
    a[1]=X[i+1][j]
  else:
    a[1]=0
  if (j-1)>0:
    a[2]=X[i][j-1]
  else:
    a[2]=0
  if (j+1)<=W-1:
    a[3]=X[i][j+1]
  else:
    a[3]=0
  return a

def len_path(i,j):
  T=[[0]*W]*H
  for S[c][d] in S:
    if S[c][d]=="#":
      T[c][d]=H*W
  T[i][j]=1
  for s in range(H*W):
    for T[k][l] in T:
      if T[k][l]==0:
        if not min(make_a(T,k,l))==0:
          T[k][l]=make_a(T,k,l)+1
  if max(T)<H*W:
    return max(T)-1
  else:
    return sorted(set(T))[-2]-1

Q=[[0]*W]*H  
for i in range(H):
  for j in range(W):
    Q[i][j]=len_path(i,j)
print(max(Q))

Submission status: Runtime Error

Solution code:
H,W=map(int, input().split())
for i in range(H):
  S[i]=list(input().split())
  
def make_a(X,i,j):
  a=[0]*4
  if (i-1)>=0:
    a[0]=X[i-1][j]
  else:
    a[0]=H*W
  if (i+1)<=H-1:
    a[1]=X[i+1][j]
  else:
    a[1]=0
  if (j-1)>0:
    a[2]=X[i][j-1]
  else:
    a[2]=0
  if (j+1)<=W-1:
    a[3]=X[i][j+1]
  else:
    a[3]=0
  return a

def len_path(i,j):
  T=[[0]*W]*H
  for S[c][d] in S:
    if S[c][d]=="#":
      T[c][d]=H*W
  T[i][j]=1
  for s in range(H*W):
    for T[k][l] in T:
      if T[k][l]==0:
        if not min(make_a(T,k,l))==0:
          T[k][l]=make_a(T,k,l)+1
  if max(T)=

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = []
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      wall.add((x, y))
    else:
      start.append((x, y))

score = -1
ssize = [(-1,0),(0,-1),(1,0),(0,1)]
for xy in start:
  d = deque()
  d.append((xy[0],xy[1],0))
  step = 0
  already = set() | wall
  while len(d) > 0:
    now = d.popleft()
    already.add(now[:-1])
    step = now[2]+1
    for xs, ys in ssize:
      x,y = now[0]+xs, now[1]+ys
      if (x, y) not in already and 0 =< x < W and 0 =< y < H:
        d.append((x, y, step))
  score = max(step-1, score)
  
print(score)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = []
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      wall.add((x, H-y-1))
    else:
      if y > 0 and y < H and x > 0 and x < W:
        a = route[H-y-1+1][x] == '#'
        b = route[H-y-1][x+1] == '#'
        c = route[H-y-1-1][x] == '#'
        d = route[H-y-1][x-1] == '#'
        if (a and c) or (b and d):
          continue
      start.append((x, H-y-1))

score = -1
for xy in start:
  d = deque()
  d.append((xy[0],xy[1],0))
  step = 0
  already = set() | wall
  while len(d) > 0:
    now = d.popleft()
    already.add(now[:-1])
    step = now[2]+1
    x,y = now[0]-1, now[1]
    if (x, y) not in already and x >= 0:
      d.append((x, y, step))
    x, y = x+1, y-1
    if (x, y) not in already and y >= 0:
      d.append((x, y, step))
    x, y = x+1, y+1
    if (x, y) not in already and x < W:
      d.append((x, y, step))
    x, y = x-1, y+1
    if (x, y) not in already and y < H:
      d.append((x, y, step))
  score = max(step-1, score)
  
print(score)

Submission status: Runtime Error

Solution code:
import copy
from collections import deque

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

field = [['#']*(w+2)]
for _ in range(h):
    field.append(['#']+list(input())+['#'])
field.append(['#']*(w+2))
max_move = 0

for a in range(1,h+1):
    for b in range(1,w+1):
        maze = copy.deepcopy(field)
        qx,qy = deque(),deque()
        qx.append(a)
        qy.append(b)
        maze[a][b] = 0
        
        while True:
            if len(qy) == 0:
                break

            nx,ny = qx.popleft(),qy.popleft()
            dir_x,dir_y = [1,-1,0,0],[0,0,1,-1]
            for i in range(4):
                if maze[nx+dir_x[i]][ny+dir_y[i]] == '.':
                    maze[nx+dir_x[i]][ny+dir_y[i]] = maze[nx][ny]+1
                    qx.append(nx+dir_x[i])
                    qy.append(ny+dir_y[i])
            
        move=0
        for i in range(1,h+1):
            for j in range(1,w+1):
                if maze[i][j]!='#':
                    move = max(move,maze[i][j])
        
        max_move = max(move,max_move)

print(max_move)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

res = 0
for i in range(h):
    for j in range(w):
        dist = np.full((h, w), -1)
        dist[i][j] = 0
        d = deque()
        d.append([i, j])

        while len(d) > 0:
            pos_x, pos_y = d.popleft()
            for k in range(4):
                x, y = pos_x + dx[k], pos_y + dy[k]
                if 0 <= x < h and 0 <= y < w and s[x][y] == "." and dist[x][y] == -1:
                    dist[x][y] = dist[pos_x][pos_y] + 1
                    d.append([x, y])

        res = max(res, np.max(dist))

print(res)

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
M=999
*s,=open(0)
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+20]=u>'#'<(s+['#'*M])[i][j];j+=1;g[k][k+1]=u>'#'<t[j]
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Submission status: Runtime Error

Solution code:
#D
import queue
H,W=map(int,input().split())
P=[0 for i in range(H)]
for i in range(H):
    P[i]=str(input())

ans=0
for i in range(H*W):
    s=(i%W,i//W)
    if P[s[0]][s[1]]=="#":
        continue
    st=queue.Queue()
    st.put(s)
    log=[[-1 for i in range(W)] for j in range(H)]
    log[s[0]][s[1]]=0
    while not st.empty():
        x,y=st.get()
        for z,w in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
            if not (0<=z and 0<=w):
                continue
            elif not (z<W and w<H):
                continue
            elif P[z][w]=="." and log[z][w]==-1:
                st.put((z,w))
                log[z][w]=log[x][y]+1
                ans=max(ans,log[z][w])
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque
import sys

M = []
H = 0
W = 0
qx = deque()
qy = deque()
qc = deque()

def main():
    global M,H,W
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(list(input()))

    startX = 0
    startY = 0
    for i in range(H):
        startX = M[i].index('.')
        if startX >= 0:
            startY = i
            break

    Mtemp = deepcopy(M)

    Mtemp[startY][startX] = '#'
    qx.append(startX)
    qy.append(startY)
    qc.append(0)
    cnt = 0
    x = 0 
    y = 0

    while len(qx) !=0:
        x =  qx.popleft()
        y =  qy.popleft()
        cnt = qc.popleft()

        if x-1>=0:
            if Mtemp[y][x-1] == '.':
                Mtemp[y][x-1] = '#'
                qx.append(x-1)
                qy.append(y)
                qc.append(cnt+1)
        if x+1<W:
            if Mtemp[y][x+1] == '.':
                Mtemp[y][x+1] = '#'
                qx.append(x+1)
                qy.append(y)
                qc.append(cnt+1)
        if y-1>=0:
            if Mtemp[y-1][x] == '.':
                Mtemp[y-1][x] = '#'
                qx.append(x)
                qy.append(y-1)
                qc.append(cnt+1)
        if y+1<H:
            if Mtemp[y+1][x] == '.':
                Mtemp[y+1][x] = '#'
                qx.append(x)
                qy.append(y+1)
                qc.append(cnt+1)

    Mtemp = deepcopy(M)

    Mtemp[y][x] = '#'
    qx.append(x)
    qy.append(y)
    qc.append(0)
    cnt = 0

    while len(qx) !=0:
        x =  qx.popleft()
        y =  qy.popleft()
        cnt = qc.popleft()

        if x-1>=0:
            if Mtemp[y][x-1] == '.':
                Mtemp[y][x-1] = '#'
                qx.append(x-1)
                qy.append(y)
                qc.append(cnt+1)
        if x+1<W:
            if Mtemp[y][x+1] == '.':
                Mtemp[y][x+1] = '#'
                qx.append(x+1)
                qy.append(y)
                qc.append(cnt+1)
        if y-1>=0:
            if Mtemp[y-1][x] == '.':
                Mtemp[y-1][x] = '#'
                qx.append(x)
                qy.append(y-1)
                qc.append(cnt+1)
        if y+1<H:
            if Mtemp[y+1][x] == '.':
                Mtemp[y+1][x] = '#'
                qx.append(x)
                qy.append(y+1)
                qc.append(cnt+1)


    print(cnt)




if __name__ == '__main__':
    main()