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: Accepted

Solution code:
from collections import deque
q = deque()

def bfs(i, j):
    q.append((i, j))
    d[i][j] = 0
    c[i][j] = 1
    m = 0
    while len(q) != 0:
        S = q.popleft()
        i, j = S[0], S[1]
        if s[i + 1][j] == "." and c[i + 1][j] == 0:
            q.append((i + 1, j))
            d[i + 1][j] = d[i][j] + 1
            c[i + 1][j] = 1
            if d[i + 1][j] > m:
                m = d[i + 1][j]
        if s[i][j + 1] == "." and c[i][j + 1] == 0:
            q.append((i, j + 1))
            d[i][j + 1] = d[i][j] + 1
            c[i][j + 1] = 1
            if d[i][j + 1] > m:
                m = d[i][j + 1]
        if s[i - 1][j] == "." and c[i - 1][j] == 0:
            q.append((i - 1, j))
            d[i - 1][j] = d[i][j] + 1
            c[i - 1][j] = 1
            if d[i - 1][j] > m:
                m = d[i - 1][j]
        if s[i][j - 1] == "." and c[i][j - 1] == 0:
            q.append((i, j - 1))
            d[i][j - 1] = d[i][j] + 1
            c[i][j - 1] = 1
            if d[i][j - 1] > m:
                m = d[i][j - 1]
        c[i][j] = 2
    return m

h, w = map(int, input().split())
s = [["#"] + list(input()) + ["#"] for _ in range(h)]
s.insert(0, ["#" for _ in range(w + 2)])
s.append(["#" for _ in range(w + 2)])
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i][j] == ".":
            d = [[-1 for _ in range(w + 2)] for _ in range(h + 2)]
            c = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
            a = bfs(i, j)
            if a > ans:
                ans = a
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
ans=0
inf=float("inf")
for i in range(h):
   for j in range(w):
      if S[i][j]!="#":
         dp=[[inf for _ in range(w)]for _ in range(h)]
         dp[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                  if dp[ni][nj]>dp[si][sj]+1:
                     dp[ni][nj]=dp[si][sj]+1
                     ans=max(ans,dp[si][sj]+1)
                     que.append((ni,nj))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

from collections import deque

H, W = input_nums()
H += 2
W += 2
grid = '#' * W
for i in range(H - 2):
    grid += '#' + input() + '#'
grid += '#' * W

def bfs(start):
    INF = 10**9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (1, -1, W, -W):
            next_v = v + move
            if grid[next_v] == '#':
                continue
            d_next_v = dv + 1
            if d_next_v >= dist[next_v]:
                continue
            dist[next_v] = d_next_v
            q.append(next_v)
    return max([x for x in dist if x < INF])

ans = max([bfs(x) for x in range(H * W) if grid[x] != '#'])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
ans=0
inf=float("inf")
for i in range(h):
   for j in range(w):
      if S[i][j]=="#":
         continue
      else:
         dp=[[inf for _ in range(w)]for _ in range(h)]
         dp[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                  if dp[ni][nj]>dp[si][sj]+1:
                     dp[ni][nj]=dp[si][sj]+1
                     ans=max(ans,dp[si][sj]+1)
                     que.append((ni,nj))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

# 最大値の格納する
ans = 0

def bfs(y,x,m):#未実装
    #表の初期化
    graph = [[None] * w for i in range(h)]
    #最初の地点のコストは0
    graph[y][x] = 0

    q = deque()
    q.append((y,x))

    for i in range(h):
        for j in range(w):
            if l[i][j] == '#':
                graph[i][j] = -1

    #ノードの移動方向 左が縦軸, 右が横軸
    move = ((0, 1), (0, -1), (1, 0), (-1, 0))

    while q: #wがからになるまで続ける while len(q):でもOK
        #que左端から取り出す
        i, j = q.popleft()

        for di, dj in move:
            #ni, nj 遷移先の座標
            ni , nj = i + di, j + dj
            #遷移先がフィールド内であるか、Noneかどうかをチェックする
            if 0 <= ni < h and 0 <= nj < w and graph[ni][nj] is None:
                #遷移可能であれば現在のコストに1足して渡す
                #print(type(graph[i][j]))
                graph[ni][nj] = graph[i][j] + 1
                #queに格納する
                q.append((ni, nj))

    #queが空になると移動コストtableが完成
    #表中の最大値返す
    return max(max(r) for r in graph)

for i in range(h):
    for j in range(w):
        #'.'であればスタート地点になり得るので、それをbfsにかける
        if l[i][j] == '.':
            d = bfs(i,j,l) # (x, y) = (j, i), lは入力の表の情報
            #返り値が現在の最大値より大きければ値を更新する
            if ans < d:
                ans = d
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
ans=0
inf=float("inf")
for i in range(h):
   for j in range(w):
      if S[i][j]!="#":
         dp=[[inf for _ in range(w)]for _ in range(h)]
         dp[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                  if dp[ni][nj]>dp[si][sj]+1:
                     dp[ni][nj]=dp[si][sj]+1
                     ans=max(ans,dp[si][sj]+1)
                     que.append((ni,nj))
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = []

for i in range(H):
    t = list(input())
    A.append(t)

tate = (-1,1,0,0)
yoko = (0,0,-1,1)
answer = 0

for i in range(H):
    for j in range(W):
        dp = [[10**4 for i in range(W)] for j in range(H)]
        if A[i][j] == '.':
            dp[i][j] = 0
            Q = list()
            Q.append([i,j])
            while(len(Q) > 0 ):
                s = Q[0][0]
                t = Q[0][1]
                for p, q in zip(tate, yoko):
                    m = s + p
                    n = t + q
                    if m >= 0 and m < H:
                        if n >= 0 and n < W:
                            if A[m][n] == '.':
                                if dp[m][n] == 10**4 :
                                    dp[m][n] = dp[s][t] + 1
                                    Q.append([m,n])
                Q.remove(Q[0])

            for k in range(H):
                for l in range(W):
                    if dp[k][l] < 10**4:
                        answer = max(answer,dp[k][l])

print(answer)

Submission status: Accepted

Solution code:
import queue

class pair:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def getter(self):
        return [self.x, self.y]

def solvmaiz(maze, x ,y):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    q = queue.Queue()
    INF = 10**5
    d = [[INF for x in range(W)]for y in range(H)]
    q.put(pair(x,y))
    d[y][x] = 0
    goal = [0, 0]
    while(not q.empty()):
        p = q.get().getter()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if nx >= 0 and nx < W and ny >= 0 and ny < H and d[ny][nx] == INF and maze[ny][nx] != '#':
                q.put(pair(nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
        goal[0] = p[1]
        goal[1] = p[0]

    return d[goal[0]][goal[1]]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze =[]
    for i in range(H):
        j = input()
        maze.append([])
        for k in j:
            maze[i].append(k)
    ans = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == '#':
                continue
            ans = max(ans, solvmaiz(maze, x, y))
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
ans=0
inf=float("inf")
for i in range(h):
   for j in range(w):
      if S[i][j]=="#":
         continue
      else:
         DP=[[inf for _ in range(w)]for _ in range(h)]
         DP[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                   if DP[ni][nj]>DP[si][sj]+1:
                      DP[ni][nj]=DP[si][sj]+1
                      ans=max(ans,DP[si][sj]+1)
                      que.append((ni,nj))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
   for j in range(w):
      if S[i][j]=="#":
         continue
      else:
         DP=[[inf for _ in range(w)]for _ in range(h)]
         DP[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                  if DP[ni][nj]>DP[si][sj]+1:
                     DP[ni][nj]=DP[si][sj]+1
                     ans=max(ans,DP[si][sj]+1)
                     que.append((ni,nj))
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=["#"+input()+"#" for an  in range(n)]
l=["#"*(m+2)]+l+["#"*(m+2)]
inf=10**7
from queue import Queue as qu
mo=[(1,0),(-1,0),(0,1),(0,-1)]
ret=0
for i in range(1,n+1):
  for j in range(1,m+1):
    if l[i][j]==".":
      q=qu()
      step=[[inf for c in range(m+2)] for x in range(n+2)]
      step[i][j]=0
      q.put((i,j))
      while not q.empty():
        d=q.get()
        for g in mo:
          c,cc=g[0]+d[0],g[1]+d[1]
          if step[c][cc]==inf and l[c][cc]==".":
            q.put((c,cc))
            step[c][cc]=step[d[0]][d[1]]+1
            ret=max(ret,step[c][cc])
print(ret)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(h, w, s, sx, sy):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    d = [[-1] * w for _ in range(h)]
    d[sx][sy] = 0
    que = deque()
    que.append((sx, sy))

    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != '#' and d[nx][ny] == -1:
                que.append((nx, ny))
                d[nx][ny] = d[x][y] + 1

    md = 0
    for i in range(h):
        for j in range(w):
          md = max(md, d[i][j])

    return md

h, w = [int(_) for _ in input().split()]
s = [0] * h
for i in range(h):
    s[i] = list(input())

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            ans = max(ans, bfs(h, w, s, i, j))

print(ans)

Submission status: Accepted

Solution code:
class BreadthFirstSearch:

    def __init__(self, h, w, maze):
        self.h = h
        self.w = w
        self.maze = maze
        self.visited = [[0] * w for _ in range(h)]
        self.queue = []
        self.dx_dy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        self.ans = 0

    def search(self):
        for i in range(self.h):
            for j in range(self.w):
                if self.maze[i][j] != ".":
                    continue
                self.queue.append((i, j))
                self.visited[i][j] = 1

                while len(self.queue) > 0:
                    now = self.queue.pop(0)
                    for dx, dy in self.dx_dy:
                        x = now[0] + dx
                        y = now[1] + dy
                        if x < 0 or self.h <= x:
                            continue
                        if y < 0 or self.w <= y:
                            continue
                        if self.maze[x][y] == "#":
                            continue
                        if self.visited[x][y] == 0:
                            self.visited[x][y] = self.visited[now[0]][now[1]] + 1
                            self.queue.append((x, y))
                for l in range(self.h):
                    for m in range(self.w):
                        self.ans = max(self.ans, self.visited[l][m])
                self.queue = []
                self.visited = [[0] * self.w for _ in range(self.h)]


def main():
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]
    bfs = BreadthFirstSearch(h, w, maze)
    bfs.search()
    print(bfs.ans-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from collections import deque

def dfs(field, s):
    MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, s)])
    dist = [[-1] * w for _ in range(h)]

    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '#':
                continue
            if dist[ni][nj] != -1:
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j

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

ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]==".":
            d,i,j=dfs(S,(i,j))
            ans=max(ans,d)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
#        for line in sys.stdin:
#            lines.append(line)
        lines.append(input())
        (h, w) = [int(e) for e in lines[0].split(" ")]
        for i in range(h):
            lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        (h, w) = [int(e) for e in lines[0].split(" ")]
    
    s = []
    for i in range(1, h + 1):
        s.append(lines[i])
        

    return (h, w, s)

def solve(h, w, s):


    result = -1
    for i in range(h):
        for j in range(w):

            if s[i][j] == "#":
                continue
            
            d = 0
            resolved = set() 
            last_resolved = set()
            last_resolved.add((i, j))
            for r in last_resolved:
                resolved.add(r)

            while True:
                neighbors_of_last_resolved = set()
                for (m, n) in last_resolved:

                    for (dm, dn) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:

                        if m+dm < 0 or h - 1 < m+dm:
                            continue

                        if n+dn < 0 or w - 1 < n+dn:
                            continue
                        
                        if s[m+dm][n+dn] == "#":
                            continue
                        else:
                            r = (m+dm, n+dn)
                            if not r in resolved:
                                neighbors_of_last_resolved.add(r)
                
                last_resolved = neighbors_of_last_resolved
                for r in last_resolved:
                    resolved.add(r)

                if len(last_resolved) == 0:
                    break
                else:
                    d = d + 1

            if d > result:
                result = d

    return result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r)
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
import copy

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

h,w = get_nums_l()

grid_s = [ input() for _ in range(h) ]
grid = [ [-1] * (w+2) for _ in range(h+2) ]

log(grid_s)

def init_grid():
    for y in range(1,h+1):
        for x in range(1, w+1):
            if grid_s[y-1][x-1] == ".":
                grid[y][x] = 999999999999999999

ans = 0
for y in range(1,h+1):
    for x in range(1, w+1):
        if grid_s[y-1][x-1] == ".":
            init_grid()
            grid[y][x] = 0

            que = deque()
            que.append((x, y, 1))

            max_ = 0
            while que:
                x,y,score = que.popleft()

                for nx,ny in neighbors4(x,y):
                    if grid[ny][nx] != -1 and grid[ny][nx] > score:
                        grid[ny][nx] = score
                        max_ = max(max_, score)
                        que.append((nx, ny, score+1))
            ans = max(ans, max_)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

def BFS(maze,check,si,sj):
    queue = deque([[si,sj]])
    check[si][sj] = 0
    maxd = 0
    while queue:
        x,y = queue.popleft()
        for k,l in ([0,1], [0,-1], [1,0], [-1,0]):
            i2, j2= x+k, y+l
            if i2<0 or i2>=h or j2<0 or j2>=w:
                continue
            if maze[i2][j2] == '.' and check[i2][j2] == -1:
                check[i2][j2] = check[x][y] + 1
                maxd = max(maxd,check[i2][j2])
                queue.append([i2,j2])
    return maxd

ans = 0
for i in range(h):
    for j in range(w):
        check = [[-1]*w for _ in range(h)]
        if maze[i][j] == '.':
            si , sj = i, j
            ans = max(ans,BFS(maze,check,si,sj))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(S,H,W,sh,sw):
    dist=[[-1]*W for i in range(H)]
    dist[sh][sw]=0

    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    lo=0
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            nh=h+dx[dir]
            nw=w+dy[dir]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(dist[nh][nw]!=-1 or S[nh][nw]=='#'):
                continue
            dist[nh][nw]=dist[h][w]+1
            lo=max(lo,dist[nh][nw])
            S[nh][nw]=='#'
            d.append([nh,nw])
    return lo

H,W=map(int,input().split())
S=[input() for i in range(H)]
ans=-1
for i in range(H):
    for j in range(W):
        if(S[i][j]!='#'):
            ans=max(ans,bfs(S,H,W,i,j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = list(map(int, input().split()))

S = [['#']*(W+2)] + [['#']+list(input())+['#'] for h in range(H)] + [['#']*(W+2)]
max_n = 0

for h1 in range(1,H+1):
  for w1 in range(1,W+1):
    if S[h1][w1] == '#':
      continue
    distance = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    distance[h1][w1] = 0
    que = deque([])
    que.append([h1,w1])
    while que:
      h, w = que.popleft()
      if S[h-1][w] == '.' and distance[h-1][w] == -1:
        que.append([h-1,w])
        distance[h-1][w] = distance[h][w] + 1
      if S[h+1][w] == '.' and distance[h+1][w] == -1:
        que.append([h+1,w])
        distance[h+1][w] = distance[h][w] + 1
      if S[h][w-1] == '.' and distance[h][w-1] == -1:
        que.append([h,w-1])
        distance[h][w-1] = distance[h][w] + 1
      if S[h][w+1] == '.' and distance[h][w+1] == -1:
        que.append([h,w+1])
        distance[h][w+1] = distance[h][w] + 1
    hw_max_n = max([max(dis) for dis in distance])
    max_n = max(max_n, hw_max_n)
print(max_n)

Submission status: Accepted

Solution code:
# from collections import deque
H, W = list(map(int, input().split()))
# dp = [[1000 for _ in range(W)] for _ in range(H)]

S = [['#']*(W+2)] + [['#']+list(input())+['#'] for h in range(H)] + [['#']*(W+2)]
# S = (H+2, W+2)
# S =  [input().split() for h in range(H)]
max_n = 0

for h1 in range(1,H+1):
  for w1 in range(1,W+1):
    if S[h1][w1] == '#':
      continue
    distance = [[1000 for _ in range(W+2)] for _ in range(H+2)]
    done_que = [[0 for _ in range(W+2)] for _ in range(H+2)]
    distance[h1][w1] = 0
    que = []
    que.append([h1,w1])
    que_i = 0
    while que_i < len(que):
      h, w = que[que_i]
      if S[h-1][w] == '.' and done_que[h-1][w] == 0:
        done_que[h-1][w] = 1
        que.append([h-1,w])
        distance[h-1][w] = min(distance[h][w] + 1, distance[h-1][w])
      if S[h+1][w] == '.' and done_que[h+1][w] == 0:
        done_que[h+1][w] = 1
        que.append([h+1,w])
        distance[h+1][w] = min(distance[h][w] + 1, distance[h+1][w])
      if S[h][w-1] == '.' and done_que[h][w-1] == 0:
        done_que[h][w-1] = 1
        que.append([h,w-1])
        distance[h][w-1] = min(distance[h][w] + 1, distance[h][w-1])
      if S[h][w+1] == '.' and done_que[h][w+1] == 0:
        done_que[h][w+1] = 1
        que.append([h,w+1])
        distance[h][w+1] = min(distance[h][w] + 1, distance[h][w+1])
      que_i += 1
    hw_max_n = 0
    for h2 in range(1,H+1):
      for w2 in range(1,W+1):
        if distance[h2][w2] != 1000:
          hw_max_n = max(hw_max_n, distance[h2][w2])
    max_n = max(max_n, hw_max_n)
print(max_n)

Submission status: Accepted

Solution code:
from collections import deque

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

max_cnt = 0

for h in range(H):
    for w in range(W):
        d = [[-1 for _ in range(W)] for _ in range(H)]
        que = deque([(h, w, 0)])
        while len(que) > 0:
            x, y, c = que.popleft()
            if x >= H or x < 0 or y >= W or y < 0:
                continue
            if d[x][y] == -1 and S[x][y] == ".":
                d[x][y] = c
                max_cnt = max(c, max_cnt)
            else:
                continue
            que.append((x + 1, y, c + 1))
            que.append((x - 1, y, c + 1))
            que.append((x, y + 1, c + 1))
            que.append((x, y - 1, c + 1))


print(max_cnt)

Submission status: Accepted

Solution code:
def main():
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j]==".":
                a[i][j]=99999
    ans=0
    import collections
    from copy import deepcopy
    direction=[[0,1],[0,-1],[1,0],[-1,0]]
    for sh in range(h):
        for sw in range(w):
            if a[sh][sw]==99999:
                field=deepcopy(a)
                field[sh][sw]=0
                next_list=collections.deque([[sh,sw]])
                while next_list:
                    n=next_list.popleft()
                    for dx,dy in direction:
                        ny,nx=n[0]+dy,n[1]+dx
                        if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="#" and field[ny][nx]==99999:
                            field[ny][nx]=field[n[0]][n[1]]+1
                            if field[ny][nx]>ans:
                                ans=field[ny][nx]
                            next_list.append([ny,nx])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j]==".":
                a[i][j]=99999
    ans=0
    import collections
    from copy import deepcopy
    direction=[[0,1],[0,-1],[1,0],[-1,0]]
    for sh in range(h):
        for sw in range(w):
            if a[sh][sw]==99999:
                field=deepcopy(a)
                field[sh][sw]=0
                next_list=collections.deque([[sh,sw]])
                while next_list:
                    n=next_list.popleft()
                    for dx,dy in direction:
                        ny,nx=n[0]+dy,n[1]+dx
                        if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="#" and field[ny][nx]==99999:
                            field[ny][nx]=field[n[0]][n[1]]+1
                            ans=max(ans,field[ny][nx])
                            next_list.append([ny,nx])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
m=np.zeros((h,w))
for i in range(h):
  for j,c in enumerate(list(input())):
    if c=='#':
      m[i,j]=-1
def dis(mc,i,j):
  if mc[i,j]!=0:return 0
  q=[(i,j,1)]
  mc[i,j]=-1
  while 0<len(q):
    i,j,x=q.pop(0)
    if i+1<h and mc[i+1,j]==0:
      mc[i+1,j]=x
      q.append((i+1,j,x+1))
    if i-1>=0 and mc[i-1,j]==0:
      mc[i-1,j]=x
      q.append((i-1,j,x+1))
    if j+1<w and mc[i,j+1]==0:
      mc[i,j+1]=x
      q.append((i,j+1,x+1))
    if j-1>=0 and mc[i,j-1]==0:
      mc[i,j-1]=x
      q.append((i,j-1,x+1))
  return np.max(mc)
max=0
for i in range(h):
  for j in range(w):
    mc = np.copy(m)
    tmp=dis(mc,i,j)
    if max<tmp:max=tmp
print(int(max))

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
#print(S)
  
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

def update(vs, i, j, x, q):
  if vs[i][j] != -1 or S[i][j] == '#':
    return
  vs[i][j] = x
  q.append((i,j))

mx = 0
for i, j in product(range(h), range(w)):
  if S[i][j] == '#':
    continue
  q = deque([])
  vs = [[-1 for i in range(w)] for j in range(h)]
  update(vs, i, j, 0, q)
  while len(q) > 0:
    #print(q)
    #print(vs)
    # x += 1
    current_q = q.popleft()
    qi, qj = current_q[0], current_q[1]
    for k in range(4):
      ni, nj = qi + di[k], qj + dj[k]
      if not(0 <= ni < h) or not(0 <= nj < w):
        continue
      update(vs, ni, nj, vs[qi][qj]+1, q)
  for i, j in product(range(h),range(w)):
    if vs[i][j] == -1:
      continue
    mx = max(mx, vs[i][j])
print(int(mx))

Submission status: Accepted

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

H, W = map(int,input().split())

maze_array = [input().split()[0] for _ in range(H)]

ans = 0
for hh in range(H):
    for ww in range(W):
        if maze_array[hh][ww] == "#":
            continue
        flag = [[0 for _ in range(W)] for _ in range(H)]
        queue = deque()
        queue.append((hh,ww,0))
        flag[hh][ww] = 1
        while len(queue):
            h, w, p = queue.popleft()
            # print(h,w,p)
            if w != W - 1 and flag[h][w+1] == 0 and maze_array[h][w+1] == ".":
                flag[h][w+1] = 1
                ans = max(ans,p+1)
                queue.append((h,w+1,p+1))
            if h != H - 1 and flag[h+1][w] == 0 and maze_array[h+1][w] == ".":
                flag[h+1][w] = 1
                ans = max(ans,p+1)
                queue.append((h+1,w,p+1))
            if w != 0 and flag[h][w-1] == 0 and maze_array[h][w-1] == ".":
                flag[h][w-1] = 1
                ans = max(ans,p+1)
                queue.append((h,w-1,p+1))  
            if h != 0 and flag[h-1][w] == 0 and maze_array[h-1][w] == ".":
                flag[h-1][w] = 1
                ans = max(ans,p+1)
                queue.append((h-1,w,p+1))
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
cost_list = [[0]*W for i in range(H)]
cost_check = [[0]*W for i in range(H)]
path_list = [] # path content
max_cost = 0 # max path cost

def path_cost(x, y):
    if path_list[x][y]=="#":
        return -1
    # cost check clear
    for i in range(H):
        for j in range(W):
            cost_check[i][j] = 0
            cost_list[i][j] = 0
    # cost calculation
    path_queue = [[x,y]]
    cost_check[x][y] = 1
    # path cost process
    while len(path_queue)>0:
        # path queue pop
        path = path_queue.pop(0)
        next_x, next_y = path[0], path[1]
        # right cost process
        if next_x+1<H:
            if path_list[next_x+1][next_y]=="." and cost_check[next_x+1][next_y]==0:
                cost_list[next_x+1][next_y] = max(cost_list[next_x+1][next_y], cost_list[next_x][next_y]+1)
                path_queue.append([next_x+1, next_y])
                cost_check[next_x+1][next_y] = 1

        # bottom cost process
        if next_y+1<W:
            if path_list[next_x][next_y+1]=="." and cost_check[next_x][next_y+1]==0:
                cost_list[next_x][next_y+1] = max(cost_list[next_x][next_y+1], cost_list[next_x][next_y]+1)
                path_queue.append([next_x, next_y+1])
                cost_check[next_x][next_y+1] = 1

        # left cost process
        if next_x-1>=0:
            if path_list[next_x-1][next_y]=="." and cost_check[next_x-1][next_y]==0:
                cost_list[next_x-1][next_y] = max(cost_list[next_x-1][next_y], cost_list[next_x][next_y]+1)
                path_queue.append([next_x-1, next_y])
                cost_check[next_x-1][next_y] = 1

        # up cost process
        if next_y-1>=0:
            if path_list[next_x][next_y-1]=="." and cost_check[next_x][next_y-1]==0:
                cost_list[next_x][next_y-1] = max(cost_list[next_x][next_y-1], cost_list[next_x][next_y]+1)
                path_queue.append([next_x, next_y-1])
                cost_check[next_x][next_y-1] = 1

    tmp_max_cost = max(sum(cost_list,[]))
    return tmp_max_cost

# input path
for i in range(H):
    path_in = input()
    path = []
    for j in range(W):
        path.append(path_in[j])
    path_list.append(path)

# cost calculation
for i in range(H):
    for j in range(W):
        max_cost = max(max_cost,path_cost(i, j))

print(max_cost)