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 sys
sys.setrecursionlimit(2000)
h,w = map(int,input().split())
s = []

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

from collections import deque

def bfs(i,j,dist):
    seen[i][j] = dist
    lis = [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]
    for place in lis:
        if place[0]<0 or place[0]>=h or place[1]<0 or place[1]>=w:
            continue
        if seen[place[0]][place[1]] != -1 or s[place[0]][place[1]]=="#":
            continue
        que.append([place[0],place[1],dist+1])
    if len(que):
        new = que.popleft()
        bfs(new[0],new[1],new[2])
    else:
        return


mx = 0
for i in range(h):
    for  j in range(w):
        if s[i][j]=="#":
            continue
        seen = [[-1 for _ in range(w)]for _ in range(h)]
        que = deque()
        bfs(i,j,0)
        mx = max(mx,max(max(seen)))
        print(seen)
#print(seen)
print(mx)

Submission status: Runtime Error

Solution code:
import copy
 
h, w = map(int, input().split())
S_outer = [input() for _ in range(h)]
 
 
def get_shortest_steps(S_inner, visited, i_inner, j_inner, steps):
    if i_inner == -1 or i_inner == h or j_inner == -1 or j_inner == w:
        return sys.maxsize
    if visited[i_inner * 20 + j_inner]:
        return sys.maxsize
    if S_inner[i_inner][j_inner] == "#":
        return sys.maxsize
    visited[i_inner * 20 + j_inner] = True
    if shortest_steps_map[i_inner * 20 + j_inner] > steps:
        shortest_steps_map[i_inner * 20 + j_inner] = steps
    get_shortest_steps(S_inner, copy.copy(visited), i_inner + 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner + 1, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner - 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner - 1, steps + 1)
    return
 
 
result = -1
for i_outer in range(h):
    for j_outer in range(w):
        visited_outer = [False] * (h * 20 + w + 1)
        shortest_steps_map = [500] * (h * 20 + w + 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer, 0)
 
        for i in range(len(shortest_steps_map)):
            if shortest_steps_map[i] == 500:
                shortest_steps_map[i] = 0
 
        if max(shortest_steps_map) > result:
            result = max(shortest_steps_map)
print(result)

Submission status: Runtime Error

Solution code:
import sys
import copy

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


def get_shortest_steps(S_inner, visited, i_inner, j_inner, steps):
    if i_inner == -1 or i_inner == h or j_inner == -1 or j_inner == w:
        return sys.maxsize
    if visited[i_inner * 20 + j_inner]:
        return sys.maxsize
    if S_inner[i_inner][j_inner] == "#":
        return sys.maxsize
    visited[i_inner * 20 + j_inner] = True
    if shortest_steps_map[i_inner * 20 + j_inner] > steps:
        shortest_steps_map[i_inner * 20 + j_inner] = steps
    get_shortest_steps(S_inner, copy.copy(visited), i_inner + 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner + 1, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner - 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner - 1, steps + 1)
    return


result = -1
for i_outer in range(h):
    for j_outer in range(w):
        visited_outer = [False] * (h * w + w + 1)
        shortest_steps_map = [500] * (h * 20 + w + 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer, 0)

        print(shortest_steps_map)
        for i in range(len(shortest_steps_map)):
            if shortest_steps_map[i] == 500:
                shortest_steps_map[i] = 0

        if max(shortest_steps_map) > result:
            result = max(shortest_steps_map)
print(result)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import deque

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

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)

Submission status: Runtime Error

Solution code:
"""
ぱっと見深さ優先探索で解ける
通った道を#にする
"""
import sys
sys.setrecursionlimit(10 ** 7)


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

print(S)

nx = [1, 0, -1, 0]
ny = [0, -1, 0, 1]

ans = 0
def dfs(h, w, count):
    if not(0 <= h < H) or not(0 <= w < W) or S[w][h] == "#":
        return max(ans, count)
    else:
        count += 1
        for i in range(4):
            dfs(h + ny[i], w + nx[i], count)
        

ans = 0
for h in range(H):
    for w in range(W):
        ans = dfs(h, w, 0)

print(ans)

Submission status: Runtime Error

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    from collections import deque
    import copy
    h,w=L()
    grid=[S() for i in range(h)]
    dist=[[-1]*w for i in range(w)]
    start=deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j]=='.':
                start.append((i,j))
                #(h,w):tuple, immutable
                
                dist[i][j]=-2
                
    def bfs(start,dist):
        ans=0
        d=0
        search=deque()
        #c=0
        while start:
            #print("#####################")
            #c+=1
            #print(c,ans)
            sty,stx=start.popleft()
            search.append((sty,stx))
            new_dist=copy.deepcopy(dist)
            new_dist[sty][stx]=0
            while search:
                tmph,tmpw=search.popleft()
                #print("$$$",end="")
                #print(tmph,tmpw,end="")
                #print("$$$")
                d=new_dist[tmph][tmpw]
                
                for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
                    new_h=tmph+dy
                    new_w=tmpw+dx
                    if new_h<0 or h<=new_h or new_w<0 or w<=new_w: continue
                    if new_dist[new_h][new_w]==-2:
                        new_dist[new_h][new_w]=d+1
                        search.append((new_h,new_w))
                        ans=max(ans,d+1)
                
                #for i in range(h):
                #    print("".join([str(a) if a>=0 else '#' if a==-1 else '.' for a in new_dist[i]]))
                #print("###")
        return ans
                
    print(bfs(start,dist)) 
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())
maze = np.array([c == "." for c in "".join(input() for _ in range(H))], dtype=np.bool)
array = np.zeros((H * W, H * W), dtype=np.bool)
N = np.arange(H * W)
R, C = np.divmod(N, W)
c_i = N[maze[N] & (C > 0) & maze[N - 1]]
r_i = N[maze[N] & (R > 0) & maze[N - W]]
array[c_i, c_i - 1] = 1
array[c_i - 1, c_i] = 1
array[r_i, r_i - W] = 1
array[r_i - W, r_i] = 1
dist = csgraph.shortest_path(array)
print(int(dist[dist < 401].max()))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix, csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
array = np.zeros((H * W, H * W), dtype=np.bool)
for n in range(H * W):
    if maze[n] == "#":
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
    if c != W - 1 and maze[n + 1] == ".":
        array[n][n + 1] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
    if r != H - 1 and maze[n + W] == ".":
        array[n][n + W] = 1
dist = csgraph.shortest_path(csr_matrix(array, dtype=np.bool, shape=(H * W, H * W)), directed=False)
print(int(dist[dist < 401].max()))

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix, csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
data = []
row = []
column = []
for n in range(H * W):
    if maze[n] == "#":
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        data.append(1)
        row.append(n)
        column.append(n - 1)
    if c != W - 1 and maze[n + 1] == ".":
        data.append(1)
        row.append(n)
        column.append(n + 1)
    if r and maze[n - W] == ".":
        data.append(1)
        row.append(n)
        column.append(n - W)
    if r != H - 1 and maze[n + W] == ".":
        data.append(1)
        row.append(n)
        column.append(n + W)
dist = csgraph.shortest_path(csr_matrix((data, (row, column)), dtype="i8", shape=(H * W, H * W)), directed=False)
print(int(dist[dist < 401].max()))

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
S = ["#"*(W+1)] + ["#"+input()+"#" for _ in range(H)] + ["#"*(W+1)]
adj = [[[[float("inf")] * W for _ in range(H)] for _ in range(W)] for _ in range(H)]
for h in range(H):
    for w in range(W):
	if S[h+1][w+1] != ".":
            continue
        adj[h][w][h][w] = 0
	for dh, dw in zip((0, 1, 0, -1), (1, 0, -1, 0)):
            if S[h+dh+1][w+dw+1] == ".":
                adj[h][w][h+dh][w+dw] = 1

from itertools import product
for (h1, h2, h3), (w1, w2, w3) in product(product(range(H), repeat=3), product(range(W), repeat=3)):
    adj[h1][w1][h3][w3] = min(adj[h1][w1][h3][w3], adj[h1][w1][h2][w2]+adj[h2][w2][h3][w3])

print(max(filter(lambda x: x != float('inf'), (adj[h1][w1][h2][w2] for (h1, w1), (h2, w2) in product(product(range(H), range(W)), repeat=2)))))

Submission status: Runtime Error

Solution code:
a = input(

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

ans = 0
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            sx, sy = (j, i)
            s = [[-1] * W for _ in range(H)]
            d = [[0] * W for _ in range(H)]

            que = deque([])
            que.append((sx, sy))
            s[sy][sx] = 1
            
            while que:
                x, y = que.popleft()
                s[y][x] = 1

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

                    if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != 1 and c[ny][nx] == '.':
                        que.append((nx, ny))
                        d[ny][nx] = d[y][x] + 1
        ans = max(ans, max([max(v) for v in d]))

print(ans)

Submission status: Runtime Error

Solution code:
import queue

h, w = map(int, input().split())
mat = ["#"*(w+2)]
for y in range(h):
  mat.append("#"+input()+"#")
mat.append("#"*(w+2))

d_mat1 = [[-1]*(w+2) for i in range(h+2)]
d_mat2 = [[-1]*(w+2) for i in range(h+2)]
q = queue.Queue()
for x in range(1, w+1):
  for y in range(1, h+1):
    if mat[x][y] == ".":
      start = (x, y)
      d_mat1[x][y] = 0
      break
q.put(start)

while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat1[x-1][y] == -1:
    d_mat1[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat1[x+1][y] == -1:
    d_mat1[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat1[x][y-1] == -1:
    d_mat1[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat1[x][y+1] == -1:
    d_mat1[x][y+1] = d+1
    q.put((x, y+1))

end = (x,y)
d_mat2[x][y] = 0
q.put(end)
while not q.empty():
  x, y = q.get()
  d = d_mat2[x][y]
  if mat[x-1][y] == "." and d_mat2[x-1][y] == -1:
    d_mat2[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat2[x+1][y] == -1:
    d_mat2[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat2[x][y-1] == -1:
    d_mat2[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat2[x][y+1] == -1:
    d_mat2[x][y+1] = d+1
    q.put((x, y+1))

print(d_mat2[x][y])

Submission status: Runtime Error

Solution code:
import queue

h, w = map(int, input().split())
mat = ["#"*(w+2)]
for y in range(h):
  mat.append("#"+input()+"#")
mat.append("#"*(w+2))

d_mat1 = [[-1]*(w+2) for i in range(h+2)]
d_mat2 = [[-1]*(w+2) for i in range(h+2)]
q = queue.Queue()
for x in range(1, w+1):
  for y in range(1, h+1):
    if mat[x][y] == ".":
      start = (x, y)
      d_mat1[x][y] = 0
q.put(start)

while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat1[x-1][y] == -1:
    d_mat1[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat1[x+1][y] == -1:
    d_mat1[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat1[x][y-1] == -1:
    d_mat1[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat1[x][y+1] == -1:
    d_mat1[x][y+1] = d+1
    q.put((x, y+1))

end = (x,y)
d_mat2[x][y] = 0
q.put(end)
while not q.empty():
  x, y = q.get()
  d = d_mat2[x][y]
  if mat[x-1][y] == "." and d_mat2[x-1][y] == -1:
    d_mat2[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat2[x+1][y] == -1:
    d_mat2[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat2[x][y-1] == -1:
    d_mat2[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat2[x][y+1] == -1:
    d_mat2[x][y+1] = d+1
    q.put((x, y+1))

print(d_mat2[x][y])

Submission status: Runtime Error

Solution code:
import queue

h, w = map(int, input().split())
mat = ["#"*(w+2)]
for y in range(h):
  mat.append("#"+input()+"#")
mat.append("#"*(w+2))

d_mat1 = [[-1]*(w+2) for i in range(h+2)]
d_mat2 = [[-1]*(w+2) for i in range(h+2)]
q = queue.Queue()
for x in range(1, w+1):
  for y in range(1, h+1):
    if mat[x][y] == ".":
      start = (x, y)
      d_mat1[x][y] = 0
q.put(start)

while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat1[x-1][y] == -1:
    d_mat1[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat1[x+1][y] == -1:
    d_mat1[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat1[x][y-1] == -1:
    d_mat1[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat1[x][y+1] == -1:
    d_mat1[x][y+1] = d+1
    q.put((x, y+1))

end = (x,y)
d_mat2[x][y] = 0
q.put(end)
while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat2[x-1][y] == -1:
    d_mat2[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat2[x+1][y] == -1:
    d_mat2[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat2[x][y-1] == -1:
    d_mat2[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat2[x][y+1] == -1:
    d_mat2[x][y+1] = d+1
    q.put((x, y+1))

print(d_mat2[x][y])

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
x = [''.join(["#"]*(w+2))]
s = x+["#"+input()+"#" for _ in range(h)]+x
ans = 0
checked_ = [[False]*(w+1) for _ in range(h+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        checked=checked.copy()
        checked[i][j]=True
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if s[pair[0]+x][pair[1]+y]=="." and [pair[0]+x,pair[1]+y] == False:
                    stack_.append([pair[0]+x,pair[1]+y])
                    checked[pair[0]+x][pair[1]+y] = True
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
from copy import deepcopy
from collections import deque
a = [input().split() for l in range(h)]
c = [[None for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            c[i][j] = -1
ans = 0
g = deque()
for l in range(h):
    for k in range(w):
        b = deepcopy(c)
        if a[l][k] == '.':
            b[l][k] = 0
            g.append((l,k))
            while len(g)>0:
                i,j = g.popleft()
                dis = b[i][j] 
                for dx,dy in ((1,0),(0,1),(-1,0), (0,-1)):
                    newi = i + dx
                    newj = j +dy
                    if newi < 0 or newi > h-1 or newj < 0 or newj > w-1:
                        continue
                    if b[newi][newj] == -1:
                        b[newi][newj] = dis + 1
                        ans = max(ans,dis+1)
                        g.append((newi,newj))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal


for i in range(0,H):
    for r in range(0,W):
        if "." in MAP[r]:
            start = [r, MAP[r].index(".")]
MAX, goal = bfs(tuple(start))
MAX, _ = bfs(tuple(goal))
print(MAX)
exit()

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal


for i in range(0,H):
    for r in range(W):
        if "." in MAP[r]:
            start = [r, MAP[r].index(".")]
MAX, goal = bfs(tuple(start))
MAX, _ = bfs(tuple(goal))
print(MAX)
exit()

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal

for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            MAX, goal = bfs(tuple([i,j]))
            break
    break

MAX, goal = bfs(tuple(goal))
print(MAX)

Submission status: Runtime Error

Solution code:
import queue
import numpy as np
h,w=map(int,input().split())
table=[]

for i in range(h):
    line=input()
    table.append(line)
max_dis=[]
for a in range(h):
    for b in range(w):
        if table[a][b]=="#":
            continue
        else:
            i=a
            j=b
            dp=[[0] w for j_ in range(h)]
            q=queue.Queue()
            dp_set=set()
            q.put((i,j))
            while not q.empty():
                i,j=q.get()
                if (i-1,j) not in dp_set and 0<=i-1 and table[i-1][j]==".":
                    dp[i-1][j]=dp[i][j]+1
                    q.put((i-1,j))
                if (i,j-1) not in dp_set and 0<=j-1 and table[i][j-1]==".":
                    dp[i][j-1]=dp[i][j]+1
                    q.put((i,j-1))
                if (i+1,j) not in dp_set and i+1<=h-1 and table[i+1][j]==".":
                    dp[i+1][j]=dp[i][j]+1
                    q.put((i+1,j))
                if (i,j+1) not in dp_set and j+1<=w-1 and table[i][j+1]==".":
                    dp[i][j+1]=dp[i][j]+1    
                    q.put((i,j+1))
                dp_set.add((i,j))
            dp=np.array(dp)
            max_dis.append(np.max(dp))
            
print(max(max_dis))

Submission status: Runtime Error

Solution code:
import queue
import numpy as np
h,w=map(int,input().split())
table=[]

for i in range(h):
    line=input()
    table.append(line)
max_dis=0
for a in range(h):
    for b in range(w):
        if table[a][b]=="#":
            continue
        else:
            i=a
            j=b
            dp=[[0]*w for j_ in range(h)]
            q=queue.Queue()
            dp_set=set()
            q.put((i,j))
            while not q.empty():
                i,j=q.get()
                if (i-1,j) not in dp_set and 0<=i-1 and table[i-1][j]==".":
                    dp[i-1][j]=dp[i][j]+1
                    q.put((i-1,j))
                if (i,j-1) not in dp_set and 0<=j-1 and table[i][j-1]==".":
                    dp[i][j-1]=dp[i][j]+1
                    q.put((i,j-1))
                if (i+1,j) not in dp_set and i+1<=h-1 and table[i+1][j]==".":
                    dp[i+1][j]=dp[i][j]+1
                    q.put((i+1,j))
                if (i,j+1) not in dp_set and j+1<=w-1 and table[i][j+1]==".":
                    dp[i][j+1]=dp[i][j]+1    
                    q.put((i,j+1))
                dp_set.add((i,j))
            dp=np.array(dp)
            max_dis=max(np.max(dp),max_dis)
            
print(max_dis)

Submission status: Runtime Error

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**5)

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

# H 3 W 5

step = 0
pattern = [[-1, 0], [1, 0], [0, 1], [0, -1]]
result = []
current_positions = [[0, 0]]
while current_positions:
    next_position = []
    step += 1
    for c_p in current_positions:
        ifStuck = True
        for pat in pattern:
            n_p = [c_p[0] + pat[0], c_p[1] + pat[1]]
            if n_p[0] >= 0 and n_p[0] < H and n_p[1] >= 0 and n_p[1] < W:
                if field[n_p[0]][n_p[1]] == '.':
                    field[n_p[0]][n_p[1]] = '#'
                    next_position.append(n_p)
                    ifStuck = False
        if ifStuck:
            result.append([step-1, c_p])
    # think when its unreachable
    current_positions = next_position
result.sort()
result.reverse()
print(result[0][0] + result[1][0])


# 計算量も考えたつもりだけど盛大にTLE。どのようなケースのことを考えられていなかったかを明確にして次に進むこと。
# 別の回答案はipadに記述済み

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
square = [list(input()) for i in range(h)]
INF = 100
def bfs(si, sj):
    que = deque([(si, sj)])
    d = [[INF] * w for i in range(h)]
    d[si][sj] = 0
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while que:
        i, j = que.popleft()
        for mi, mj in move:
            ni, nj = i + mi, j + mj
            if 0 <= ni < h and 0 <= nj < w and square[ni][nj] = '.' and d[ni][nj] == INF:
                que.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_num = 0
for i in range(h):
    for j in range(w):
        if square[i][j] == '.':
            max_ij = bfs(i, j)
            max_num = max(max_num, max_ij)
print(max_num)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ac=0
ans=[True]*n
wa=[0]*n
for i in range(m):
    p,s=input().split()
    p=int(p)-1
    if s=="AC" and ans[p]:
        ans[p]=False
        ac+=1
    elif s=="WA" and ans[p]:
        wa[p]+=1

cnt=0
for i in range(n):
    if not ans[i]:
        cnt+=wa[i]

print(ac,cnt)

Submission status: Runtime Error

Solution code:
from collections import deque

inf = float('inf')
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

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

# bfs
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#':
            continue
        dist = [[inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0]
            j = q[1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '#':
                    continue
                update(ni, nj, dist[i][j] + 1)
        
for i in range(h):
    for j in range(w):
        if dist[i][j] == inf:
            continue
        ans = max(ans, dist[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
import queue
H,W = map(int,input().split())
maze = list()
q = queue.Queue()
for i in range(H):
   maze.append( [x for x in input()])

maxim = 1
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." :
            maze_score = [[0]*W for k in range(W)]
            maze_score[i][j] = 1
            q.put([i,j])
            
        else :
            continue
        
        while(True):
            if q.empty() :
                if maze_score[x][y] > maxim:
                    maxim = maze_score[x][y]
                break
            [x,y] = q.get()
            
            
            
            
            ##top
            if x != 0:
                if (maze_score[x-1][y] ==0 or maze_score[x-1][y] > maze_score[x][y]+1) and maze[x-1][y] == ".":
                    maze_score[x-1][y] = maze_score[x][y] +1
                    q.put([x-1,y])
            ##right
            if y != W-1:
                if (maze_score[x][y+1] ==0 or maze_score[x][y+1] > maze_score[x][y]+1) and maze[x][y+1] == ".":
                    maze_score[x][y+1] = maze_score[x][y] +1
                    q.put([x,y+1])
            ##bottom
            if x != H-1:
                if (maze_score[x+1][y] ==0 or maze_score[x+1][y] > maze_score[x][y]+1) and maze[x+1][y] == ".":
                    maze_score[x+1][y] = maze_score[x][y] +1
                    q.put([x+1,y])
            ##left
            if y != 0:
                if (maze_score[x][y-1] ==0 or maze_score[x][y-1] > maze_score[x][y]+1) and maze[x][y-1] == ".":
                    maze_score[x][y-1] = maze_score[x][y] +1
                    q.put([x,y-1])
        
print(maxim-1)

Submission status: Runtime Error

Solution code:
import queue
H,W = map(int,input().split())
maze = list()
q = queue.Queue()
for i in range(H):
   maze.append( [x for x in input()])

maxim = 1
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." :
            maze_score = [[0]*W for k in range(W)]
            maze_score[i][j] = 1
            q.put([i,j])
            
        else :
            continue
        
        while(True):
            if q.empty() :
                if maze_score[x][y] > maxim:
                    maxim = maze_score[x][y]
                break
            [x,y] = q.get()
            
            
            
            
            ##top
            if x != 0:
                if maze_score[x-1][y] ==0 and maze[x-1][y] == ".":
                    maze_score[x-1][y] = maze_score[x][y] +1
                    q.put([x-1,y])
            ##right
            if y != W-1:
                if maze_score[x][y+1] ==0 and maze[x][y+1] == ".":
                    maze_score[x][y+1] = maze_score[x][y] +1
                    q.put([x,y+1])
            ##bottom
            if x != H-1:
                if maze_score[x+1][y] ==0 and maze[x+1][y] == ".":
                    maze_score[x+1][y] = maze_score[x][y] +1
                    q.put([x+1,y])
            ##left
            if y != 0:
                if maze_score[x][y-1] ==0 and maze[x][y-1] == ".":
                    maze_score[x][y-1] = maze_score[x][y] +1
                    q.put([x,y-1])
        
print(maxim-1)