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:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect
import itertools
import heapq


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(H, W, inputs):
    d_map = inputs
    best_step_num = None
    for i in range(H):
        for j in range(W):
            process_map = [[False for _ in range(W)] for _ in range(H)]
            bfs_queue = collections.deque([[i, j, 0]])
            last_step_num = None

            while len(bfs_queue) > 0:
                [y, x, step_num] = bfs_queue.pop()
                if y >= H or x >= W or y < 0 or x < 0 or d_map[y][x] == '#' or process_map[y][x] is True:
                    continue
                process_map[y][x] = True
                last_step_num = step_num

                bfs_queue.appendleft((y+1, x, step_num+1))
                bfs_queue.appendleft((y-1, x, step_num+1))
                bfs_queue.appendleft((y, x+1, step_num+1))
                bfs_queue.appendleft((y, x-1, step_num+1))

            if last_step_num is not None and (best_step_num is None or last_step_num > best_step_num):
                best_step_num = last_step_num
    return best_step_num


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [H, W] = string_to_int(input())
    ret = solve(H, W, inputs(H))
    print(ret)

Submission status: Accepted

Solution code:
from collections import deque
import copy


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


def bfs(maze, start):
    q = deque()
    q.append((start, 0))

    max_depth = 0

    while len(q) > 0:
        p, depth = q.popleft()

        if p[0] < 0 or H <= p[0]:
            continue
        if p[1] < 0 or W <= p[1]:
            continue
        if maze[p[0]][p[1]] == "#":
            continue

        maze[p[0]][p[1]] = "#"
        max_depth = depth

        next_pos = [
            (p[0]-1, p[1]),
            (p[0]+1, p[1]),
            (p[0], p[1]-1),
            (p[0], p[1]+1),
        ]

        for pos in next_pos:
            q.append((pos, depth+1))

    return max_depth


depth = 0
for h in range(H):
    for w in range(W):
        maze = copy.deepcopy(S)
        depth = max(depth, bfs(maze, (h, w)))

print(depth)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(loc):
    global tem_ans
    d = [[float('inf')] * w for i in range(h)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque([])
    que.append(loc)
    d[loc[0]][loc[1]] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.append([nx,ny])
                if tem_ans < d[nx][ny]:
                    tem_ans = d[nx][ny]
    return tem_ans

h,w = map(int,input().split())

maze = [list(input()) for i in range(h)]


ans = 0
tem_ans = 0

loc = []
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            loc = [i,j]
        else:
            continue
        ans = max(ans,bfs(loc))

print(ans)

Submission status: Accepted

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



H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
que = deque()
ans  = -1
for sx in range(W):
    for sy in range(H): # スタート地点のループ
        if C[sy][sx] == "#":
            continue
        
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        
        que.append((sy,sx))
        dist[sy][sx] = 0
        while que:
            y,x = que.popleft()
            for temp in go:
                gx,gy = temp
                nx = x + gx
                ny = y + gy
                if 0<= nx < W and 0<= ny < H and C[ny][nx] != "#":
                    if dist[ny][nx] == -1: # ここの更新にminはいらない(幅優先なので自明に最短距離を進む)
                        dist[ny][nx] = dist[y][x] + 1
                        que.append( (ny,nx))
        for temp in dist:
            cand = max(temp)
            ans = max(ans,cand)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = list(map(int, input().split()))
maze = [ input() for _ in range(h)]

def bfs(que):
  d = 0
  while que:
    y,x = que.popleft()
    d = dist[y][x]
    for dy, dx in ((0,1),(1,0),(0,-1),(-1, 0)):
      next_y = y + dy
      next_x = x + dx
      if(0 <= next_y and next_y < h and 0 <= next_x and next_x < w and maze[next_y][next_x] != "#" and dist[next_y][next_x] == -1):
        que.append((next_y,next_x))
        dist[next_y][next_x] = d + 1
  return d

ans = -1
for i in range(h):
  for j in range(w):
    que = deque()
    dist = [ [-1]*w for _ in range(h) ]
    if(maze[i][j] != "#"):
      dist[i][j] = 0
      que.append((i, j))
      ans = max([ans, bfs(que)])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
INF = 1001001001
di = [-1, 0, 1, 0]
dj = [ 0,-1, 0, 1]
H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = 0
for si in range(H):
    for sj in range(W):
        if S[si][sj] == '#': continue
        q = deque([(si, sj)])
        dist = [[INF] * W for _ in range(H)]
        dist[si][sj] = 0
        while q:
            i, j = q.popleft()
            for d in range(4):
                ni = i + di[d]
                nj = j + dj[d]
                if (ni<0 or ni>=H or nj<0 or nj>=W): continue
                if S[ni][nj] == '#': continue
                if dist[ni][nj] != INF: continue
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1
        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    ans = max(ans, dist[i][j])
print(ans)

Submission status: Accepted

Solution code:
## atcoder problem 4 ever
dr = [0, -1, 0, 1]
dc = [1, 0, -1, 0]

def get_child(M, i, j, h, w, vis):
    child = []
    for k in range(4):
        x = i + dr[k]
        y = j + dc[k]
        if 0<= x< h and 0 <= y < w and (x, y) not in vis and M[x][y]!='#':
            child.append((x, y))

    return child

def bfs(M, i, j, h, w):
    vis = {(i, j): True}
    li = [(i, j, 0)]
    mx = 0
    while li:
        tp = li.pop(0)
        mx = max(mx, tp[2])
        ch = get_child(M, tp[0], tp[1], h, w, vis)
        vis.update( {}.fromkeys(ch, True) )
        
        ch = [(t[0], t[1], tp[2]+1) for t in ch]
        li.extend(ch)

    return mx
        
        
def solve(M, h, w):
    ans = 0
    for r in range(h):
        for c in range(w):
            if M[r][c]=='.':
                ## start bfs from this point
                depth = bfs(M, r, c, h, w)
                ans = max(ans, depth)
    print(ans)
h, w = map(int, input().split())
Mat = []
for row in range(h):
    Mat.append(input())


solve(Mat, h, w)

Submission status: Accepted

Solution code:
# 再帰の制限を上げる
import sys
sys.setrecursionlimit(10**8)

import itertools
import queue

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

# (x,y)がエリア内である
def check(x,y):
    return not(x<0 or x>H-1 or y<0 or y>W-1 or S[x][y] == "#")

# 到達可能な場所を，距離を記録しながら幅優先探索で埋め尽くす
def bfs(start):
    # 各ノードへの距離 (-1: 未訪問or到達不可)
    dists = [[-1 for _ in range(W)] for _ in range(H)]

    # startが範囲外なら終了
    if not check(*start): return dists
    
    q = queue.Queue()    
    # start位置をput
    q.put(start)
    dists[start[0]][start[1]] = 0
    
    # キューからデータがなくなるまで取り出しを行う
    while not q.empty():
        here = q.get()
        x = here[0]
        y = here[1]

        # この場所の距離
        dist = dists[x][y]
        
        # x,yがエリア内なら
        if check(*here):
            # 訪問済みでない隣接するノードをキューに追加
            for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                # エリア内かつ未訪問
                if check(x+dx,y+dy) and dists[x+dx][y+dy] == -1:
                    q.put((x+dx,y+dy))
                    dists[x+dx][y+dy] = dist + 1

    return dists

ans = []
for start in itertools.product(range(H),range(W)):

    dists = bfs(start)
    ans.append(max([max(_) for _ in dists]))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque()
dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
max = 0
for i in range(h):
    for j in range(w):
        dist = [[-1 for m in range(w)] for n in range(h)]
        dist[i][j] = 0
        if s[i][j] == "#":
            continue
        
        q.append((i, j))
        while q:
            sh, sw = q.popleft()
            for k in range(4):
                ah = sh + dh[k]
                aw = sw + dw[k]
                
                if 0<=ah<h and 0<=aw<w:
                    if s[ah][aw] == "#":
                        continue

                    if dist[ah][aw] == -1:
                        q.append((ah, aw))
                        dist[ah][aw] = dist[sh][sw] + 1

                        if dist[ah][aw] > max:
                            max = dist[ah][aw]

print(max)

Submission status: Accepted

Solution code:
from  queue import Queue
r,c  = map(int,input().split() )

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

meiro = []
for i in range(r):
    meiro.append(list(input()) ) 


def kyori(x, y):
    global r
    global c
    global meiro
    global dx
    global dy
    global INF

    if (meiro[y][x] =="#"):
        return 0

    k = [[INF for j in range (r) ] for i in range(c)]
    #初期化
    q = Queue()
    # 初期位置を保存
    q.put( (x,y) )

    k[x][y] = 0
    
    mk = 0
    while True:
        if q.empty():
            break

        p = q.get()
        for i in range(4):
            nx = dx[i] + p[0]
            ny = dy[i] + p[1]
            # 次に移動できるかどうかの判定
            if (nx < 0 or nx >= c  or
                ny < 0 or ny >= r   ):
                
                continue
            if (k[nx][ny] != INF or 
                meiro[ny][nx] == "#"):
                
                continue
            q.put((nx, ny))
            k[nx][ny] = k[p[0]][p[1]] + 1
            mk = k[nx][ny]
            
            
    return mk

mkList = []
for y in range(r):
    for x in range(c):
        mkList.append(kyori(x, y))
        

print(max(mkList))

Submission status: Accepted

Solution code:
from collections import deque
def bfs(loc):
  global ans
  d=[[float('inf')]*w for i in range(h)]
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  que=deque([])
  que.append(loc)
  d[loc[0]][loc[1]]=0
  while que:
    p=que.popleft()
    for i in range(4):
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and d[nx][ny]==float('inf'):
        d[nx][ny]=d[p[0]][p[1]]+1
        que.append([nx,ny])
        if ans<d[nx][ny]:ans=d[nx][ny]
  return ans

h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
a=0
ans=0
loc=[]
for i in range(h):
  for j in range(w):
    if maze[i][j]!='#':
      loc=[i,j]
    else:continue
    a=max(a,bfs(loc))
print(a)

Submission status: Accepted

Solution code:
#151-D:BFS
from collections import deque
#スタート地点loc=(sx,sy)を決めたときのゴールをbfsで求める
def bfs(loc):
    global tem_ans
    d=[[float('inf')]*w for i in range(h)]

    #進む方向を決める
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

    que=deque([])
    que.append(loc)
    d[loc[0]][loc[1]]=0

    #遷移していってこれ以上遷移できない状態まで埋める
    while que:
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            #遷移可能かどうか調べる
            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and d[nx][ny]==float('inf'):
                #移動後の距離を保存
                d[nx][ny]=d[p[0]][p[1]]+1
                que.append([nx,ny])

                if tem_ans<d[nx][ny]:
                    tem_ans=d[nx][ny]
    return tem_ans



h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
ans=0
tem_ans=0

loc=[]
for i in range(h):
    for j in range(w):
        #通路をスタート地点に設定する
        if maze[i][j]!='#':
            loc=[i,j]
        else:
            continue
        ans=max(ans,bfs(loc))

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
HW = str(input()).split()
H = int(HW[0])
W = int(HW[1])
S = [[0 for i in range(W)] for j in range(H)]
# SS = [[INF]*(W*H)]*(W*H)
mlength = 0


for i in range(H):
  temp = str(input())
  for j in range(W):
    S[i][j]=temp[j]


for i in range(H):
  for j in range(W):
    if(S[i][j] != "#"):
      TS = copy.deepcopy(S)
      mlength = max(mlength, bfs(TS, i, j, H, W))

print(mlength);

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

h,w = map(int,input().split())
geo = np.zeros((h,w),dtype=np.bool)
for i in range(h):
    geo[i] = [x=='.' for x in input()]
geo_i = np.ones((h,w),dtype=np.int) * -1 - (~geo)
    
res = 0

def one_step(igeo,deq,pos,h,w):
    n = igeo[pos]
    for gp in [(0,1),(0,-1),(1,0),(-1,0)]:
        cpos = pos[0]+gp[0], pos[1]+gp[1]
        if h>cpos[0]>=0 and w>cpos[1]>=0:
            if igeo[cpos] == -1:
                igeo[cpos] = n+1
                deq.append(cpos)
    return

for ih in range(h):
    for iw in range(w):
        if geo[ih,iw]:
            igeo = geo_i.copy()
            igeo[ih,iw] = 0
            deq = deque()
            deq.append((ih,iw))
            while len(deq)>0:
                pos = deq.popleft()
                one_step(igeo,deq,pos,h,w)
            res = max(res, igeo.max())
print(res)

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(sx, sy):
    ds = [[1,0], [-1,0], [0,1], [0,-1]]
    distance = [[-1 for _ in range(h)] for _ in range(w)]
    q = deque([[sx, sy]])
    distance[sx][sy] = 0

    while q:
        x, y = q.popleft()
        #print('-----', x, y)
        for dx, dy in ds:
            nx, ny = x+dx, y+dy
            if (nx >= 0) and (nx <= w-1) and (ny >= 0) and (ny <= h-1):
                #print(nx, ny)
                if maze[ny][nx] != '#' and distance[nx][ny] == -1:
                    q.append([nx, ny])
                    distance[nx][ny] = distance[x][y] + 1
    return max(map(max, distance))

count = 0
for s_x in range(w):
    for s_y in range(h):
        if maze[s_y][s_x] == '.':
            count = max(count, bfs(s_x, s_y))

print(count)

Submission status: Accepted

Solution code:
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.state = 0
        self.cost = -1

    def __str__(self):
        return str(self.cost)

    def __repr__(self):
        return str(self.cost)


def show(points):
    for row in points:
        print(*row)


def maxp(points):
    mp = 0
    for row in points:
        for cell in row:
            mp = max(cell.cost, mp)
    return mp


h, w = map(int, input().split())
s = ["#" * (w + 2)] + ["#" + input() + "#" for _ in range(h)] + ["#" * (w + 2)]
ans = 0


for sy in range(h):
    for sx in range(w):
        p = [[Point(x, y) for x in range(w)] for y in range(h)]
        next_search = [(sx, sy)]
        p[sy][sx].cost = 0
        while next_search:
            x, y = next_search.pop(0)
            t = p[y][x]
            if t.state == -1:
                continue
            t.state = -1
            if s[y + 1][x + 1] == "#":
                continue
            if s[y + 1][x] == ".":
                u = p[y][x - 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x - 1, y))
            if s[y + 1][x + 2] == ".":
                u = p[y][x + 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x + 1, y))
            if s[y][x + 1] == ".":
                u = p[y - 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y - 1))
            if s[y + 2][x + 1] == ".":
                u = p[y + 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y + 1))
        ans = max(maxp(p), ans)
print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque


def shori(d, r, max_distance):
    si, sj = d.popleft()
    next_kouho = [
        {'x': si + 1, 'y': sj},
        {'x': si - 1, 'y': sj},
        {'x': si, 'y': sj + 1},
        {'x': si, 'y': sj - 1}
    ]
    for nk in next_kouho:
        if (0 <= nk['x'] < h) and (0 <= nk['y'] < w) and (r[nk['x']][nk['y']] == '.'):
            r[nk['x']][nk['y']] = r[si][sj] + 1
            if max_distance < r[si][sj] + 1:
                max_distance = r[si][sj] + 1
            d.append((nk['x'], nk['y']))
    return d, r, max_distance


if __name__ == '__main__':
    h, w = list(map(int, input().split(" ")))
    s = []
    r = []
    for i in range(h):
        s.append(list(input()))

    d = deque()
    max_distance = 0
    # start 総当り
    for si in range(h):
        for sj in range(w):
            r = copy.deepcopy(s)
            if r[si][sj] == '.':
                r[si][sj] = 0
                d.append((si, sj))

                while True:
                    if len(d) == 0:
                        break
                    else:
                        d, r, max_distance = shori(d, r, max_distance)

    print(max_distance)

Submission status: Accepted

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

delta = [(-1, 0), (1, 0), (0, 1), (0, -1)]


def bfs(i, j):
    if s[i][j] == '#':
        return -1
    q = deque([(i, j)])
    visited = [[-1 for _ in range(w)] for __ in range(h)]
    visited[i][j] = 0
    while q:
        v = q.popleft()
        for d in delta:
            vd1, vd2 = v[0]+d[0], v[1]+d[1]
            if 0 <= vd1 < h and 0 <= vd2 < w:
                if s[vd1][vd2] != '#' and visited[vd1][vd2] == -1:
                    visited[vd1][vd2] = visited[v[0]][v[1]] + 1
                    q.append((vd1, vd2))
    return max(map(max, visited))


ans = 0

for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))

print(ans)

Submission status: Accepted

Solution code:
dr = [0, -1, 0, 1]
dc = [1, 0, -1, 0]

def get_child(M, i, j, h, w, vis):
    child = []
    for k in range(4):
        x = i + dr[k]
        y = j + dc[k]
        if 0<= x< h and 0 <= y < w and (x, y) not in vis and M[x][y]!='#':
            child.append((x, y))

    return child

def bfs(M, i, j, h, w):
    vis = {(i, j): True}
    li = [(i, j, 0)]
    mx = 0
    while li:
        tp = li.pop(0)
        mx = max(mx, tp[2])
        ch = get_child(M, tp[0], tp[1], h, w, vis)
        vis.update( {}.fromkeys(ch, True) )
        
        ch = [(t[0], t[1], tp[2]+1) for t in ch]
        li.extend(ch)

    return mx
        
        
def solve(M, h, w):
    ans = 0
    for r in range(h):
        for c in range(w):
            if M[r][c]=='.':
                ## start bfs from this point
                depth = bfs(M, r, c, h, w)
                ans = max(ans, depth)
    print(ans)
h, w = map(int, input().split())
Mat = []
for row in range(h):
    Mat.append(input())


solve(Mat, h, w)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[str(input()) for _ in range(h)]#行→列の順
dist=[[-1]*w for _ in range(h)]
ans=[]
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([(j,i)])
            while len(que):
                x,y=que.popleft()
                for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nx,ny=x+dx,y+dy
                    if min(nx,ny)>=0 and nx<=w-1 and ny<=h-1:
                        if maze[ny][nx]=='.' and dist[ny][nx]<0:
                            dist[ny][nx]=dist[y][x]+1
                            que.append([nx,ny])
        m=0
        for k in range(h):
          for l in range(w):
            m=max(m,dist[k][l])
        ans.append(m)
print(max(ans))

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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

maze = []
for h in range(H):
  s = input()
  maze.append(s)

def BFS(i,j):
  place = np.zeros((H,W))
  dist = 0
  queue = deque()
  queue.append((i,j,0))
  while queue:
    i,j,d = queue.popleft()
    if not place[i][j]:
      dist = max(dist,d)
      place[i][j] = 1
      for di,dj in [(1,0),(-1,0),(0,1),(0,-1)]:
        if (0 <= i+di and i+di < H and 0 <= j+dj and j+dj < W):
          if maze[i+di][j+dj] == '.' and place[i+di][j+dj] == 0:
            queue.append((i+di,j+dj,d+1))
  return dist

ans = 0
for h in range(H):
  for w in range(W):
    if maze[h][w] == '.':
      ans = max(ans,BFS(h,w))

print(ans)

Submission status: Accepted

Solution code:
h,w =map(int, input().split())
a =['#'*(w+2)] + ['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans=0
for ii in range(h):
    for jj in range(w):
        if a[ii+1][jj+1]=='#':
            continue
        count=1
        n=[(ii+1,jj+1)]
        route={n[0]:0}
        p=[[1,0],[0,1],[-1,0],[0,-1]]
        while count != 1000:
            route2 = route.copy()
            n2=[]
            for i in n:
                for j in p:
                    np=(i[0]+j[0],i[1]+j[1])
                    if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                        n2.append(np)
                        route[np]=count
            n=n2
            count+=1
            if route == route2:
                break
        ans=max(ans,max(route.values()))
        #print(ans, route)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import numpy as np
from collections import deque

H, W = map(int, input().split())
maze = []
for h in range(H):
    ls = input()
    maze.append(ls)


def bfs(x,y):
    visited = np.zeros((H,W))
    dist = 0
    queue = deque()
    queue.append((x,y,0))
    while(queue):
        x,y,d = queue.popleft()
        if not visited[x][y]:
            dist = max(dist, d)
            visited[x][y] = 1
            for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                if (0 <= x+dx and x+dx < H and 0 <= y+dy and y+dy < W):
                    if maze[x+dx][y+dy] == '.' and visited[x+dx][y+dy] == 0:
                        queue.append((x+dx, y+dy, d+1))
    return dist

ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w]==".":
            ans = max(ans, bfs(h,w))

print (ans)

Submission status: Accepted

Solution code:
# ABC151 D
def solve_maze(sx, sy, maze):
    distance = [[None for _ in range(w)] for _ in range(h)]
    queue = [(sx, sy)]
    distance[sy][sx] = 0
    max_distance = 0

    while queue:
        x, y = queue.pop()

        for i in range(4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            try:
                if (0 <= nx <= w and 0 <= ny <= h and maze[ny][nx] == "." and distance[ny][nx] is None):
                    queue.insert(0, (nx, ny))
                    dis = distance[y][x] + 1
                    distance[ny][nx] = dis
                    max_distance = max(max_distance, dis)
            except IndexError:
                pass

    return max_distance
    

h, w = list(map(int, input().split())) # h, w = y, x
maze = [input() for _ in range(h)]

result = 0
for j in range(h):
    for k in range(w):
        if maze[j][k] == ".":
            result = max(result, solve_maze(k, j, maze))

print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
iH, iW = map(int, input().split())
naAll = np.zeros((iH+2, iW+2), dtype=int) - 1
#0123:udlr
iID0 = 0
for iH0 in range(iH):
  s = input()
  for i, s0 in enumerate(s):
    if s0 == ".":
      naAll[iH0+1, i+1] = iID0
      iID0 += 1
lMaze = [[] for _ in range(iID0)]
#lPoss = []
for iH0 in range(iH):
  for iW0 in range(iW):
    if naAll[iH0+1, iW0+1] >= 0:
      iID = naAll[iH0 + 1, iW0 + 1]
      if naAll[iH0 + 2, iW0 + 1] >= 0:
        lMaze[iID].append(naAll[iH0 + 2, iW0 + 1])
      if naAll[iH0 + 1, iW0 + 2] >= 0:
        lMaze[iID].append(naAll[iH0 + 1, iW0 + 2])
      if naAll[iH0    , iW0 + 1] >= 0:
        lMaze[iID].append(naAll[iH0    , iW0 + 1])
      if naAll[iH0 + 1, iW0    ] >= 0:
        lMaze[iID].append(naAll[iH0 + 1, iW0    ])
      #if not( (naAll[iH0 + 2, iW0 + 1] >= 0 and \
      #         naAll[iH0    , iW0 + 1] >= 0) or
      #        (naAll[iH0 + 1, iW0 + 2] >= 0 and \
      #         naAll[iH0 + 1, iW0    ] >= 0) ):
      #  lPoss.append(iID)
      #print(iID, lMaze)
lMax = []
for iID in range(iID0):
  lState = [0]*iID0
  lState[iID] = 1
  lMazeNow = [lMaze[iID]]
  iPre        = 1
  iTime       = 0
  while iPre < iID0:
    lMazeNow0 = []
    for lMazeNext in lMazeNow :
      for iIDnext in lMazeNext:
        if lState[iIDnext] == 0:
          lState[iIDnext] = 1
          iPre += 1
          lMazeNow0.append(lMaze[iIDnext])
    lMazeNow = lMazeNow0
    iTime += 1
    #print(iID, iTime, lState)
  lMax.append(iTime)
print(max(lMax))
#print(lMaze)
#print(naAll)

Submission status: Accepted

Solution code:
from collections import deque

d=[(1,0),(0,1),(-1,0),(0,-1)]
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
def BFS(i,j):
    q = deque()
    dist = [[-1]*W for _ in range(H)]
    if M[i][j] == '.':

        #前処理
        Ma = 0
        q.append((i, j))#スタート地点挿入
        dist[i][j] = 0
        while q:
            cx,cy = q.popleft()
            for nx,ny in d:
                x ,y= cx+nx,cy+ny
                if 0<= x < H and 0<= y < W and M[x][y] == "." and dist[x][y]==-1:
                    dist[x][y]=dist[cx][cy]+1
                    Ma = max(Ma,dist[x][y])
                    q.append((x,y))
        return Ma
    return 0
for i in range(H):#全部の地点でBFSをためす
    for j in range(W):
        Max_list.append(BFS(i,j))

print(max(Max_list))

Submission status: Accepted

Solution code:
from collections import deque
''' 
INF = float('inf')
MOD = 10 ** 9 + 7
'''
## ここは１つにまとめれる
# dy = (0, -1, 0, 1)
# dx = (1, 0, -1, 0)
d=[(1,0),(0,1),(-1,0),(0,-1)]

    
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in d:
                    x ,y= cx+nx,cy+ny
                    ''' ここの処理がをnotにしてわかりやすく
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    '''
                    '''
                    if 0<= x < H and 0<= y < W and dist[x][y]<=0:
                    '''
                    if 0<= x < H and 0<= y < W and M[x][y] == "." and dist[x][y]==-1:
                        dist[x][y]=dist[cx][cy]+1
                        Ma = max(Ma,dist[x][y])
                        q.append((x,y))
            Max_list.append(Ma)

print(max(Max_list))

Submission status: Accepted

Solution code:
from collections import deque
''' 
INF = float('inf')
MOD = 10 ** 9 + 7
'''
## ここは１つにまとめれる
# dy = (0, -1, 0, 1)
# dx = (1, 0, -1, 0)
d=[(1,0),(0,1),(-1,0),(0,-1)]

    
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in d:
                    x ,y= cx+nx,cy+ny
                    ''' ここの処理がをnotにしてわかりやすく
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    '''
                    if 0<= x < H and 0<= y < W:

                        if M[x][y] == "." and dist[x][y] == -1:
                            dist[x][y]=dist[cx][cy]+1
                            Ma = max(Ma,dist[x][y])
                            q.append((x,y))
            Max_list.append(Ma)

print(max(Max_list))