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:
class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0

        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    #辺の追加
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]


    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.adjacent

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in G.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in G.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None

    #グラフの直径
    def diameter(self):
        from collections import deque
        inf=float("inf")

        u=self.vertex[0]
        T={u:inf  for u in G.adjacent}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)

        w=max(T,key=lambda x:T[x])
        T={u:inf  for u in G.adjacent}

        Q=deque([w])
        T[w]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        w=max(T,key=lambda x:T[x])
        return T[w]

#格子グラフ
def Grid_Graph(m,n):
    E=[]
    for x in range(1,m+1):
        E+=[(x,y) for y in range(1,n+1)]

    G=Graph(E)
    H=[(1,0),(0,1)]

    for y in range(1,n+1):
        for x in range(1,m+1):
            for a,b in H:
                p=x+a
                q=y+b
                if 1<=p<=m and 1<=q<=n:
                    G.add_edge((x,y),(p,q))
    return G
#====================================================
H,W=map(int,input().split())

G=Grid_Graph(W,H)
for y in range(H):
    S=input()
    for x in range(W):
        if S[x]=="#":
            G.remove_vertex((x+1,y+1))
print(G.diameter())

Submission status: Runtime Error

Solution code:
class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0

        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    #辺の追加
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]


    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.adjacent

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in G.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in G.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None

    #グラフの直径
    def diameter(self):
        from collections import deque
        inf=float("inf")

        u=self.vertex[0]
        T={u:inf  for u in G.vertex}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)

        w=max(T,key=lambda x:T[x])
        T={u:inf  for u in G.vertex}

        Q=deque([w])
        T[w]=0
        while Q:
            w=Q.popleft()
            for x in G.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        w=max(T,key=lambda x:T[x])
        return T[w]

#格子グラフ
def Grid_Graph(m,n):
    E=[]
    for x in range(1,m+1):
        E+=[(x,y) for y in range(1,n+1)]

    G=Graph(E)
    H=[(1,0),(0,1)]

    for y in range(1,n+1):
        for x in range(1,m+1):
            for a,b in H:
                p=x+a
                q=y+b
                if 1<=p<=m and 1<=q<=n:
                    G.add_edge((x,y),(p,q))
    return G
#====================================================
H,W=map(int,input().split())

G=Grid_Graph(W,H)
for y in range(H):
    S=input()
    for x in range(W):
        if S[x]=="#":
            G.remove_vertex((x+1,y+1))
print(G.diameter())

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

H,W = (int(x) for x in input().rstrip('\n').split())

m = []
for i in range(H):
  S = list(input().rstrip('\n'))
  m.append(S)
r = []
for x in range(W):
  for y in range(H):
    if m[y][x] == '.':
      r.append((x,y))
res = 0
for x,y in r:
  res_n = 0
  ok = [(x,y)]
  used = []
  while len(ok) > 0 :
    ok_n = []
    for X,Y in ok:
      if X==0:
        if Y==0:
          next = [(X+1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X+1,Y),(X,Y-1)]
        else:
          next = [(X+1,Y),(X,Y-1),(X,Y+1)]
      elif X==H-1:
        if Y==0:
          next = [(X-1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X-1,Y),(X,Y-1)]
        else:
          next = [(X-1,Y),(X,Y-1),(X,Y+1)]
      else:
        if Y==0:
          next = [(X+1,Y),(X-1,Y),(X,Y+1)]
        elif Y==H-1:
          next = [(X+1,Y),(X-1,Y),(X,Y-1)]
        else:
          next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if i not in used]
      next = [i for i in next if m[i[1]][i[0]] == '.']
      ok_n.extend(next)
    used.extend(ok)
    ok = ok_n
    res_n += 1
  if res < res_n-1:
    res = res_n-1
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque


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

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


def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == ".":
                dist = [[-1] * W for _ in range(H)]
                dist[i][j] = 0
                que = deque()
                que.append([i, j])

                while que:
                    y, x = que.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx >= W or nx < 0 or ny >= H or ny < 0:
                            continue
                        if dist[ny][nx] != -1:
                            continue
                        if maze[ny][nx] == "#":
                            continue
                        dist[ny][nx] = dist[y][x] + 1
                        que.append([ny, nx])
            
            ans = max(ans, max(max(steps) for steps in dist))
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import collections

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

def bfs(x0, y0):
    visited = [0] * h * w
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x * h + y] = 1
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if visited[nx * h + ny] == 1:
                # already visited
                continue
            v = (nx, ny, nd)
            deq.append(v)
    
    return mx

mxall = 0
for x0 in range(h):
    for y0 in range(w):
        if smat[x0][y0] == '.':
            mx = bfs(x0, y0)
            mxall = max(mxall, mx)
print(mxall)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = [int(s) for s in input().split()]
fields = []
for _ in range(H):
    fields.append(list(input()))

fields_num = []
for i in range(H):
    for j in range(W):
        fields_num.append((i, j))

dist = {}


def get_search_obj(i, j):
    ret = []
    moving_range = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    for dx, dy in moving_range:
        if 0 <= (i + dx) <= (H - 1) and 0 <= (j + dy) <= (W - 1) and fields[i + dx][j + dy] == '.':
            ret.append((i + dx, j + dy))
    return ret


def bfs(start, end):
    start = [start[0], start[1], 0]
    dq = deque([start])
    visited = [[False] * W for _ in range(H)]
    while dq:
        sx, sy, cnt = dq.pop()
        for x, y in get_search_obj(sx, sy):
            if x == end[0] and y == end[1]:
                return cnt + 1
            if not visited[x][y]:
                if not (start, (x, y)) in dist.keys():
                    dist[(start, (x, y))] = cnt + 1
                dq.appendleft([x, y, cnt + 1])
                visited[x][y] = True
    return 0


max_hop = 0
for i in range(H * W):
    for j in range(i + 1, H * W):
        h1, w1 = fields_num[i]
        h2, w2 = fields_num[j]
        if ((h1, w1), (h2, w2)) in dist.keys():
            continue

        if fields[h1][w1] == '.' and fields[h2][w2] == '.':
            max_hop = max(max_hop, bfs((h1, w1), (h2, w2)))

print(max_hop)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = [int(s) for s in input().split()]
fields = []
for _ in range(H):
    fields.append(list(input()))

fields_num = []
for i in range(H):
    for j in range(W):
        fields_num.append((i, j))

dist = {}


def get_search_obj(i, j):
    ret = []
    moving_range = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    for dx, dy in moving_range:
        if 0 <= (i + dx) <= (H - 1) and 0 <= (j + dy) <= (W - 1) and fields[i + dx][j + dy] == '.':
            ret.append((i + dx, j + dy))
    return ret


def bfs(start, end):
    start = [start[0], start[1], 0]
    dq = deque([start])
    visited = [[False] * W for _ in range(H)]
    while dq:
        sx, sy, cnt = dq.pop()
        for x, y in get_search_obj(sx, sy):
            if x == end[0] and y == end[1]:
                return cnt + 1
            if not visited[x][y]:
                if not (start, (x, y)) in dist.keys():
                    dist[(start, (x, y))] = cnt + 1
                    dist[((x, y), start)] = cnt + 1
                dq.appendleft([x, y, cnt + 1])
                visited[x][y] = True
    return 0


max_hop = 0
for i in range(H * W):
    for j in range(i + 1, H * W):
        h1, w1 = fields_num[i]
        h2, w2 = fields_num[j]
        if ((h1, w1), (h2, w2)) in dist.keys():
            continue

        if fields[h1][w1] == '.' and fields[h2][w2] == '.':
            max_hop = max(max_hop, bfs((h1, w1), (h2, w2)))

print(max_hop)

Submission status: Runtime Error

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

def bfs(x, y):
    q = []
    dp = {}
    def qpush(x, y, t):
        if 0 <= x < w and 0 <= y < h and s[y][x] != '#' and (x, y) not in dp:
            q.append((x, y))
            dp[(x, y)] = t

    qpush(x, y, 0)
    while len(q) > 0:
        (x, y) = q.pop(0)
        qpush(x + 1, y, dp[(x, y)] + 1)
        qpush(x, y - 1, dp[(x, y)] + 1)
        qpush(x - 1, y, dp[(x, y)] + 1)
        qpush(x, y + 1, dp[(x, y)] + 1)
    return (dp[(x, y)], x, y)

(t, x, y) = bfs(0, 0)
(t, x, y) = bfs(x, y)
print(t)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i++)
typedef long long ll;
#define repran(i, a,b) for (int i = a; i<b;i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using LP = pair<ll,ll>;
using P = pair<int,int>;
const int inf = 500;
int h, w;
char g[21][21];
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};

int bfs(int si, int sj){
    if (g[si][sj] == '#') return inf;
    vector<vector<int>> dist(h, vector<int>(w, inf));
    dist[si][sj] = 0;
    deque<P> q;
    q.emplace_back(si, sj);
    while (!q.empty())
    {
        P now = q.front();q.pop_front();
        int i = now.first;
        int j = now.second;
        rep(k, 4){
            int ni = i + di[k];
            int nj = j + dj[k];
            if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
            if (g[ni][nj] == '#') continue;
            if (dist[ni][nj] > dist[i][j]+1){
                dist[ni][nj] = dist[i][j] + 1;
                q.emplace_back(ni, nj);
            }
        }
        
    }
    int m = 0;
    rep(i, h) rep(j, w) {
        if (dist[i][j] == inf) continue;
        m = max(m, dist[i][j]);
    } 
    return m;
}

int main()
{
    cin >> h >> w;
    vector<vector<int>> ans(h, vector<int>(w, inf));
    rep(i, h) rep(j, w) cin >> g[i][j];
    rep(i, h) rep(j, w) {
        int m = bfs(i, j);
        ans[i][j] = m;
    }
    int m = 0;
    rep(i, h) rep(j, h) {
        if (ans[i][j] == inf) continue;
        m = max(m, ans[i][j]);
    }
    cout << m << endl;

}

Submission status: Runtime Error

Solution code:
H,W = list(map(int,input().split()))
N=H*W

#壁のノード
wall=[]
for h in range(H):
    for w_idx,w in enumerate(list(input())):
        if w == '#':
            wall.append(W*h+w_idx+1)
#道のノード        
path=[_ for _ in range(1,N+1) if _ not in wall]

#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N):
    n=n+1
    if n not in wall:
        up = n-W
        if up > 0 and up not in wall:
            ad[n].append(up)
            
        down = n+W
        if down <= N and down not in wall:
            ad[n].append(down)
            
        left = n-1
        if n % W != 1 and left not in wall:
            ad[n].append(left)
        
        right = n+1
        if n % W != 0 and right not in wall:
            ad[n].append(right)      

from collections import deque

def BFS(start):
    que = deque([start])
    visit = deque([])

    color = {}
    for n in range(N):
        color[n+1] = -1
    color[start] = 0

    depth = {}
    for n in range(N):
        depth[n+1] = -1

    depth[start]=0
    while len(que) > 0:
        start = que[0]
        for v in ad[start]:
            if color[v] == -1:
                que.append(v)
                color[v] = 0
                depth[v] = depth[start]+1

        color[start]=1
        visit.append(que.popleft())

    return depth[start]

ans=-1
for start in path:
    ans_=BFS(start)
    if ans < BFS(start):
        ans = ans_
    
#     print(start,ans_)
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
           
def bfs(sx, sy):
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sy][sx] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if s[ny][nx] != "#" and d[ny][nx] == -1:
                    q.append([nx, ny])
                    d[ny][nx] = d[y][x] + 1
    return d

def max_dim2(d):
    ret = 0
    for i in range(len(d)):
        for j in d[i]:
            ret = max(ret, j)
    return ret

ans = 0
for i in range(H):
    for j in range(W):
        if s[j][i] == ".":
            ret = bfs(i, j)
            temp = max_dim2(ret)
            ans = max(ans, temp)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
           
def bfs(sx, sy):
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sy][sx] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if s[ny][nx] != "#" and d[ny][nx] == -1:
                    q.append([nx, ny])
                    d[ny][nx] = d[y][x] + 1
    return d

def max_dim2(d):
    ret = 0
    for i in range(len(d)):
        for j in d[i]:
            ret = max(ret, j)
    return ret

ans = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            ret = bfs(i, j)
            temp = max_dim2(ret)
            ans = max(ans, temp)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
           
def bfs(sx, sy):
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sy][sx] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if s[ny][nx] != "#" and d[ny][nx] == -1:
                    q.append([nx, ny])
                    d[ny][nx] = d[y][x] + 1
    return d

def max_dim2(d):
    ret = 0
    for i in range(len(d)):
        for j in d[i]:
            ret = max(ret, j)
    return ret

ans = 0
for i in range(H):
    for j in range(W):
        if d[i][j] == ".":
            ret = bfs(i, j)
            temp = max_dim2(ret)
            ans = max(ans, temp)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
           
def bfs(sx, sy):
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sy][sx] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if s[ny][nx] != "#" and d[ny][nx] == -1:
                    q.append([nx, ny])
                    d[ny][nx] = d[y][x] + 1
    return d

def max_dim2(d):
    ret = 0
    for i in range(len(d)):
        for j in d[i]:
            ret = max(ret, j)
    return ret

ans = 0
for i in range(H):
    for j in range(W):
        if d[i][j] == ".":
            ret = bfs(j, i)
            temp = max_dim2(ret)
            ans = max(ans, temp)
print(ans)

Submission status: Runtime Error

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

dp = [[10**6]*(H*W) for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        p = H*i+j
        if i > 0 and S[i-1][j] == ".":
            dp[p][p-H] = 1
            dp[p-H][p] = 1
        if i < H-1 and S[i+1][j] == ".":
            dp[p][p+H] = 1
            dp[p+H][p] = 1
        if j > 0 and S[i][j-1] == ".":
            dp[p][p-1] = 1
            dp[p-1][p] = 1
        if j < W-1 and S[i][j+1] == ".":
            dp[p][p+1] = 1
            dp[p+1][p] = 1

for i in range(H*W):
    dp[i][i] = 0
for k in range(H*W):
    for i in range(H*W):
        for j in range(H*W):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dp[i][j] == 10**6:
            continue
        ans = max(ans, dp[i][j])
            
print(ans)

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)]
    if maze(i,j,map_lis):
      count_lis[i][j] = 1
      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
      new_ans = 0
      for m in num_lis[1:]:
        if m != []:
          new_ans += 1
        if m == []:
          break
      ans = max(ans, new_ans)
      k += 1
      if num_lis[k] == []:
        break
                                     
print(ans)

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
      new_ans = 0
      for m in num_lis[1:]:
        if m != []:
          new_ans += 1
        if m == []:
          break
      ans = max(ans, new_ans)
      k += 1
      if num_lis[k] == []:
        break
    
                                           
print(ans)

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)