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
H, W = map(int, input().split())
g = [list(input()) for i in range(H)]
direction = [[0,1],[1,0],[0,-1],[-1,0]]
ans=0
for sh in range(H):
    for sw in range(W):
        #スタート地点が壁ならスキップ
        if g[sh][sw]=="#":
            continue
        dist=[[-1]*W for i in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh,sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in direction:
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
                if g[nh+dh][nw+dw]=="#":
                    continue
                if dist[nh+dh][nw+dw]!=-1:
                    continue
                
                #dist[nh+dw][nw+dw] = dist[nh][nw]+1
                #que.appendleft([nh + dh,nw+dw])
                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                que.appendleft([nh + dh, nw + dw])
        ans = max (ans, max([max(d) for d in dist]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')



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

def bfs(sy, sx):
  dist = [[0 for x in range(w)] for y in range(h)]
  dy = [0, 1, 0, -1]
  dx = [1, 0, -1, 0]
  Q = deque()
  Q.append((sy, sx))
  while Q:
    q = Q.popleft()
    y = q[0]
    x = q[1]
    d = dist[y][x]
    for i in range(4):
      ny = y + dy[i]
      nx = x + dx[i]
      if ny < 0 or h <= ny or nx < 0 or w <= nx:
        continue
      #迷路における道が'.'、壁が'#'で表されている場合
      if ny == sy and nx == sx:
        continue
      if maze[ny][nx] == '#':
        continue
      nd = d + 1
      if dist[ny][nx] != 0 and nd >= dist[ny][nx]:
        continue
      dist[ny][nx] = nd
      Q.append((ny, nx))
  return max(max(x) for x in dist)

ans = 0
for y in range(h):
  for x in range(w):
    if maze[y][x] == '.':
      ans = max(ans, bfs(y,x))
print(ans)

Submission status: Accepted

Solution code:
import queue
from itertools import product

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

ans=-1

def bfs(start):
    distance=[[-1]*H for j in range(W)]
    li_x=[1,-1,0,0]
    li_y=[0,0,1,-1]
    q = queue.Queue()
    q.put(start)
    distance[start[0]][start[1]]=0

    while not q.empty():
        hoge=q.get()
        x=hoge[0]
        y=hoge[1]
        dis=distance[x][y]

        for i in range(4):
            x1=x+li_x[i]
            y1=y+li_y[i]
            if (0 <=x1 < W and 0 <= y1 < H):
                if distance[x1][y1] == -1:
                    if S[y1][x1]=='.':
                        q.put([x1,y1])
                        distance[x1][y1]=dis+1
    m=[]
    for i in range(W):
        m.extend(distance[i])
    return max(m)

for sx,sy in product(range(W),range(H)):

                if S[sy][sx]=='.':
                    re=bfs([sx,sy])
                    if re > ans:
                        ans=re

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
import math
import io

    
H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
    grid += '#' + input() + '#'
grid += '#' * (W+2)
move = [1, -1, W+2, -W-2]
    
def bfs(start):
    lst = [10**9] *((H+2)*(W+2))
    lst[start] = 0
    q = deque([start])
    while q:
        x = q.popleft()
        dx = lst[x]
        for d in move:
            y = x + d
            if grid[y] == '#':
                continue
            dy = dx + 1
            if dy >= lst[y]:
                continue
            lst[y] = dy
            q.append(y)
    return max(x for x in lst if x < 10**9)
    
    
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '#'))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
maze = nsn(h)

def bfs(sx, sy):
    q = deque()
    q.append((sx, sy))
    dist = [[inf] * w for _ in range(h)]
    dist[sy][sx] = 0
    dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
    res = 0
    while len(q):
        p = q.popleft()
        cx, cy = p
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if nx < 0 or nx >= w:
                continue
            if ny < 0 or ny >= h:
                continue
            if dist[ny][nx] != inf:
                continue
            if maze[ny][nx] == '#':
                continue
            update = dist[cy][cx] + 1
            dist[ny][nx] = update
            res = max(res, update)
            q.append((nx, ny))
    
    return res

def main():
    ans = 0

    for y in range(h):
        for x in range(w):
            if maze[y][x] == '#':
                continue
            ans = max(ans, bfs(x, y))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

h, w = na()
maze = nsn(h)

def bfs(sx, sy):
    q = deque()
    q.append((sx, sy))
    dist = [[inf] * w for _ in range(h)]
    dist[sy][sx] = 0
    dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
    res = 0
    while len(q):
        p = q.popleft()
        cx, cy = p
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if nx < 0 or nx >= w:
                continue
            if ny < 0 or ny >= h:
                continue
            if dist[ny][nx] != inf:
                continue
            if maze[ny][nx] == '#':
                continue
            update = dist[cy][cx] + 1
            dist[ny][nx] = update
            res = max(res, update)
            q.append((nx, ny))
    
    return res

ans = 0

for y in range(h):
    for x in range(w):
        if maze[y][x] == '#':
            continue
        ans = max(ans, bfs(x, y))

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val
        
h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    x, y, _ = root
    grid[y, x] = 0
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy, d+1))
                grid[y+dy, x+dx] = 0
    return d
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i, 0)))
print(ans)

Submission status: Accepted

Solution code:
def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
#             if x == gx and y == gy:
#                 # ゴール座標と一致するなら
#                 break
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x] + 1
                    # （追記）距離の最大値を更新する
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist_max
#         return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

R , C = [int(i) for i in input().split()]
c = [input() for _ in range(R)]

# スタート地点は全て試す
dist_ans = 0
for sy in range(1, R+1):
    for sx in range(1, C+1):
        if c[sy-1][sx-1] != '#':
            dist_tmp = C_BFS(R, C, sy, sx, 1, 1, c) # 今回、 gy, gx は不要
            if dist_ans < dist_tmp:
                dist_ans = dist_tmp
print(dist_ans)

Submission status: Accepted

Solution code:
#BFS
from collections import deque
def bfs(i,j):
    q=deque()
    q.append((i,j))
    log=[[-1]*w for i in range(h)]
    log[i][j]=0
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    long=0
    while q:
        #qの先頭を取り出す
        p=q.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            if not(0<=nx<h and 0<=ny<w):continue
            if maze[nx][ny]=='#':continue
            if log[nx][ny]!=-1:continue
            log[nx][ny]=log[p[0]][p[1]]+1
            q.append((nx,ny))
            if long<=log[nx][ny]:long=log[nx][ny]
    return long

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

ans=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            temp=bfs(i,j)
            if ans<temp:ans=temp
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
S = [["#"] * (W + 2)]
S += [["#"] + list(input()) + ["#"] for _ in range(H)]
S.append(["#"] * (W + 2))

DX = [0,0,-1,1]
DY = [-1,1,0,0]

from collections import deque

def bfs(y,x):
    dist = [[-1] * (W + 2) for _ in range(H + 2)] 
    
    que = deque([(y, x)])
    dist[y][x] = 0
    while que:
        y, x = que.popleft()
        d = dist[y][x]
        for dy,dx in zip(DY,DX):
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#": continue
            if dist[ny][nx] < 0:
                dist[ny][nx] = d + 1
                que.append((ny,nx))
    
    ans = -1
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            ans = max(ans, dist[i][j])
    return ans

ans = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i][j] == "#": continue
        ans = max(ans, bfs(i, j))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = list(map(int,input().split()))
inf=float("inf")
s = [[-1]*(w+2)] + [[-1] + [inf if i=="." else -1 for i in input()] + [-1] for _ in range(h)] + [[-1]*(w+2)]

from copy import deepcopy
from collections import deque

ret = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        temp_s = deepcopy(s)
        if temp_s[i][j]!=-1:
            temp_s[i][j]=-1
            stack_deque = deque([(i,j,0)])
        else:
            stack_deque = []
        max_v=0
        while len(stack_deque)>0:
            hi,wj,v = stack_deque.popleft()
            v+=1
            if temp_s[hi][wj-1]!=-1:
                temp_s[hi][wj-1]=-1
                stack_deque.append([hi,wj-1,v])
                max_v=max(max_v,v)
            if temp_s[hi][wj+1]!=-1:
                temp_s[hi][wj+1]=-1
                stack_deque.append([hi,wj+1,v])
                max_v=max(max_v,v)
            if temp_s[hi-1][wj]!=-1:
                temp_s[hi-1][wj]=-1
                stack_deque.append([hi-1,wj,v])
                max_v=max(max_v,v)
            if temp_s[hi+1][wj]!=-1:
                temp_s[hi+1][wj]=-1
                stack_deque.append([hi+1,wj,v])
                max_v=max(max_v,v)
        ret=max(ret,max_v)
print(ret)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy


def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    ans = 0
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                continue
            now_grid = deepcopy(grid)
            answer = [[float("inf") for _ in range(w)] for _ in range(h)]
            next = deque([[i, j]])
            answer[i][j] = 0
            while next:
                y, x = next.popleft()
                if now_grid[y][x] == ".":
                    now_grid[y][x] = "#"
                    for dx, dy in d:
                        if 0 <= x + dx < w and 0 <= y + dy < h and now_grid[y + dy][x + dx] == ".":
                            answer[y + dy][x + dx] = min(answer[y][x] + 1, answer[y + dy][x + dx])
                            next.append([y + dy, x + dx])
            for k in range(h):
                for l in range(w):
                    if grid[k][l] == "#":
                        continue
                    ans = max(ans, answer[k][l])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(sx, sy, maze):
    INF = 100000000
    visit = [[-INF for i in range(w + 2)] for j in range(h + 2)]
    queue = deque([])
    queue.append([sx, sy])
    visit[sx][sy] = 0
    res = 0
    while len(queue):
        x, y = queue.popleft()
        for k in range(0, 4):
            nx, ny = x + dx[k], y + dy[k]
            if maze[nx][ny] != '#' and visit[nx][ny] == -INF:
                queue.append([nx, ny])
                visit[nx][ny] = visit[x][y] + 1
                res = max(res, visit[nx][ny])
    return res


h, w = map(int, input().split())
maze = [list("#" * (w + 2))]
for _ in range(h):
    maze.append(["#"] + list(input()) + ["#"])
maze += [list("#" * (w + 2))]

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

ans = 0
for i in range(h + 2):
    for j in range(w + 2):
        if maze[i][j] == ".":
            ans = max(ans, bfs(i, j, maze))
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, rows in zip(range(h), grid):
            for j, val in zip(range(w), rows):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, rows)) for rows in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val
h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        d += 1
        grid[y, x] = 0
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy, d))
                grid[y+dy, x+dx] = 0
    return d-1
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i, 0)))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def bfs(sy, sx):
    dist = [[-INF] * W for _ in range(H)]
    dist[sy][sx] = 0
    que = deque([(sy, sx)])
    popleft = que.popleft; append = que.append
    while que:
        y, x = popleft()
        cur = dist[y][x]
        for dy, dx in zip([0, 1, 0, -1], [1, 0, -1, 0]):            
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '#' and dist[ny][nx] == -INF:
                dist[ny][nx] = cur + 1
                append((ny, nx))
    ret = max(max(x for x in di)for di in dist)
    return ret

INF = 10 ** 3
H, W = lr()
grid = [sr() for _ in range(H)]
answer = max(max(bfs(i, j) if grid[i][j] == '.' else 0 for j in range(W)) for i in range(H))
print(answer)
#

Submission status: Accepted

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

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue

        # h,w
        record = [[[h, w]]]
        count = 0
        while True:
            if record[count] == []:
                break
            li = []
            for p in record[count]:
                h = p[0]
                w = p[1]
                next_to_p = []
                if h > 0 and S[h - 1][w] == "." and [h - 1, w] not in record[count - 1] + li:
                    next_to_p.append([h - 1, w])
                if w > 0 and S[h][w - 1] == "." and [h, w - 1] not in record[count - 1] + li:
                    next_to_p.append([h, w - 1])
                if h < H - 1 and S[h + 1][w] == "." and [h + 1, w] not in record[count - 1] + li:
                    next_to_p.append([h + 1, w])
                if w < W - 1 and S[h][w + 1] == "." and [h, w + 1] not in record[count - 1] + li:
                    next_to_p.append([h, w + 1])
                li = li + next_to_p
            record.append(li)
            count += 1

        ans = max(ans, count - 1)

print(ans)

Submission status: Accepted

Solution code:
# ATC001 A

# recursive function
# x, y からスタートして行けるところを探索する
# r[x, y] = x, y まで来るのにかかったステップ数
def search(x, y, r):
    # right
    if x < H - 1 and S[x + 1][y] == "." and r[x + 1][y] == -1:
        r[x + 1][y] = r[x][y] + 1
        search(x + 1, y, r)
    # down
    if y < W - 1 and S[x][y + 1] == "." and r[x][y + 1] == -1:
        r[x][y + 1] = r[x][y] + 1
        search(x, y + 1, r)
    # left
    if 0 < x and S[x - 1][y] == "." and r[x - 1][y] == -1:
        r[x - 1][y] = r[x][y] + 1
        search(x - 1, y, r)
    # up
    if 0 < y and S[x][y - 1] and r[x][y - 1] == -1:
        r[x][y - 1] = r[x][y] + 1
        search(x, y - 1, r)


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

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue

        # h,w
        record = [[[h, w]]]
        count = 0
        while True:
            if record[count] == []:
                break
            li = []
            for p in record[count]:
                h = p[0]
                w = p[1]
                next_to_p = []
                if h > 0 and S[h - 1][w] == "." and [h - 1, w] not in record[count - 1] + li:
                    next_to_p.append([h - 1, w])
                if w > 0 and S[h][w - 1] == "." and [h, w - 1] not in record[count - 1] + li:
                    next_to_p.append([h, w - 1])
                if h < H - 1 and S[h + 1][w] == "." and [h + 1, w] not in record[count - 1] + li:
                    next_to_p.append([h + 1, w])
                if w < W - 1 and S[h][w + 1] == "." and [h, w + 1] not in record[count - 1] + li:
                    next_to_p.append([h, w + 1])
                li = li + next_to_p
            record.append(li)
            count += 1

        ans = max(ans, count - 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def warshal_floyd(d, n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
        
  return d
 
h, w = map(int, input().split())
m = [str(input()) for _ in range(h)]
d = [[float('inf') for i in range(h*w)] for j in range(h*w)]
for i in range(h*w):
  d[i][i] = 0
  
for i in range(h*w):
  for j in range(h*w):
    py, px = i//w, i%w
    qy, qx = j//w, j%w
    if (px == qx and abs(py-qy) == 1) or (py == qy and abs(px-qx) == 1):
      pm = m[py][px]
      qm = m[qy][qx]
      if qm == '.' and pm == '.':
        d[i][j] = 1
        
#print(d)
d = warshal_floyd(d, h*w)
#print(d)
 
ans = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] != float('inf'):
      ans = max(ans, d[i][j])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
MAZE = ['#'*(w+2)]
for _ in range(h):
    MAZE.append("#"+input()+"#")
else:
    MAZE.append('#'*(w+2))

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dist = [[INF]*(w+2) for _ in range(h+2)]
    q = deque([(init_x, init_y)])
    dist[init_x][init_y] = 0
    MAX = 0
    while q:
        x, y = q.popleft()
        for i, j in directions:
            if MAZE[x+i][y+j] == '#':
                continue
            if dist[x+i][y+j] <= dist[x][y]+1:
                continue
            dist[x+i][y+j] = dist[x][y]+1
            q.append((x+i, y+j))

        MAX = max(MAX, dist[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '#':
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue
h, w = map(int, input().split())
MAZE = ['#'*(w+2)]
for _ in range(h):
    MAZE.append("#"+input()+"#")
else:
    MAZE.append('#'*(w+2))

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dist = [[INF]*(w+2) for _ in range(h+2)]
    q = Queue()
    q.put((init_x, init_y))
    dist[init_x][init_y] = 0
    MAX = 0
    while not q.empty():
        x, y = q.get()
        for i, j in directions:
            if MAZE[x+i][y+j] == '#':
                continue
            if dist[x+i][y+j] <= dist[x][y]+1:
                continue
            dist[x+i][y+j] = dist[x][y]+1
            q.put((x+i, y+j))
        MAX = max(MAX, dist[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '#':
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
# 上下左右どこでもいける
# BFS
from queue import Queue
h, w = map(int, input().split())
MAZE = ['#'*(w+2)]
for _ in range(h):
    MAZE.append("#"+input()+"#")
else:
    MAZE.append('#'*(w+2))

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dp = [[INF]*(w+2) for _ in range(h+2)]
    resisterd = [[0]*(w+2) for _ in range(h+2)]
    q = Queue()
    q.put((init_x, init_y))
    dp[init_x][init_y] = 0
    MAX = 0
    while not q.empty():
        x, y = q.get()
        for i, j in directions:
            if MAZE[x+i][y+j] == '#':
                continue
            if resisterd[x+i][y+j]:
                continue
            resisterd[x+i][y+j] = 1
            q.put((x+i, y+j))
        dp[x][y] = min(dp[x][y], min(dp[x+v][y+w]+1 for v, w in directions))
        MAX = max(MAX, dp[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '#':
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def bfs(sy, sx):
    dist = [[-INF] * W for _ in range(H)]
    dist[sy][sx] = 0
    que = deque([(sy, sx)])
    popleft = que.popleft; append = que.append
    while que:
        y, x = popleft()
        cur = dist[y][x]
        for dy, dx in zip([0, 1, 0, -1], [1, 0, -1, 0]):            
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '#' and dist[ny][nx] == -INF:
                dist[ny][nx] = cur + 1
                append((ny, nx))
    ret = max(max(x for x in di)for di in dist)
    return ret

INF = 10 ** 3
H, W = lr()
grid = [sr() for _ in range(H)]
answer = max(max(bfs(i, j) if grid[i][j] == '.' else 0 for j in range(W)) for i in range(H))
print(answer)
# 22

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
N = ii()
A = li()
right = 0
flag = [0]*(10**5+1)
ans = 0

for left in range(N):
    #flag[A[left]] = 1
    while right < N and flag[A[right]]!=1:
        flag[A[right]] = 1
        right += 1
    #print(left, right)
    ans = max(ans, right-left)
    if left == right:
        right += 1
    else:
        flag[A[left]] = 0

print(ans)
'''

from collections import deque

H, W = mi()
S = [input() for i in range(H)]

d = deque()
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
ans = 0
flag = dp2(0, W, H)

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            flag = dp2(0, W, H)
            d.append([i, j, 0])
            flag[i][j] = 1
            while d!=deque():
                a = d.popleft()
                for k in range(4):
                    x, y = a[0]+dy[k], a[1]+dx[k]
                    if 0 <= x < H and 0 <= y < W:
                        if S[x][y] == '.' and flag[x][y] != 1:
                            d.append([x, y, a[2]+1])
                            flag[x][y] = 1
                            ans = max(ans, a[2]+1)

print(ans)

Submission status: Accepted

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

#from queue import Queue #キューを使ったら1ケースだけTLEになった。
from collections import deque

dj = [1, 0, -1, 0]
di = [0, 1, 0, -1]

sum_sharp = sum([A[i].count('#') for i in range(H)])

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        d_max = 0
        q_i = deque()
        q_j = deque()
        D = [[-1]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            q_i.append(s_i)
            q_j.append(s_j)
            while len(q_i)!=0:
                i = q_i.popleft()
                j = q_j.popleft()
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or D[ni][nj]!=-1:
                        continue
                    else:
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        q_i.append(ni)
                        q_j.append(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)