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:
#input
H, W = map(int, input().split())
import numpy as np

S = np.full((H, W), ".")
for i in range(H):
    x = input()
    for j in range(W):
        if x[j] == "#":
            S[i, j] = "#"

#output
INF = 10**5
dp = np.full((H, W), INF)

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

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

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

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

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

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                dp = np.full((H, W), INF)
                p = clear_maze(h1, w1, h2, w2, S)
                if p != INF:
                    L.append(p)

print(max(L))

Submission status: Runtime Error

Solution code:
#input
H, W = map(int, input().split())
import numpy as np

S = np.full((H, W), ".")
for i in range(H):
    x = input()
    for j in range(W):
        if x[j] == "#":
            S[i, j] = "#"

#output
import queue
INF = 10**10
dp = np.full((H, W), INF)

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

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

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

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

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

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                dp = np.full((H, W), INF)
                p = clear_maze(h1, w1, h2, w2, S)
                if p != INF:
                    L.append(p)

print(max(L))

Submission status: Runtime Error

Solution code:
import math
from collections import deque
import copy

def cha(maze,h,w):
    maze = copy.deepcopy(maze)
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                maze[i][j] = math.inf
            if maze[i][j] == "#":
                maze[i][j] = -1
    return maze

def bfs(maze,sy,sx):
    maze = copy.deepcopy(maze)
    maze[sy][sx] = 0
    que = deque([[sy,sx]])
    while que:
        y,x = que.popleft()
        for next_y,next_x in [(y+1,x),(y-1,x),(y,x+1),(y,x-1)]:
            if maze[next_y][next_x] == -1:
                continue
            dist = maze[next_y][next_x]
            if dist > maze[y][x] + 1:
                maze[next_y][next_x] = maze[y][x] + 1
                que.append([next_y,next_x])
    return maze

def search(maze):
    c = 0
    for i in maze:
        i.append(c)
        c = max(i)
    return c

def _main():
    h,w = map(int,input().split())
    maze = [["#"]*w]
    for _ in range(h):
        maze.append(list(input()))
    maze.append(["#"]*w)
    for i in range(h+2):
        maze[i].insert(0,"#")
        maze[i].insert(w+1,"#")
    C = 0
    for sy in range(h+2):
        for sx in range(w+2):
            if maze[sy][sx] == ".":
                C = max((search(bfs(cha(maze,h+2,w+2),sy,sx)),C))
    print(C)
if __name__=="__main__":
  	_main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for si in range(H):
    for sj in range(W):
      if S[si][sj] == '#':
        continue

      dist = [[-1 for _ in range(W)] for _ in range(H)]
      q = deque()

      def update(pos, num):
        i, j = pos
        if dist[i][j] != -1:
          return
        dist[i][j] = num
        q.append(pos)
        ans = max(ans, num)

      start = (si, sj)
      update(start, 0)

      while q:
        qi, qj = q.popleft()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          update((ni, nj), dist[qi][qj]+1)

    return ans


if __name__ == "__main__":
  print(main())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import queue
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for i in range(W):
    for j in range(H):
      dist = [[-1 for _ in range(W)] for _ in range(H)]
      if S[i][j] == '#':
        continue
      start = (i, j)
      q = queue.Queue()

      def update(pos, num):
        i, j = pos
        if dist[i][j] != -1:
          return
        dist[i][j] = num
        q.put(pos)
      update(start, 0)
      while not q.empty():
        qi, qj = q.get()
        for di, dj in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= W:
            continue
          if nj < 0 or nj >= H:
            continue
          if S[ni][nj] == '#':
            continue
          update((ni, nj), dist[qi][qj]+1)
      ans = max(ans, max(max(x) for x in dist))
    return ans


if __name__ == "__main__":
  print(main())

Submission status: Runtime Error

Solution code:
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited = [[False] * w for _ in range(h)]
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z + 1
                        visited[nx][ny] = True
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(2000)
h, w = map(int, input().split())
field = []
for i in range(h):
    field.append(list(input()))

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))

            while q:
                (y, x, cnt) = q.popleft()
                # print(y, x, cnt)
                for ny, nx in (y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x):
                    # if 0 <= ny < h and 0 <= nx < w and not seen[ny][nx]:
                    #     if field[ny][nx] == '.':
                    #         q.append((ny, nx, cnt + 1))
                    #         seen[y][x] = 1
                    if ny < 0 or ny >= h or nx < 0 or nx >= w:
                        pass
                    elif field[ny][nx] == '.' and seen[ny][nx] == 0:
                        q.append((ny, nx, cnt + 1))
                        seen[ny][nx] = 1
        out = max(out, cnt)
print(out)

Submission status: Runtime Error

Solution code:
from collections import deque

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

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))

            while q:
                y, x, cnt = q.popleft()
                # print(y, x, cnt)
                for ny, nx in (y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x):
                    # if 0 <= ny < h and 0 <= nx < w and not seen[ny][nx]:
                    #     if field[ny][nx] == '.':
                    #         q.append((ny, nx, cnt + 1))
                    #         seen[y][x] = 1
                    if ny < 0 or ny >= h or nx < 0 or nx >= w:
                        pass
                    elif field[ny][nx] == '.' and seen[ny][nx] == 0:
                        q.append((ny, nx, cnt + 1))
                        seen[ny][nx] = 1
        out = max(out, cnt)
print(out)

Submission status: Runtime Error

Solution code:
from collections import deque

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

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))

            while q:
                y, x, cnt = q.popleft()
                # print(y, x, cnt)
                for ny, nx in (y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x):
                    if 0 <= ny < h and 0 <= nx < w:
                        if field[ny][nx] == '.' and not seen[ny][nx]:
                            q.append((ny, nx, cnt + 1))
                            seen[y][x] = 1
        out = max(out, cnt)
print(out)

Submission status: Runtime Error

Solution code:
from collections import deque

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

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))

            while q:
                y, x, cnt = q.popleft()
                # print(y, x, cnt)
                for ny, nx in [(y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x)]:
                    if 0 <= ny < h and 0 <= nx < w and not seen[ny][nx]:
                        if field[ny][nx] == '.':
                            q.append((ny, nx, cnt + 1))
                            seen[y][x] = 1
        out = max(out, cnt)
print(out)

Submission status: Runtime Error

Solution code:
from collections import deque

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

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))

            while q:
                y, x, cnt = q.popleft()
                # print(y, x, cnt)
                for ny, nx in [(y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x)]:
                    if 0 <= ny < h and 0 <= nx < w and not seen[ny][nx]:
                        if field[ny][nx] == '.':
                            q.append((ny, nx, cnt + 1))
                            seen[y][x] = 1
        out = max(out, cnt)
print(out)

Submission status: Runtime Error

Solution code:
from collections import deque

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

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))

            while q:
                y, x, cnt = q.popleft()
                # print(y, x, cnt)
                seen[y][x] = 1
                for ny, nx in [(y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x)]:
                    if 0 <= ny < h and 0 <= nx < w and not seen[ny][nx]:
                        if field[ny][nx] == '.':
                            q.append((ny, nx, cnt + 1))
        out = max(out, cnt)
print(out)

Submission status: Runtime Error

Solution code:
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
     
    max_step = 0
    for i in range(H * W):
        sy, sx = i // W, i % W
        if S[sy][sx] == "#":
            continue
     
        steps = [[-1] * W for _ in range(H)]
        steps[sy][sx] = 0
        queue = [(sy, sx)]
        while len(queue) >= 1:
            cy, cx = queue.pop(0)
            for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                ny, nx = cy + dy, cx + dx
                if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
                    continue
                if S[ny][nx] == "#" or steps[ny][nx] >= 0:
                    continue
                queue.append((ny, nx))
                steps[ny][nx] = steps[cy][cx] + 1
     
        ms = max(max(r) for r in steps)
        max_step = max(ms, max_step)
     
    print(max_step)

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    mod = 10**9+7

    fact = [1]

    for i in range(1, n+1):
        fact.append(fact[-1]*i % mod)

    def inv_n(n, mod=10**9+7): return pow(n, mod-2, mod)
    def nCr(n, r, mod=10**9+7): return inv_n(fact[n-r]
                                             * fact[r] % mod, mod)*fact[n] % mod

    ans = 0

    for i in range(n-k+1):
        ans = (ans+nCr(n-i-1, k-1)*(a[n-i-1]-a[i])) % mod
    print(ans)


main()

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
S=[[0 for i in range(W)]for j in range(H)]
def mawari(r,c):
  no=W*(r-1)+c
  an={}
  an=set(an)
  if no%W==0:
    an=an|{no-1}
  elif no%W==1:
    an=an|{no+1}
  else:
    an=an|{no+1,no-1}
  if no<=W:
    an=an|{no+W}
  elif no>W*(H-1):
    an=an|{no-W}
  else:
    an=an|{no+W,no-W}
  return an
def longest(r,c):
  if S[r][c]=='.':
    cand=[]
    ted={}
    ted=set(ted)
    ted=ted|{W*(r-1)+c}
    cand=list(mawari(r,c))
    While cand!=[]:
      new=cand[0]
      cand=cand[1:]
      if S[new//W+1][new%W]=='.' and new not in ted:
        ted=ted|{new}
        cand=cand+[list(mawari((new//W+1),new%c)-ted)]

Submission status: Runtime Error

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

queue = []
visited = [] 
for i in range(h):
    T = [0]*w
    visited.append(T) 
    
for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            count = 0
            p = 0
            while len(queue) > 0:
              now = queue.pop(0)
              for i in range(4):
                y = now[0]+dy_dx[i][0]
                x = now[1]+dy_dx[i][1]
                if 0 <= y < h and 0 <= x < w:
                  if C[y][x] != '#' and visited[y][x] == 0:
                    visited[y][x] = visited[now[0]][now[1]]+1
                    queue.append([y,x])
                    if p == 0:
                      count += 1
                      p += 1
              p = 0
        for i in range(h):
          for j in range(w):
            ans = max(ans,visited[i][j])
        queue = []
        visited = [] 
        ans = 0
        for i in range(h):
            T = [0]*w
            visited.append(T) 
            
       
            
        
print(ans-1)

Submission status: Runtime Error

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

queue = []
visited = [] 
ans = []
for i in range(h):
    T = [0]*w
    visited.append(T) 
    
for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            count = 0
            p = 0
            while len(queue) > 0:
              now = queue.pop(0)
              for i in range(4):
                y = now[0]+dy_dx[i][0]
                x = now[1]+dy_dx[i][1]
                if 0 <= y < h and 0 <= x < w:
                  if C[y][x] != '#' and visited[y][x] == 0:
                    visited[y][x] = 1
                    queue.append([y,x])
                    if p == 0:
                      count += 1
                      p += 1
              p = 0
        ans.append(count)
        queue = []
        visited = []  
        for i in range(h):
            T = [0]*w
            visited.append(T) 
        
print(max(ans))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
g = [input() for _ in range(n)]
maze = np.array(list(map(list, g)))

from collections import deque


def dfs(s, maze):
    H, W = maze.shape

    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    visited[s[0]][s[1]] = 0

    actions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([s])

    while queue:
        x,y = queue.popleft()
        for action in actions:
            nx = x + action[0]
            ny = y + action[1]
            if nx in range(H) and ny in range(W) and maze[(nx,ny)]=='.' and visited[(nx,ny)]==-1:
                visited[(nx,ny)] = visited[(x,y)] + 1
                queue.append((nx,ny))
    return np.max(visited)
    
ret = -1

for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == '.':
            ret = max(dfs((sx,sy), maze), ret)
print(ret)

Submission status: Runtime Error

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

import numpy as np    
from collections import deque

s = (2, 0)

def dfs(s, maze):
    H, W = maze.shape

    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    visited[s[0]][s[1]] = 0

    actions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([s])

    while queue:
        c = queue.popleft()
        for action in actions:
            nc = [0,0]
            nc[0] = c[0] + action[0]
            nc[1] = c[1] + action[1]
            if nc[0] in range(H) and nc[1] in range(W) and maze[tuple(nc)]=='.' and visited[tuple(nc)]==-1:
                visited[tuple(nc)] = visited[tuple(c)] + 1
                queue.append(nc)
    return np.max(visited)

ret = -1

for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == '.':
            ret = max(dfs((sx,sy), maze), ret)
print(ret)

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
for i in range(len(CORD)):
    for j in range(i+1, len(CORD)):
        st, en = CORD[i], CORD[j]
        if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
            QUE=deque()
            visited = [[0]*W for i in range(H)]
            visited[st[0]][st[1]] = 1
            QUE.append((st[0], st[1], 0))
            res = 0
            while QUE:
                ii, jj, dist = QUE.popleft()
                if (ii, jj) == en:
                    res = dist
                    visited.clear()
                    break
                for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                    if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not visited[iii][jjj]:
                        QUE.append((iii, jjj, dist+1))
                        visited[iii][jjj]=1

            max_dist = max(res, max_dist)

print(max_dist)

Submission status: Runtime Error

Solution code:
# ABC 151 C Maze Master
from collections import deque

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

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

ans = 0
for si in range(H):
    for sj in range(W):
        if graph[si][sj] == "#": continue
        que = deque()
        que.append([si, sj])

        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        
        while que:
            y, x = que.popleft()

            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
                if ny < 0 or ny >= H or nx < 0 or nx >= W: continue
                if graph[ny][nx] == "#":continue

                if graph[ny][nx] == "." and dist[ny][nx] == -1:
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

    for i in range(H):
        for j in range(W):
            if dist[i][j] == -1: continue
            ans = max(ans, dist[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
'''input
3 3
...
...
...
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0:
				if maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n:
				if maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0:
				if maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m:
				if maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(m):
	state = list(stdin.readline().strip())
	maze.append(state)

# from random import randint
# for _ in range(1000):
# maze = []
# n = randint(1, 20)
# m = randint(1, 20)
# for i in range(n):
# 	temp = []
# 	for j in range(m):
# 		k = randint(1, 2)
# 		if k == 1:
# 			temp.append('.')
# 		else:
# 			temp.append('#')
# 	maze.append(temp)

ans = 0
done = set()
for i in range(n):
	for j in range(m):
		first = [i, j]
		ans = max(ans, bfs(first))	
print(ans)

Submission status: Runtime Error

Solution code:
# ABC 151 C Maze Master
from collections import deque

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

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

ans = 0
for si in range(H):
    for sj in range(W):
        if graph[si][sj] == "#": continue
        que = deque()
        que.append([si, sj])

        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        
        while que:
            y, x = que.popleft()

            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
                if ny < 0 or ny >= H or nx < 0 or nx >= W: continue
                if graph[ny][nx] == "#":continue

                if graph[ny][nx] == ".":
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

    for i in range(H):
        for j in range(W):
            if dist[i][j] == -1: continue
            ans = max(ans, dist[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
def bfs(x, y, S):
    s = copy.deepcopy(S)
    q = collections.deque([(x, y, 0)])
    while q:
        x, y, d = q.popleft()
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == '.':
                q += [[nx, ny, d + 1]]
                s[nx][ny] = '#'
    return x, y, d
for x,y in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S[x][y] == '.':
        s[x][y] = '#'
        break
x, y, d = bfs(x, y, S)
x, y, d = bfs(x, y, S)
print(d)

Submission status: Runtime Error

Solution code:
'''input
3 3
...
...
...
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0 and maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
				visited[mp([x -1, y])] = True
				temp.append([x - 1, y])
			if x  + 1 < n and maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
				visited[mp([x + 1, y])] = True
				temp.append([x + 1, y])
			if y - 1 >= 0 and maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
				visited[mp([x, y - 1])] = True
				temp.append([x, y - 1])
			if y + 1 < m and maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
				visited[mp([x, y + 1])] = True
				temp.append([x, y + 1])
		myq = temp
	return dist		


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(m):
	state = list(stdin.readline().strip())
	maze.append(state)

# from random import randint
# maze = []
# n = 20
# m = 20
# for i in range(20):
# 	temp = []
# 	for i in range(20):
# 		k = randint(1, 2)
# 		if k == 1:
# 			temp.append('.')
# 		else:
# 			temp.append('#')
# 	maze.append(temp)

ans = 0
done = set()
for i in range(n):
	for j in range(m):
		first = [i, j]
		ans = max(ans, bfs(first))
		
print(ans)

Submission status: Runtime Error

Solution code:
'''input
1 2
. .
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = 0
	while len(myq) > 0:
		temp = deque()
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0 and maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
				visited[mp([x -1, y])] = True
				temp.append([x - 1, y])
			if x  + 1 < n and maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
				visited[mp([x + 1, y])] = True
				temp.append([x + 1, y])
			if y - 1 >= 0 and maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
				visited[mp([x, y - 1])] = True
				temp.append([x, y - 1])
			if y + 1 < m and maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
				visited[mp([x, y + 1])] = True
				temp.append([x, y + 1])
		dist += 1
		myq = temp
	return dist		


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(m):
	state = list(stdin.readline().strip())
	maze.append(state)

# from random import randint
# maze = []
# n = 20
# m = 20
# for i in range(20):
# 	temp = []
# 	for i in range(20):
# 		k = randint(1, 2)
# 		if k == 1:
# 			temp.append('.')
# 		else:
# 			temp.append('#')
# 	maze.append(temp)

ans = 0
done = set()
for i in range(n):
	for j in range(m):
		first = [i, j]
		ans = max(ans, bfs(first))
		
print(ans - 1)

Submission status: Runtime Error

Solution code:
# ABC 151 C Maze Master
import sys
from collections import deque

input = sys.stdin.readline
H, W = map(int, input().split())          
graph = [list(input()) for _ in range(H)]

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

ans = 0
for si in range(H):
    for sj in range(W):
        if graph[si][sj] == "#": continue
        que = deque()
        que.append([si, sj])

        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        
        while que:
            y, x = que.popleft()

            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
                if ny < 0 or ny >= H or nx < 0 or nx >= W: continue
                if graph[ny][nx] == "#":continue

                if dist[ny][nx] != -1: continue

                if graph[ny][nx] == ".":
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

    for i in range(H):
        for j in range(W):
            if dist[i][j] == -1: continue
            ans = max(ans, dist[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

ans = 0
for si in range(H):
    for sj in range(W):
        if graph[si][sj] == "#": continue
        que = deque()
        que.append([si, sj])

        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        
        while que:
            y, x = que.popleft()

            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
                if ny < 0 or ny >= H or nx < 0 or nx >= W: continue
                elif graph[ny][nx] == "#":continue

                elif dist[ny][nx] != -1: continue

                elif graph[ny][nx] == ".":
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

    for i in range(H):
        for j in range(W):
            if dist[i][j] == -1: continue
            ans = max(ans, dist[i][j])

print(ans)