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: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
mx = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[h][w] = 0
        que = deque([])
        que.append([h,w])
        while que != deque([]):
            u,v = que.pop()
            for dir in range(4):
                nu = u + dx[dir]
                nv = v + dy[dir]

                if (nu < 0) or (nu >= H) or (nv < 0) or (nv >= W):
                    continue
                if field[nu][nv] == "#":
                    continue
                if dist[nu][nv] != -1:
                    if dist[nu][nv] < dist[u][v] + 1:
                        continue
            
                que.append([nu,nv])
                dist[nu][nv] = dist[u][v] + 1
            
            
        for i in range(H):
            for j in range(W):
                if mx < dist[i][j]:
                    mx = dist[i][j]
    
print(mx)

Submission status: Time Limit Exceeded

Solution code:
inf=float("inf")  


h,w=map(int,input().split())
s=[["#"]*(w+2) for i in range(h+2)]
for i in range(h):
    s[i+1]=["#"]+list(input())+["#"]

#h,w=3,5
#s=[['#', '#', '#', '#', '#', '#', '#'], ['#', '.', '.', '.', '#', '.', '#'], ['#', '.', '#', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '#'], ['#', '#', '#', '#', '#', '#', '#']]    

nv=h*w
dp=[[inf]*nv for i in range(nv)] 

def nhw(hi,wi):
    return (hi-1)*w+wi-1

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        vij=nhw(i,j)
        if s[i-1][j]==".":
            vij2=nhw(i-1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i+1][j]==".":
            vij2=nhw(i+1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j-1]==".":
            vij2=nhw(i,j-1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j+1]==".":
            vij2=nhw(i,j+1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
for i in range(nv):
    dp[i][i]=0
           
#print(dp)
for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
#    print(dp)
#print(dp)
dpmax=0
for i in range(nv):
    for j in range(nv):
        if dp[i][j]!=inf:
            if dpmax<dp[i][j]:
                dpmax=dp[i][j]
print(dpmax)

Submission status: Time Limit Exceeded

Solution code:
"""
解法１：
startとgoalの組み合わせの全探索で調べる。
マス目の数は最大で400なので、組み合わせの数は最大で約160000.
各組み合わせごとにBFSで最短経路を調べるので、400回ループが必要。
なので計算時間としてはO(H^3W^3)

解法２：
ワーシャルフロイドで各ノードから各ノードへの最短経路を求める。
計算量としては、O(H^3W^3となる)。

実装としては解法１のほうが楽そうなのでそちらを使う。
"""

from itertools import combinations
from copy import deepcopy
from collections import deque

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

nodeList = []
for i in range(H):
    for j in range(W):
        if MAP[i][j] == ".":
            nodeList.append((i,j))

adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0
for start,goal in list(combinations(nodeList,2)):
    copyMAP = deepcopy(MAP)
    que = deque([[start,0]])
    while que:
        node,step = que.popleft()
        if node == goal:
            ans = max(ans,step)
            break
        else:
            i,j = node
            if copyMAP[i][j] == ".":
                copyMAP[i][j] == "#"
                for a,b in adjecents:
                    x = i+a
                    y = j+b
                    if 0<=x<H and 0<=y<W and copyMAP[x][y]==".":
                        que.append([(x,y),step+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
解法１：
startとgoalの組み合わせの全探索で調べる。
マス目の数は最大で400なので、組み合わせの数は最大で約16000.
各組み合わせごとにBFSで最短経路を調べるので、400回ループが必要。
なので計算時間としてはO(H^3W^3)

解法２：
ワーシャルフロイドで各ノードから各ノードへの最短経路を求める。
計算量としては、O(H^3W^3となる)。

実装としては解法１のほうが楽そうなのでそちらを使う。
"""

from itertools import combinations
from copy import deepcopy
from collections import deque

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

nodeList = []
for i in range(H):
    for j in range(W):
        if MAP[i][j] == ".":
            nodeList.append((i,j))

adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0
for start,goal in list(combinations(nodeList,2)):
    copyMAP = deepcopy(MAP)
    que = deque([[start,0]])
    while que:
        node,step = que.popleft()
        if node == goal:
            ans = max(ans,step)
            break
        else:
            i,j = node
            if copyMAP[i][j] == ".":
                copyMAP[i][j] == "#"
                for a,b in adjecents:
                    x = i+a
                    y = j+b
                    if 0<=x<H and 0<=y<W:
                        que.append([(x,y),step+1])
print(ans)

Submission status: Time Limit Exceeded

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:
      next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if i not in used]
      for i in next:
        if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0]):
          if m[i[1]][i[0]]=='.':
            ok_n.append(i)
    used.extend(ok)
    ok = ok_n
    if len(ok)>0:
      res_n += 1
  if res < res_n:
    res = res_n
print(res)

Submission status: Time Limit Exceeded

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))
M=-1
for a in G.adjacent:
    for b in G.adjacent:
        M=max(M,G.distance(a,b))
print(M)

Submission status: Time Limit Exceeded

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:
      next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0])]
      for i in next:
        if i not in used and m[i[1]][i[0]]=='.':
          ok_n.append(i)
    used.extend(ok)
    ok = ok_n
    if len(ok)>0:
      res_n += 1
  if res < res_n:
    res = res_n
print(res)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = []
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(h):
    s += [input()]
ans = 0


def dfs(d, i, j, c):
    if i < 0 or h <= i or j < 0 or w <= j:
        return
    if s[i][j] == '#' or d[i][j] <= c:
        return

    d[i][j] = c
    for y,x in v:
        dfs(d, i+y, j+x, c+1)


for i in range(h*w): 
    for j in range(h*w):
        d = [[h * w] * w for i in range(h)]
        p = (i // w, i % w)
        q = (j // w, j % w)
        if s[p[0]][p[1]] == '#' or s[q[0]][q[1]] == '#':
            continue
        dfs(d, p[0], p[1], 0)
        if d[q[0]][q[1]] < h*w:
            ans = max(d[q[0]][q[1]], ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = []
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(h):
    s += [input()]
ans = 0


def dfs(d, i, j, c):
    if i < 0 or h <= i or j < 0 or w <= j:
        return
    if s[i][j] == '#' or d[i][j] <= c:
        return

    d[i][j] = c
    for y,x in v:
        dfs(d, i+y, j+x, c+1)


for i in range(h*w):
    for j in range(h*w):
        d = [[h * w] * w for i in range(h)]
        p = (i // w, i % w)
        q = (j // w, j % w)
        if s[p[0]][p[1]] == '#' or s[q[0]][q[1]] == '#':
            continue
        dfs(d, p[0], p[1], 0)
        if d[q[0]][q[1]] < h*w:
            ans = max(d[q[0]][q[1]], ans)

print(ans)

Submission status: Time Limit Exceeded

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)
res = 0
for x in range(W):
  for y in range(H):
    if m[y][x]=='.':
      res_n = 0
      ok = [(x,y)]
      used = []
      while len(ok) > 0 :
        ok_n = []
        for X,Y in ok:
          next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
          next = [i for i in next if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0])]
          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)

Submission status: Time Limit Exceeded

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:
      next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0])]
      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
    if len(ok)>0:
      res_n += 1
  if res < res_n:
    res = res_n
print(res)

Submission status: Time Limit Exceeded

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:
      next = [(X+1,Y),(X-1,Y),(X,Y-1),(X,Y+1)]
      next = [i for i in next if all([i[0]>=0,i[0]<W,i[1]<H,i[1]>=0])]
      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
    if len(ok)>0:
      res_n += 1
  if res < res_n:
    res = res_n
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() + "#" for _ in range(H)]
S.append("#" * (W + 1))

todo = deque()
done = set()
ans = 0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw] == "#":
            continue
        s = (sh, sw)
        done.clear()
        todo.append((s, 0))
        while todo:
            p, count = todo.popleft()
            ans = max(ans, count)
            done.add(p)
            ncount = count + 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh = p[0] + dh
                nw = p[1] + dw
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np in done:
                    continue
                todo.append((np, ncount))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
ROAD = set()
for h in range(H):
    for w, c in enumerate(sys.stdin.readline()):
        if c == ".":
            ROAD.add((h, w))

todo = deque()
done = set()
ans = 0
for s in ROAD:
    done.clear()
    todo.append((s, 0))
    while todo:
        p, count = todo.popleft()
        ans = max(ans, count)
        done.add(p)
        ncount = count + 1
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            np = (p[0] + dh, p[1] + dw)
            if not np in ROAD or np in done:
                continue
            todo.append((np, ncount))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
S.append(['#' for _ in range(W+2)])
for _ in range(H):
  s = input()
  s = '#' + s + '#'
  S.append([])
  for k in range(W+2):
    S[-1].append(s[k])
S.append(['#' for _ in range(W+2)])
b = 0
start = []
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h][w] == '.':
      c = 0
      b += 1
      if S[h+1][w] == '.':
        c += 1
      if S[h-1][w] == '.':
        c += 1
      if S[h][w+1] == '.':
        c += 1
      if S[h][w-1] == '.':
        c += 1
      if c == 1:
        start.append([h, w])
if len(start) == 0:
  for h in range(1, H+1):
    for w in range(1, W+1):
      if S[h][w] == '.':
        c = 0
        if S[h+1][w] == '.':
          c += 1
        if S[h-1][w] == '.':
          c += 1
        if S[h][w+1] == '.':
          c += 1
        if S[h][w-1] == '.':
          c += 1
        if c == 2:
          start.append([h, w])
#dfs 121ms
"""
def solve(nowh, noww, point):
  counter[nowh][noww] = point
  flag = True
  if counter[nowh+1][noww] > point + 1:
    solve(nowh+1, noww, point+1)
    flag = False
  if counter[nowh-1][noww] > point + 1:
    solve(nowh-1, noww, point+1)
    flag = False
  if counter[nowh][noww+1] > point + 1:
    solve(nowh, noww+1, point+1)
    flag = False
  if counter[nowh][noww-1] > point + 1:
    solve(nowh, noww-1, point+1)
    flag = False
  if flag:
    return 0
ans = 0
for item in start:
  original_counter = [[b for _ in range(W+2)] for _ in range(H+2)]
  for k in range(H+2):
    for j in range(W+2):
      if S[k][j] == '#':
        original_counter[k][j] = -1
  counter = original_counter
  solve(item[0], item[1], 0)
  anskouho = 0
  for h in range(1, H+1):
    for w in range(1, W+1):
      anskouho = max(anskouho, counter[h][w])
  ans = max(ans, anskouho)

print(ans)
"""
#bfs
def solve(now, point):
  nextlist = []
  for n in now:
    counter[n[0]][n[1]] = point
    if counter[n[0]+1][n[1]] > point + 1:
      nextlist.append([n[0]+1, n[1]])
    if counter[n[0]][n[1]+1] > point + 1:
      nextlist.append([n[0], n[1]+1])
    if counter[n[0]-1][n[1]] > point + 1:
      nextlist.append([n[0]-1, n[1]])
    if counter[n[0]][n[1]-1] > point + 1:
      nextlist.append([n[0], n[1]-1])
  if len(nextlist) == 0:
    anskouho.append(point)
    return 0
  else:
    solve(nextlist, point+1)

anskouho = []
for item in start:
  original_counter = [[b for _ in range(W+2)] for _ in range(H+2)]
  for k in range(H+2):
    for j in range(W+2):
      if S[k][j] == '#':
        original_counter[k][j] = -1
  counter = original_counter
  solve([item], 0)
print(max(anskouho))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x][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][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: Time Limit Exceeded

Solution code:
import collections
import numpy as np

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

def bfs(x0, y0):
    visited = np.zeros((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][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][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: Time Limit Exceeded

Solution code:
import collections

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

def bfs(x0, y0):
    visited = set()
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited.add((x, y))
        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 (nx, ny) in visited:
                # 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: Time Limit Exceeded

Solution code:
import queue

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

def bfs(x0, y0):
    visited = set()
    q = queue.Queue()
    q.put((x0, y0, -1))

    mx = 0
    while not q.empty():
        x, y, d = q.get()
        nd = d + 1
        visited.add((x, y))
        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 (nx, ny) in visited:
                # already visited
                continue
            v = (nx, ny, nd)
            q.put(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: Time Limit Exceeded

Solution code:
import queue

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

def bfs(x0, y0):
    dist = {}
    q = queue.Queue()
    q.put((x0, y0, -1))

    mx = 0
    while not q.empty():
        x, y, d = q.get()
        nd = d + 1
        dist[(x, y)] = nd
        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 (nx, ny) in dist:
                # already visited
                continue
            v = (nx, ny, nd)
            q.put(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: Time Limit Exceeded

Solution code:
import queue

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

def bfs(x0, y0):
    dist = {}
    q = queue.Queue()
    q.put((x0, y0, -1))

    while not q.empty():
        x, y, d = q.get()
        nd = d + 1
        dist[(x, y)] = 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 (nx, ny) in dist:
                # already visited
                continue
            v = (nx, ny, nd)
            q.put(v)
    
    mx_key = max(dist, key=lambda k: dist[k])
    #print('x0, y0, mx_key = ', x0, y0, mx_key, dist[mx_key])
    return dist[mx_key]

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: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def bfs(table, i, j):
    dq = deque()
    seen = set()
    if table[i][j] == "#":
        return -1
    h = len(table)
    w = len(table[0])
    ans = 0
    dq.append((i, j, 0))  # x,y,distance
    while dq:
        x, y, dis = dq.popleft()
        ans = max(ans, dis)
        seen.add((x, y))
        if x > 0 and (x - 1, y) not in seen and table[x - 1][y] != "#":
            dq.append((x - 1, y, dis + 1))
        if x < h - 1 and (x + 1, y) not in seen and table[x + 1][y] != "#":
            dq.append((x + 1, y, dis + 1))
        if y > 0 and (x, y - 1) not in seen and table[x][y - 1] != "#":
            dq.append((x, y - 1, dis + 1))
        if y < w - 1 and (x, y + 1) not in seen and table[x][y + 1] != "#":
            dq.append((x, y + 1, dis + 1))
    del(seen)
    return ans


def main():
    h, w = [int(i) for i in input().strip().split()]
    grid = [list(input().strip()) for _ in range(h)]
    ans = -1
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                max_path = bfs(grid, i, j)
                ans = max(ans, max_path)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def bfs(table, i, j):
    dq = deque()
    seen = set()
    if table[i][j] == "#":
        return -1
    h = len(table)
    w = len(table[0])
    ans = 0
    dq.append((i, j, 0))  # x,y,distance
    while dq:
        x, y, dis = dq.popleft()
        ans = max(ans, dis)
        seen.add((x, y))
        if x > 0 and (x - 1, y) not in seen and table[x - 1][y] != "#":
            dq.append((x - 1, y, dis + 1))
        if x < h - 1 and (x + 1, y) not in seen and table[x + 1][y] != "#":
            dq.append((x + 1, y, dis + 1))
        if y > 0 and (x, y - 1) not in seen and table[x][y - 1] != "#":
            dq.append((x, y - 1, dis + 1))
        if y < w - 1 and (x, y + 1) not in seen and table[x][y + 1] != "#":
            dq.append((x, y + 1, dis + 1))
    return ans


def main():
    h, w = [int(i) for i in input().strip().split()]
    grid = [list(input().strip()) for _ in range(h)]
    ans = -1
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                max_path = bfs(grid, i, j)
                ans = max(ans, max_path)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def bfs(table, i, j):
    dq = deque()
    seen = []
    if table[i][j] == "#":
        return -1
    h = len(table)
    w = len(table[0])
    ans = 0
    dq.append((i, j, 0))  # x,y,distance
    while dq:
        x, y, dis = dq.popleft()
        ans = max(ans, dis)
        seen.append((x, y))
        if x > 0 and (x - 1, y) not in seen and table[x - 1][y] != "#":
            dq.append((x - 1, y, dis + 1))
        if x < h - 1 and (x + 1, y) not in seen and table[x + 1][y] != "#":
            dq.append((x + 1, y, dis + 1))
        if y > 0 and (x, y - 1) not in seen and table[x][y - 1] != "#":
            dq.append((x, y - 1, dis + 1))
        if y < w - 1 and (x, y + 1) not in seen and table[x][y + 1] != "#":
            dq.append((x, y + 1, dis + 1))
    return ans


def main():
    h, w = [int(i) for i in input().strip().split()]
    grid = [list(input().strip()) for _ in range(h)]
    ans = -1
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                max_path = bfs(grid, i, j)
                ans = max(ans, max_path)

    print(ans)


if __name__ == "__main__":
    main()