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 collections
import numpy as np
import sys
input = sys.stdin.readline

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
inf = float('inf')


def bfs(sx, sy):
    # sx,sy := スタートの座標
    # gx,gy := ゴールの座標
    d = [[-inf]*W for _ in range(H)]
    que = collections.deque()
    que.append([sx, sy])
    d[sx][sy] = 0
    while (len(que) > 0):
        p = que.popleft()
        # if p[0] == gx and p[1] == gy:
        #     break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and f[nx][ny] != "#" and d[nx][ny] == -inf):
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
        if len(p)==0:
            break
    return np.max(d)

# 入力
H, W = map(int, input().split())
f = [list(input()) for _ in range(H)]

res = 0
for h1 in range(H):
    for w1 in range(W):
        # 全"."を開始とする探索をする。
        # 最短経路で一番遠いポイントが理想的なゴール地点
        if f[h1][w1] == ".":
            # 理想的なゴール地点を更新
            res = max(res, bfs(h1,w1))
        else:
            continue
print(int(res))

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
from collections import deque

inputs = sys.stdin.readlines()
h, w = map(int, inputs[0].split())
S = deque(deque(map(lambda x: int(x=='.'), x)) for x in inputs[1:])
S.appendleft(deque([0]*w))
S.append(deque([0]*w))
for row in S:
    row.appendleft(0)
    row.append(0)

max_dist = 0
for y in range(1, h+1):
    for x in range(1, w+1):
        if S[y][x]:
            maze = deepcopy(S)
            queue = deque([(x, y, 0)])
            while queue:
                x, y, d = queue.popleft()
                d += 1
                maze[y][x] = 0
                for dx, dy in zip([0, 1, 0, -1], [-1, 0, 1, 0]):
                    if maze[y+dy][x+dx]:
                        queue.append((x+dx, y+dy, d))
                        maze[y+dy][x+dx] = 0
                        max_dist = max(max_dist, d)
print(max_dist)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
    
from collections import deque
import numpy as np
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 最大の地点を
def dfs(sx, sy):
    que = deque()
    # 各点までの最長距離の配列
    d = [[-1 for _ in range(W)] for _ in range(H)]
    que.append([sx, sy])
    d[sx][sy] = 0
    
    while(len(que) != 0):
        front = que.popleft()
        for i in range(4):
            nx = front[0] + dx[i]
            ny = front[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W):
                if maze[nx][ny] != "#" and d[nx][ny] == -1:
                    que.append([nx, ny])
                    d[nx][ny] = d[front[0]][front[1]] + 1
                else:
                    continue
            else:
                continue
    return np.max(d)

import itertools

ans = []
l1 = [(s1, s2) for s1 in range(H) for s2 in range(W)]


for v in l1:
    if maze[v[0]][v[1]] == "#":
        continue
    ans.append(dfs(v[0], v[1]))
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split(' '))
maze = [[ch for ch in input()] for _ in range(H)]
max_ans = -1
'''
幅優先探索 実装
'''
def bfs(sx, sy):
    queue = deque()
    queue.append([sx, sy])
    cost_map = [[None if maze[i][j] == '.' else -1 for j in range(W)] for i in range(H)]
    cost_map[sy][sx] = 0
    while queue:
        x, y = queue.popleft()
        for next_x, next_y in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if (-1 < next_x < W) and (-1 < next_y < H) and (cost_map[next_y][next_x] is None):
                queue.append([next_x, next_y])
                cost_map[next_y][next_x] = cost_map[y][x] + 1
    return max([max(x) for x in cost_map])

for i in range(W):
    for j in range(H):
        if maze[j][i] != '#':
            ans = bfs(i, j)
            if max_ans < ans:
                max_ans = ans
print(max_ans)

Submission status: Accepted

Solution code:
from collections import deque

def a():
    H,W = map(int,input().split())
    S = ["" for _ in range(H)]
    for _ in range(H):
        S[_] = input()
    b = lambda n:S[n//W][n%W] == '.'
    v = list(filter(b,range(H*W)))
    u = list(map(lambda n:(n%W,n//W),v))

    le = len(v)

    def bfs(root):
        i = 0
        depth = [[-1]*W for _ in range(H)]
        in_que = [[0]*W for _ in range(H)]
        q = deque()
        q.append((root,0))
        xx,yy = root
        in_que[yy][xx] = 1
        while i < le:
            r,d = q.popleft()
            x,y = r
            depth[y][x] = d
            i += 1
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                dx += x
                dy += y
                if 0 <= dx < W and 0 <= dy < H and in_que[dy][dx] == 0 and S[dy][dx] == ".":
                    q.append(((dx,dy),d+1))
                    in_que[dy][dx] = 1
        return depth
    
    print(max([max([max(y) for y in x]) for x in map(bfs,u)]))

a()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
def check(s,t):
    if (0 <= s <= w - 1) and (0 <= t <= h - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (not check(x,y) ) or grid[y][x] == '#':
            continue
        if (x,y) not in finished:
            finished.add((x,y))
            graph[y][x] = cost
            que.append([x+1,y,cost+1])
            que.append([x, y+1, cost+1])
            que.append([x-1,y,cost+1])
            que.append([x,y-1,cost+1])
ans = 0
inf = 400

for i in range(h):
    for j in range(w):
        que = deque()
        que.append([j,i,0])
        graph = [[inf for _ in range(w)] for _ in range(h)]
        bfs(que)
        for p in range(h):
            for q in range(w):
                if graph[p][q] < inf:
                    ans = max(ans, graph[p][q])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
H, W = map(int, input().split())
 
init_field = [list(input()) for _ in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
 
def bfs(x, y):
    distance = [[-1]*W for _ in range(H)]
    que = deque([])
    que.append((y, x))
    distance[y][x] = 0
    res = 0
    while que:
        y, x = que.popleft()
        res = max(res, distance[y][x])
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= nx < W and 0 <= ny < H and field[ny][nx] == "." and distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                que.append((ny, nx))
    return res

ans = 0
for sy in range(H):
    for sx in range(W):
        if init_field[sy][sx] == '#':
            continue
        field = [[i for i in row] for row in init_field]
        d = bfs(sx, sy)
        ans = max(ans, d)
print(ans)

Submission status: Accepted

Solution code:
import copy
h,w=map(int,input().split())
maze = [['#']+list(input())+['#'] for i in range(h)]
maze.insert(0,['#']*(w+2))
maze.append(['#']*(w+2))

def get_max_length_from_start(maze,x,y):
    ans_maze=[]
    min_now=1000000000
    max_length_list=[]
    tmp_maze=copy.deepcopy(maze)
    searching = [[y,x]]
    length=0
    while len(searching)!=0:
        next_searching_list=[]
        for point in searching:
            tmp_maze[point[0]][point[1]]=length
            mawari = [[point[0]+1,point[1]],[point[0]-1,point[1]],[point[0],point[1]+1],[point[0],point[1]-1]]
            next_searching = list(filter(lambda x:tmp_maze[x[0]][x[1]]==".",mawari))
            if len(next_searching)==0:
                max_length_list.append(length)
                continue
            next_searching_list += next_searching
        searching = list(map(list, set(map(tuple, next_searching_list))))
        length+=1
    return max(max_length_list)

true_max_length_list=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if maze[y][x]=='#':
            continue
        max_length=get_max_length_from_start(maze,x,y)
        true_max_length_list.append(max_length)

print(max(true_max_length_list))

Submission status: Accepted

Solution code:
import queue

q = queue.Queue()

H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
ans = 0
vec_x = [1,0,-1,0]
vec_y = [0,1,0,-1]

def bfs(sx,sy):
    #最短距離を格納する配列
    d = [[-1 for i in range(W)] for j in range(H)]
    d[sy][sx] = 0
    q.put([sx,sy])
    while not q.empty():
        current_xy = q.get()
        #4方向のループ
        for i in range(4):
            nx = current_xy[0] + vec_x[i]
            ny = current_xy[1] + vec_y[i]

            #移動が可能か
            if( (nx >= 0 and nx < W ) and (ny >= 0 and ny < H ) ):
                if S[ny][nx] != "#":
                    #すでにおとずれていないか
                    if d[ny][nx] == -1:
                        q.put([nx,ny])
                        d[ny][nx] = d[current_xy[1]][current_xy[0]] + 1
    return d[current_xy[1]][current_xy[0]]

for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == "#":
            continue
        if ans <= bfs(sx,sy):
            ans = bfs(sx,sy)

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
inf=float("inf")
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy]==".":
            data=[[inf]*W for i in range(H)]
            que=[[sx,sy]]
            data[sx][sy]=0
            count=1
            while que:
                h=[]
                for x,y in que:
                    for dx,dy in d:
                        nx,ny=x+dx,y+dy
                        if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                            h.append([nx,ny])
                            data[nx][ny]=count
                que=h
                count+=1
            for i in range(H):
                for j in range(W):
                    if data[i][j]!=inf:
                        ans=max(ans,data[i][j])
print(ans)

Submission status: Accepted

Solution code:
import collections

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

m = []
for _ in range(h):
    m.append(list(input()))


ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == '#':
            continue

        checked = [[False]*w for _ in range(h)]
        q = collections.deque()
        q.append((i, j, 0))
        checked[i][j] = True
        while True:
            x, y, s = q.popleft()
            #print(q)

            if x > 0 and m[x-1][y] != '#' and checked[x-1][y] == False:
                q.append((x-1, y, s+1))
                checked[x-1][y] = True

            if x+1 < h and m[x+1][y] != '#' and checked[x+1][y] == False:
                q.append((x+1, y, s+1))
                checked[x+1][y] = True

            if y > 0 and m[x][y-1] != '#' and checked[x][y-1] == False:
                q.append((x, y-1, s+1))
                checked[x][y-1] = True

            if y+1 < w and m[x][y+1] != '#' and checked[x][y+1] == False:
                q.append((x, y+1, s+1))
                checked[x][y+1] = True

            ans = max(ans, s)

            if len(q) == 0:
                break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = [int(v) for v in input().split()]

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

def contains(maze, i, j):
    if i < 0 or i >= h:
        return False
    if j < 0 or j >= w:
        return False
    return True

def far(maze, i0, j0):
    q = deque([])

    q.append((i0, j0, 0))

    closed = set()
    closed.add((i0, j0))
    max_dist = 0
    max_p = None
    while len(q) > 0:
        e = q.popleft()
        
        i = e[0]
        j = e[1]
        cost = e[2] + 1
        for n in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            ni = i + n[0]
            nj = j + n[1]
            nkey = (ni, nj)
            if not contains(maze, ni, nj):
                continue
            if maze[ni][nj] != '.':
                continue
            nkey = (ni, nj)
            if nkey in closed:
                continue
            closed.add(nkey)
            q.append((ni, nj, cost))
            if max_dist < cost:
                max_dist = cost
                max_p = nkey
    return max_p, max_dist
    
def solve(maze):
    max_dist = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] != '.':
                continue
            p, dist = far(maze, i, j)
            if max_dist < dist:
                max_dist = dist
    return max_dist

print(solve(maze))

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(H):
    maze.append(list(input()))
def bfs(sx,sy):
    INF = -1
    cost = [[INF]*W for _ in range(H)]
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.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 cost[nx][ny] == INF:
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost
def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] != "#":
                sx,sy = i,j
                cs = bfs(sx,sy)
                for k in range(len(cs)):
                    if max(cs[k]) > ans:
                        ans = max(cs[k])
    return ans
print(solve())

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
field = []

for i in range(h):
    field.append(list(input()))

out = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            seen = [[0 for m in range(w)] for n in range(h)]
            seen[i][j] = 1
            q = deque([])
            q.append((i, j, 0))
            while q:
                (y, x, cnt) = q.popleft()
                # print(y,x)
                # print(seen)
                for ny, nx in (y, x + 1), (y, x - 1), (y + 1, x), (y - 1, x):
                    if ny < 0 or ny >= h or nx < 0 or nx >= w:
                        pass
                    elif field[ny][nx] == '.' and seen[ny][nx] == 0:
                        q.append((ny, nx, cnt + 1))
                        seen[ny][nx] = 1

            out = max(out, cnt)
print(out)

Submission status: Accepted

Solution code:
from collections import deque

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

INF = -1

def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        # if p[0] == gx and p[1] == gy:
        #     break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    ret = -1
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

ans = -1
for i in range(H):
    for j in range(W):
            sx, sy = i, j
            if c[sx][sy] == '#':
                continue
            ans = max(ans, bfs())
print(ans)

Submission status: Accepted

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

def bfs():
    dist = [[-float('inf')]*W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    q = deque()
    q.append([sy,sx])
    dist[sy][sx] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] == '.' and dist[ny][nx] == -float('inf'):
                q.append([ny,nx])
                dist[ny][nx] = dist[p[0]][p[1]] + 1
    longest_dist = 0
    for y in range(H):
        for x in range(W):
            longest_dist = max(longest_dist,dist[y][x])
    return longest_dist
ans = 0
for sy in range(H):
    for sx in range(W):
        if grid[sy][sx] == '.':
            ans = max(bfs(),ans)

print(ans)

Submission status: Accepted

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

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
INF = 10**9 + 7

def bfs(y, x):
    res = 0
    q = [[y,x]]
    D = [[INF for _ in range(W)] for _ in range(H)]
    D[y][x] = 0
    while len(q):
        y, x = q.pop(0);
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= ny <= H-1 and 0 <= nx <= W-1): continue
            if S[ny][nx] == '#': continue
            if D[ny][nx] > D[y][x] + 1:
                D[ny][nx] = D[y][x] + 1
                q.append([ny,nx])
                res = max(res, D[ny][nx])
    return res

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

Submission status: Accepted

Solution code:
# coding:utf-8
from scipy.sparse.csgraph import floyd_warshall

int_max = 2 ** 63 - 1

def get_cost(start, end):
    return 1 if start == '.' and end == '.' else 2 ** 63 - 1


def main():

    H, W = map(int, input().split(' '))
    ad_table = [[int_max for _ in range(H*W)] for _ in range(H*W)]
    maze = []
    for _ in range(H):
        maze.append(input())

    for si in range(H):
        for sj in range(W):
            for ti in range(H):
                for tj in range(W):
                    if si == ti and sj == tj:
                        ad_table[(si*W)+sj][(ti*W)+tj] = 0
                    elif (abs(si - ti) == 1 and sj - tj == 0) or (si - ti == 0 and abs(sj - tj) == 1):
                        ad_table[(si*W)+sj][(ti*W)+tj] = get_cost(maze[si][sj], maze[ti][tj])

    res = floyd_warshall(ad_table)
    ans = -1
    for i in range(H*W):
        for j in range(i+1,H*W):
            if res[i][j] != int_max:
                ans = max(res[i][j], ans)
    print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
s = ['#' * (w + 2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w + 2)]
# print(*s, sep='\n')

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


def bfs(si, sj):
    queue = deque([(si, sj, 0)])
    cost = [[-1] * (w + 2) for _ in range(h + 2)]
    cost[si][sj] = 0
    while queue:
        ci, cj, cc = queue.popleft()
        for k in range(4):
            ni = ci + di[k]
            nj = cj + dj[k]
            if s[ni][nj] == '#':
                continue
            if cost[ni][nj] != -1:
                continue
            queue.append((ni, nj, cc + 1))
            cost[ni][nj] = cc + 1

    return max(map(lambda x: max(x), cost))


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

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    reg = [[0] * w for _ in range(h)]    
    for i in range(h):
        for j in range(w):
            d = [[float("inf")] * w for _ in range(h)]
            que = deque([])
            res = 0
            if field[i][j] == ".":
                sx = i
                sy = j
                que.append([sx, sy])
                d[sx][sy] = 0
                
                dx = [0, 1, 0, -1]
                dy = [1, 0, -1, 0]
    
                while len(que) != 0:
                    p = que.popleft()

                    for k in range(4):
                        nx = p[0] + dx[k]
                        ny = p[1] + dy[k]

                        if 0 <= nx < h and 0 <= ny < w and field[nx][ny] != "#" and d[nx][ny] == float("inf"):
                            que.append([nx, ny])
                            d[nx][ny] = d[p[0]][p[1]] + 1
                            res = max(res, d[nx][ny])
                reg[sx][sy] = res
    global ans
    for i in range(h):
        for j in range(w):
            ans = max(ans, reg[i][j])


h, w = map(int, input().split())
field =[list(input()) for _ in range(h)]
ans = 0
bfs()

print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    S = []
    max_move = 0
    for _ in range(H):
        S.append(list(input()))

    for hs in range(H):
        for ws in range(W):
            if S[hs][ws] == '#':
                continue
            answer = bfs(S, H, W, hs, ws)
            if max_move < answer:
                max_move = answer
    print(max_move)

def bfs(S, H, W, hs, ws):
    visited = [[-1] * W for _ in range(H)]
    s = (hs, ws, 0)
    queue = [s]
    c = s
    max_c = 0
    while len(queue) > 0:
        c = queue.pop(0)
        count = c[2]
        if count > max_c:
            max_c = count
        # 確認済みに追加
        visited[c[0]][c[1]] = 1
        # 上
        enqueue(c[0] - 1, c[1], S, H, W, queue, count, visited)
        # 左
        enqueue(c[0], c[1] - 1, S, H, W, queue, count, visited)
        # 下
        enqueue(c[0] + 1, c[1], S, H, W, queue, count, visited)
        # 右
        enqueue(c[0], c[1] + 1, S, H, W, queue, count, visited)
    # 最短距離を返す
    return max_c

def enqueue(i, j, S, H, W, queue, count, visited):
    if i >= 0 and i < H and j >= 0 and j < W and visited[i][j] == -1 and S[i][j] == '.':
        queue.append((i, j, count + 1))
        visited[i][j] = 1

main()

Submission status: Accepted

Solution code:
dxys = [(-1,0), (1,0), (0,-1), (0,1)]

H, W = map(int, input().split())
Sss = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

N = H*W
adjL = [[] for _ in range(N)]
for x in range(1, H+1):
    for y in range(1, W+1):
        if Sss[x][y] != '.': continue
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if Sss[x2][y2] != '.': continue
            z = (x-1)*W + y-1
            z2 = (x2-1)*W + y2-1
            adjL[z].append(z2)

# 重みなしグラフの直径を求める
def getDiameterOfUnweightedGraph(adjList):
    numV = len(adjList)
    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        return cost - 1
    return max([bfs(vSt) for vSt in range(numV)])

maxDist = getDiameterOfUnweightedGraph(adjL)
print(maxDist)

Submission status: Accepted

Solution code:
# BFS queue
import queue
import copy

import time
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
l = 0
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
            l += 1
if l == H*W:
    print(H+W-2)
    exit()
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

H, W = map(int, input().split())
S = []
for i in range(H):
    s1 = list(input())
    S.append(s1)
    
graph = [[0 for _ in range(H*W)] for _ in range(H*W)]

for i in range(H-1):
    for j in range(W):
        if S[i][j] == "." and S[i+1][j] == ".":
            graph[j+(i*W)][j+(W*(i+1))] = 1
            graph[j+(W*(i+1))][j+(i*W)] = 1
for i in range(H):
    for j in range(W-1):
        if S[i][j] == "." and S[i][j+1] == ".":
            graph[j+(i*W)][j+(W*i)+1] = 1
            graph[j+(W*i)+1][j+(i*W)] = 1
            
d = floyd_warshall(graph)

ans = 0
for i in range(H*W):
    for j in range(i+1,H*W):
        if d[i][j] != float("inf"):
            ans = max(ans, d[i][j])

print(int(ans))

Submission status: Accepted

Solution code:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

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

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)

Submission status: Accepted

Solution code:
import copy

def judge1(masu,h,w):
    if (masu[0]>=0)&(masu[0]<h)&(masu[1]>=0)&(masu[1]<w):
        return True
    else:
        return False
    
def judge2(masu,s):
    if s[masu[0]][masu[1]] == '.':
        return True
    else:
        return False
    
def tsugi(i,j,h,w,s2):
    ans=[]
    for masu in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
        if judge1(masu,h,w):
            if judge2(masu,s2):
                ans.append(masu)
    return ans
    


def solve(i,j,s,h,w):
    ma = 0
    s2 = copy.deepcopy(s)
    if s2[i][j]=='.':
        s2[i][j]='#'
        nex = tsugi(i,j,h,w,s2)
        while len(nex)!=0 :
            ma+=1
            nex2=[]
            for n in nex:
                nex2[len(nex2):] = tsugi(n[0],n[1],h,w,s2)
                s2[n[0]][n[1]]='#'
            nex = set(nex2)
    return ma


h,w=map(int,input().split())
s = []
ma = 0
for i in range(h):
    s.append(list(input()))
for i in range(h):
    for j in range(w):
        ans = solve(i,j,s,h,w)
        ma = max(ma,ans)
print(ma)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
infinity = -10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1
#print(A)
N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i][j] ==1:
            if A[i+1][j] == 1:
                G[W*(i+1)+j].append(W*i+j)
                G[W*i+j].append(W*(i+1)+j)

            if A[i][j+1] == 1:
                G[W*i+(j+1)].append(W*i+j)
                G[W*i+j].append(W*i+(j+1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0

"""
for i in range(N):
    I = i//W
    J = i%W
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))
"""

for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            d = BFS(W*i+j)
            ans = max(ans,max(d))

print(ans)

Submission status: Accepted

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

def bfs(i,j,d):
    d_max=0
    used=[[False for j in range(W)] for i in range(H)]
    Q=deque()
    Q.append((i,j,d))
    used[i][j]=True
    while Q:
        i,j,d=Q.popleft()
        for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if ni<0 or nj<0 or ni>=H or nj>=W:
                continue
            if M[ni][nj]=='.' and not used[ni][nj]:
                d_max=max(d_max,d+1)
                used[ni][nj]=True
                Q.append((ni,nj,d+1))
    return d_max

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

print(ans)