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
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 len(d)!=0:
                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:
import sys
from collections import deque

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

H, W = lr()
grid = [sr() for _ in range(H)]

def bfs(sy, sx):
    d = [[float('inf')] * W for _ in range(H)]
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    que = deque()
    que.append((sy, sx))
    d[sy][sx] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]                
            if 0 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '#' and d[ny][nx] == float('inf'):
                d[ny][nx] = d[p[0]][p[1]] + 1
                que.append((ny, nx))
    max = 0
    for row in d:
        for r in row:
            if r != float('inf') and r > max:
                max = r
    return max

answer = 0    
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            continue
        result = bfs(i, j)
        if result > answer:
            answer = result

print(answer)
# 49

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(maze,visited,sx,sy):
    stack = deque([[sy,sx]])
    visited[sy][sx] = 0
    while stack:
        y,x = stack.pop()
        count = visited[y][x]
        
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y,new_x = y+j,x+k
            if new_x < 0 or new_x >= W or new_y < 0 or new_y >= H:
                continue
            #深さ優先
            elif maze[new_y][new_x] != "#" and visited[new_y][new_x] > count+1:
                visited[new_y][new_x] = count+1
                stack.appendleft([new_y, new_x])
    return count

inf = float('inf')

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            visited = [[inf]*W for _ in range(H)]
            answer = max(answer,bfs(maze,visited,j,i))
print(answer)

Submission status: Accepted

Solution code:
def gridbfs(grid,sy,sx):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    dist[sy][sx] = 0
    q = [(sy,sx)]
    d = 1

    while q:
        qq = []
        for y,x in q:
            for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                yy,xx = y+dy, x+dx
                if not (0 <= yy < gridy and 0 <= xx < gridx):
                    continue
                if grid[yy][xx] == '#':
                    continue
                if dist[yy][xx] != INF:
                    continue
                dist[yy][xx] = d
                qq.append((yy,xx))
        q = qq
        d += 1

    return dist

h,w = map(int,input().split())
s = [input() for i in range(h)]
c = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d_list = gridbfs(s,i,j)
        for k in range(h):
            for l in range(w):
                if d_list[k][l] != 10**18:
                    c = max(c,d_list[k][l])
print(c)

Submission status: Accepted

Solution code:
#abc151d
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,raw_input().split())
s=[raw_input() for i in range(h)]
n=w*h
e=[[0]*n for i in range(n)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
 for j in range(w):
  if s[i][j]=='.':
   for x,y in d:
    ni,nj=i+x,j+y
    if 0<=ni<h and 0<=nj<w and s[ni][nj]=='.':
     e[w*i+j][w*ni+nj]=1
res=floyd_warshall(e)
INF=float("inf")
print int(max(max(a if a!=INF else 0 for a in a) for a in res))

Submission status: Accepted

Solution code:

h,w=map(int,input().split())
g=[input() for _ in range(h)]
def search(y,x):
  que=[(y,x)]
  vis=[[-1]*w for _ in range(h)]
  vis[y][x]=0
  while que:
    cy,cx=que.pop(0)
    for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
      ny,nx=cy+dy,cx+dx
      if 0<=ny<h and 0<=nx<w and g[ny][nx]=="." and vis[ny][nx]==-1:
        vis[ny][nx]=vis[cy][cx]+1
        que.append((ny,nx))
  return max(max(l) for l in vis)
ans=0
for i in range(h):
  for j in range(w):
    if g[i][j]==".":
      ans=max(search(i,j),ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    import copy
    h,w = map(int, input().split())
    s = [list(input().rstrip()) for _ in range(h)]

    #始点(i,j)から最短で行ける一番遠い距離
    def bfs(i, j):
        dxy = [[0,1],[0,-1],[1,0],[-1,0]]
        q = deque([[i,j]])
        d[i][j] = 0
        while q:
            x, y = q.popleft()
            for dx, dy in dxy:
                nx, ny = x+dx, y+dy
                if 0<=nx<=h-1 and 0<=ny<=w-1:
                    if d[nx][ny]=='.':
                        d[nx][ny] = d[x][y] + 1
                        q.append([nx,ny])
        res = 0
        for a in range(h):
            for b in range(w):
                if d[a][b] != '#':
                    res = max(res, d[a][b])
        return res

    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                d = copy.deepcopy(s)
                res = max(res, bfs(i, j))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    h, w = src
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    que = deque([(h, w, 0)])
    dist = list2d(H, W, -1)
    dist[h][w] = 0
    while que:
        h, w, c = que.popleft()
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if grid[h2][w2] == '#':
                continue
            if dist[h2][w2] != -1:
                continue
            dist[h2][w2] = c + 1
            que.append((h2, w2, c+1))
    return dist

H, W = MAP()
grid = build_grid(H, W, '#', str, space=0, padding=1)

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] != '#':
            # 有効な全マスから最短距離試す
            res = bfs(grid, (i, j))
            for k in range(1, H+1):
                for l in range(1, W+1):
                    # 一番遠い場所
                    ans = max(ans, res[k][l])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

U, D, L, R = (-1, 0), (+1, 0), (0, -1), (0, +1)

is_good = lambda x, y, R, C: True if x < R and x >= 0 and y < C and y >= 0 else False


def traverse(grid, start, distance_grid):
  d = deque([(start, 0)])
  tx, ty = start
  distance_grid[tx][ty] = 0
  #print(distance_grid)
  dis = 0
  visited = set([start])
  while d:
    node, path = d.popleft()
    cx, cy = node
    for dx, dy in U, D, L, R:
      if is_good(cx + dx, cy + dy, len(grid), len(grid[0])) and grid[cx + dx][cy + dy] != '#' and (cx + dx, cy + dy) not in visited:
        nx, ny = cx + dx, cy + dy
        visited.add((nx, ny))
        d.append([(nx, ny), path+1])
        distance_grid[nx][ny] = distance_grid[cx][cy]+1
  #print(distance_grid)
  for arr in distance_grid:
    dis = max(dis, max(arr))
  return dis

from copy import deepcopy

def bfs():
  R, C = tuple(map(int, input().split()))
  grid =[list(input()) for _ in range(R)]
  temp = [[-1 for _ in range(C)] for _ in range(R)]
  #print(grid)
  answer = 0
  for row in range(R):
    for col in range(C):
      if grid[row][col] != '#':
        start = (row, col)
        distance_grid = deepcopy(temp)
        answer = max(answer, traverse(grid, start, distance_grid))
  return answer


print(bfs())

Submission status: Accepted

Solution code:
import copy
from collections import deque


def bfs(H, W, maze, dist, sh, sw):
    queue = deque([[sh, sw]])
    dist[sh][sw] = 0
    while queue:
        h, w = queue.popleft()
        for i, j in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
            next_h, next_w = h + i, w + j
            if not ((0 <= next_h <= H - 1) and (0 <= next_w <= W - 1)):
                continue
            if (maze[next_h][next_w] == ".") and (dist[next_h][next_w] == -1):
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append([next_h, next_w])
    ret = 0
    for i in range(H):
        tmp = max(dist[i])
        if tmp > ret:
            ret = tmp
    return ret


if __name__ == "__main__":
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    dist = [[-1 for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if S[sh][sw] == "#":
                continue
            d = copy.deepcopy(dist)
            max_move = bfs(H, W, S, d, sh, sw)
            if max_move > ans:
                ans = max_move
    print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
sys.setrecursionlimit(10**6)

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

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

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0) ,walker)
    else:
        return None


candicate = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
            far=0

            for gx in range(W):
                for gy in range(H):
                    if S[gy][gx]=='.':
                        if far < temp_walker[gy][gx]:
                            far = temp_walker[gy][gx]

            #print(sx, sy, temp_walker, far)
            candicate.append(far)
print(max(candicate))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
meiro = []
for i in range(h):
    meiro.append(list(input()))
#進む方向のリスト
d = [(1,0) , (-1,0) , (0,1),(0,-1)]
ans = 0

def search(n,m):
    ans = -1  #最後に次の層に行けなくても+1するから-1から
    
    X = [[0 for i in range(w)] for j in range(h)]  #探索判定用配列
    X[n][m] = 1#初期位置を到達済みにする
    que = [(n,m)]#初期位置をキューに追加
    while que:#キューがからでないなら
        new_que = []#深さ+1で到達済みの点を次のqueにする
        for x,y in que:
            for dx,dy in d:
                if 0<= x+dx < h and 0<= y+dy < w and meiro[x+dx][y+dy] == '.' and X[x+dx][y+dy] == 0:
                    X[x+dx][y+dy] = 1
                    new_que.append((x+dx , y+dy))
        ans += 1
        que = new_que
    return ans

for i in range(h):
    for j in range(w):
        if meiro[i][j] == '.':
            ans = max(ans , search(i,j))
            
print(ans)

Submission status: Accepted

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

def cal_dist(sx, sy):
    # スタートからの距離を格納
    x_max, y_max = h, w
    dist = [[float('inf')] * w for _ in range(h)]

    # キューを作成
    que = deque([])
    que.append((sx, sy))
    dist[sx][sy] = 0

    # ゴールにたどり着くまで探索
    dist_max = 0
    while len(que) > 0:
        x, y = que.popleft()

        dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < x_max and 0 <= ny < y_max and \
               s[nx][ny] != '#' and dist[nx][ny] == float('inf'):
                que.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1
                dist_max = max(dist[nx][ny], dist_max)

    return dist_max

dist_max = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        dist = cal_dist(i, j)
        if dist == float('inf'):
            continue
        dist_max = max(dist, dist_max)
print(dist_max)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=[]
for _ in range(H):
    s.append(list(input()))
def dfs(y,x):
    q=[(y,x)]
    visited=[[-1]*W for _ in range(H)]
    visited[y][x]=0
    while q:
        cy,cx=q.pop(0)
        for dy,dx in ((1,0),(-1,0),(0,-1),(0,1)):
            nx=cx+dx
            ny=cy+dy
            if 0<=ny<H and 0<=nx<W and s[ny][nx]=='.' and visited[ny][nx]==-1:
                visited[ny][nx]=visited[cy][cx]+1
                q.append((ny,nx))
    return max(max(i) for i  in visited)
ans=0
for h in range(H):
    for w in range(W):
        if s[h][w]=='.':
            ans=max(dfs(h,w),ans)
print(ans)

Submission status: Accepted

Solution code:
import numpy
H,W = map(int, input().split())
S = [list('#'+input()+"#") for i in range(H)]
S.insert(0, list('#'*(W+2)))
S.append(list('#'*(W+2)))
vector = [(1,0), (-1,0), (0,1), (0,-1)]
ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]=='.':
            Q = [(i,j)]
            distance = [[0]*(W+2) for i in range(H+2)]
            distance[i][j] = 1
            while Q!=[]:
                x,y = Q.pop(0)
                for k in vector:
                    x1,y1 = x+k[0],y+k[1]
                    if S[x1][y1]=='.' and distance[x1][y1]==0:
                        Q.append((x1,y1))
                        distance[x1][y1] = distance[x][y] + 1
            ans = max(ans, numpy.max(distance))
print(ans-1)

Submission status: Accepted

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

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def bfs(g, sh, sw):
    # [[-1, -1, -1], [-1, -1, -1]]
    dist = [[-1] * W for _ in range(H)]
    que = queue.Queue()
    res = 0
    que.put((sh,sw))
    dist[sh][sw] = 0
    while not que.empty():
        sh, sw = que.get()
        res = max(res, dist[sh][sw])
        for i in range(4):
            nh = sh + dx[i]
            nw = sw + dy[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if g[nh][nw] == '#':
                continue
            if dist[nh][nw] == -1:
                dist[nh][nw] = dist[sh][sw] + 1
                que.put((nh, nw))
    return res

ans = 0
for sh in range(H):
    for sw in range(W):
        if g[sh][sw] == '#':
            continue
        ans = max(ans, bfs(g, sh, sw))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
inf=10**6
dx=[-1,0,1,0]
dy=[0,1,0,-1]
h,w=map(int,input().split())
maze=[list(input()) for _ in range(h)]
def bfs(sx,sy):
    dist=[[inf for _ in range(w)] for _ in range(h)]
    dist[sx][sy]=0
    d=deque()
    d.append([sx,sy])
    while d:
        x,y=d.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or nx>=h or ny<0 or ny>=w or maze[nx][ny]=='#' or dist[nx][ny]!=inf:
                continue
            d.append([nx,ny])
            dist[nx][ny]=dist[x][y]+1
    val=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]!=inf:
                val=max(val,dist[i][j])
    return val
ans=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            ans=max(ans,bfs(i,j))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from queue import Queue
H, W = map(int, input().split())
m = [input() for i in range(H)]
G = defaultdict(list)
l = []
for i in range(H):
    for j in range(W):
        v = i*W + j+1
        if m[i][j] != '.':
            continue
        l.append(v)
        if i + 1 < H and m[i+1][j] == '.':
            G[v].append((i+1)*W + j+1)
        if 0 <= i - 1 and m[i-1][j] == '.':
            G[v].append((i-1)*W + j+1)
        if j + 1 < W and m[i][j+1] == '.':
            G[v].append(i*W + j+2)
        if 0 <= j - 1 and m[i][j-1] == '.':
            G[v].append(i*W + j)

def bfs(v):
    visited = defaultdict(bool)
    q = Queue()
    visited[v] = 1
    dist = [-1] * (H*W)
    dist[v-1] = 0
    q.put(v)
    while not q.empty():
        v = q.get()
        for c in G[v]:
            if not c in visited:
                visited[c] = 1
                dist[c-1] = dist[v-1] + 1
                q.put(c)
    return dist

ans = 0
for v in l:
    ans = max(ans, max(bfs(v)))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
H, W = map(int, input().split())
M = []
for i in range(H):
    M.append(list(input()))


def getMaxDistantPoint(Sx, Sy):
    BIG = 10**16

    def bigcost():
        return BIG
    costs = defaultdict(bigcost)
    costs[(Sx, Sy)] = 0
    current = [(Sx, Sy)]
    visited = set()
    while len(current) > 0:
        next = []
        for v in current:
            c = costs[v]
            if v[0] > 0 and M[v[1]][v[0]-1] == ".":
                coord = (v[0]-1, v[1])
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
            if v[0] < W-1 and M[v[1]][v[0]+1] == ".":
                coord = (v[0]+1, v[1])
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
            if v[1] < H-1 and M[v[1]+1][v[0]] == ".":
                coord = (v[0], v[1]+1)
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
            if v[1] > 0 and M[v[1]-1][v[0]] == ".":
                coord = (v[0], v[1]-1)
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
        current = next
    maxCost = 0
    maxCoord = None
    for c in costs:
        if costs[c] != BIG:
            if costs[c] > maxCost:
                maxCoord = c
                maxCost = costs[c]
    return (maxCoord, maxCost)


result = 0
for Sx in range(W):
    for Sy in range(H):
        if M[Sy][Sx] == '.':
            result = max(result, getMaxDistantPoint(Sx, Sy)[1])
print(result)

Submission status: Accepted

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

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            #いまみているグリッド
            q=queue.Queue()
            d=0
            #初めのグリッド
            q.put([i,j])
            x[i][j]=0
            #次々にグリッドを辿って全部のグリッド辿ったら終わり
            while q.qsize()!=0:
                #距離を加算
                d+=1
                l=q.qsize()
                #今いるグリッドの数は数えておく
                for t in range(l):
                    I,J=q.get()
                    #今いるグリッドから次のグリッドへ
                    #その判定は"そこにグリッドがあるか","そこが辿れるのか","すでに辿っているのか"の三つです。
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        #この更新をif文内で行わないと余計にグリッドを調べてしまう
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))

Submission status: Accepted

Solution code:
def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    from collections import defaultdict
    cnt = defaultdict(int)
    for item in s:
        for c in item:
            cnt[c] += 1
    if '#' not in cnt:
        print(H+W-2)
        quit()

    def bfs(row, col, R, C, s):
        from collections import deque
        q = deque()
        q.append([(row, col), 0])
        seen = set()
        ans = 0
        while q:
            (r, c), dist = q.popleft()
            ans = max(dist, ans)
            seen.add((r, c))
            for (next_r, next_c) in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if (next_r, next_c) not in seen and \
                    0 <= next_r < R and 0 <= next_c < C and \
                   s[next_r][next_c] == '.':
                    q.append([(next_r, next_c), dist + 1])
        return ans

    max_v = 0
    for h in range(H):
        for w in range(W):
            if s[h][w] == '.':
                max_v = max(max_v, bfs(h, w, H, W, s))
    print(max_v)
resolve()

Submission status: Accepted

Solution code:
import collections
H,W = map(int,input().split())
if H == W == 1:
    print(0)
    exit()
if (H == 1 and W == 2) or (H == 2 and W == 1):
    print(1)
    exit()
LL=[]
for i in range(H):
    LL.append(input())

L = ((1,0),(0,1),(-1,0),(0,-1))
q = collections.deque()
max_L = []
for i in range(H):
    for j in range(W):
        d = [[0]*W for i in range(H)]
        if LL[i][j] ==".":
            q.append((i,j))
            d[i][j] = 0
            max1 = 0
            while q:
                x,y = q.popleft()
                for dx,dy in L:
                    if 0>x+dx or x+dx>H-1 or 0>y+dy or y+dy>W-1 or d[x+dx][y+dy] !=0:
                        continue
                    if  LL[x+dx][y+dy] == ".":
                        d[x+dx][y+dy] = d[x][y] +1
                        q.append((x+dx,y+dy))
                        max1 = max(max1,d[x+dx][y+dy])
                        max_L.append(max1)
                        #print(q,d ,max1)
print(max(max_L))

Submission status: Accepted

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

def bfs(startx,starty):
    d = [[-1]*w for i in range(h)]
    q = deque([[startx,starty]])
    d[startx][starty] = 0
    cnt = 0
    while(q):
        x,y = q.popleft()
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x,new_y = x+i,y+j
            if (new_x>h-1) or (new_x<0) or (new_y>w-1) or (new_y<0):
                continue
        
            elif s[new_x][new_y] == '#':
                continue
        
            elif d[new_x][new_y] == -1:
                d[new_x][new_y] = d[x][y]+1
                q.append([new_x,new_y])
                cnt = max(cnt,d[new_x][new_y])
    
    return cnt

ans = 0

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

print(ans)

Submission status: Accepted

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

def bfs(x, y):
  D = [[10 ** 9 for i in range(W)] for j in range(H)]
  q = queue.Queue()
  q.put([x, y])
  D[y][x] = 0
  direct = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  max_distance = 0
  while q.qsize() != 0:
    x, y = q.get()
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H:
        continue
      if M[ny][nx] == "#":
        continue
      if D[ny][nx] > D[y][x] + 1:
        D[ny][nx] = D[y][x] + 1
        max_distance = max([max_distance, D[ny][nx]])
        q.put([nx, ny])
  return max_distance

result = 0
for y in range(H):
  for x in range(W):
    if M[y][x] == "#":
      continue
    result = max([result, bfs(x, y)])
print(result)

Submission status: Accepted

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

def bfs(startx,starty):
    d = [[-1]*W for _ in range(H)]
    q = deque([[startx,starty]])
    d[startx][starty] = 0
    cnt = 0
    while(q):
        x,y = q.popleft()
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x,new_y = x+i,y+j
            if(new_x>H-1 or new_x<0 or new_y>W-1 or new_y<0):
                continue
            elif(S[new_x][new_y] == "#"):
                continue
            elif(d[new_x][new_y] == -1):
                d[new_x][new_y] = d[x][y] + 1
                q.append([new_x,new_y])
                cnt = max(cnt,d[new_x][new_y])
    return cnt

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

Submission status: Accepted

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

def meiro(s):
    que=queue.Queue()
    dist=[[-1 for _ in range(W)] for _ in range(H)]
    dist[s[0]][s[1]]=0
    que.put(s)
    mv=((1,0),(-1,0),(0,1),(0,-1))
    max=0
    while not que.empty():
        h,w=que.get()
        for y,x in mv:
            nh=h+y
            nw=w+x
            if nh<0 or nh>=H or nw<0 or nw>=W:
                continue
            elif field[nh][nw]=="#":
                continue
            elif dist[nh][nw]!=-1:
                continue
            else:
                dist[nh][nw]=dist[h][w]+1
                que.put((nh,nw))
                if max<dist[nh][nw]:
                    max=dist[nh][nw]

    return max

ans=0
for i in range(H):
    for k in range(W):
        if field[i][k]=="#":
            continue
        tmp=meiro((i,k))
        if tmp>ans:
            ans=tmp
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=[list(input()) for _ in range(H)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
ans=0
def search(n,m):
    X=[[0]*W for _ in range(H)]
    X[n][m]=1
    ans=-1
    que=[]
    que.append((n,m))
    while que:
        newque=[]
        for x,y in que:
            for dx,dy in d:
                if 0<=x+dx<H and 0<=y+dy<W and s[x+dx][y+dy]=="." and X[x+dx][y+dy]==0:
                    X[x+dx][y+dy]=1
                    newque.append((x+dx,y+dy))
        ans+=1
        que=newque
    return ans
        
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            ans=max(ans,search(i,j))
                
print(ans)

Submission status: Accepted

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

from collections import deque
import itertools
import copy

def chk_bfd(sy,sx):
    m_max=0
    ma=copy.deepcopy(maze)
    ma[sy][sx]=0
    d=[(1,0),(-1,0),(0,1),(0,-1)]
    q=deque([[sy,sx]])
    while q:
        y,x=q.popleft()
        for dy,dx in d:
            if ma[y+dy][x+dx]=='.':
                q.append([y+dy,x+dx])
                ma[y+dy][x+dx]=ma[y][x]+1
                m_max=max(m_max,ma[y+dy][x+dx])
    return m_max

s=[]
for h in range(H+2):
    for w in range(W+2):
        if maze[h][w]=='.':
            s.append([h,w])

res=0
for sy,sx in s:
    res=max(res,chk_bfd(sy,sx))

print(res)