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:
H,W = map(int,input().split())
D = [[0]*(W) for i in range(H)]

for i in range(H):
    S = input()
    for j in range(W):
        s = S[j]
        if s=='.':
            D[i][j] = 1

ans = 0
import heapq

for i in range(H):
    for j in range(W):
        if D[i][j] == 1:
            tmp = 0
            h = [[0,i,j]]
            visited = [[0]*W for i in range(H)]
            while h!=[]:
                w,nowi,nowj = heapq.heappop(h)
                tmp = max(tmp,w)
                visited[nowi][nowj] = 1
                if 0<nowi<H-1:
                    for k in [-1,1]:
                        if D[nowi+k][nowj]==1 and visited[nowi+k][nowj]==0:
                            heapq.heappush(h,[w+1,nowi+k,nowj])
                            visited[nowi+k][nowj]=1
                elif nowi+1<=H-1:
                    if D[nowi+1][nowj]==1 and visited[nowi+1][nowj]==0:
                        heapq.heappush(h,[w+1,nowi+1,nowj])
                        visited[nowi+1][nowj]=1
                elif nowi-1 >=0:
                    if D[nowi-1][nowj]==1 and visited[nowi-1][nowj]==0:
                        heapq.heappush(h,[w+1,nowi-1,nowj])
                        visited[nowi-1][nowj]=1

                if 0<nowj<W-1:
                    for k in [-1,1]:
                        if D[nowi][nowj+k]==1 and visited[nowi][nowj+k]==0:
                            heapq.heappush(h,[w+1,nowi,nowj+k])
                            visited[nowi][nowj+k]=1
                elif nowj-1>=0:
                    if D[nowi][nowj-1]==1 and visited[nowi][nowj-1]==0:
                        heapq.heappush(h,[w+1,nowi,nowj-1])
                        visited[nowi][nowj-1]=1
                elif nowj+1 <= W-1:
                    if D[nowi][nowj+1]==1 and visited[nowi][nowj+1]==0:
                        heapq.heappush(h,[w+1,nowi,nowj+1])
                        visited[nowi][nowj+1]=1
            ans = max(ans,tmp)
            
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product
import numpy as np

H, W = map(int, input().split())
S = np.zeros((H, W), dtype='U1')
for hi in range(H):
    raw = input()
    S[hi, :] = list(raw)

maxmove = np.zeros_like(S, dtype='int')

for hi, wi in product(range(H), range(W)):
    # hi, wiをスタート位置とする場合
    if S[hi, wi] == '#': continue

    # 必要な諸々を定義
    VisitOrScheduled = np.zeros_like(S, dtype='bool')
    VisitOrScheduled[hi, wi] = True
    nummove = np.zeros_like(S, dtype='int')
    deq = deque()

    deq.append((hi, wi))
    while True:
        try:
            hj, wj = deq.popleft()
        except IndexError:
            break
        VisitOrScheduled[hj, wj] = True
        for neighbour in [(hj, wj-1), (hj, wj+1), (hj+1, wj), (hj-1, wj)]:
            if not (0 <= neighbour[0] < H and 0 <= neighbour[1] < W): continue
            if S[neighbour] == '#':
                continue
            if not VisitOrScheduled[neighbour]:
                nummove[neighbour] = nummove[hj, wj] + 1
                deq.append(neighbour)
                VisitOrScheduled[neighbour] = True
    
    maxmove[hi, wi] = np.max(nummove)

print(np.max(maxmove))

Submission status: Accepted

Solution code:
# 幅優先探索
# YouTube解説を見てから (https://www.youtube.com/watch?v=1oLDDdWRu6Y&feature=youtu.be)

# queue.Queueよりも、collections.dequeの方が高速だった
# 前者を使うとTLEになっちゃった。。。

from queue import Queue
from collections import deque
from itertools import product
import numpy as np

H, W = map(int, input().split())
S = np.zeros((H, W), dtype='U1')
for hi in range(H):
    raw = input()
    S[hi, :] = list(raw)

maxmove = np.zeros_like(S, dtype='int')

for hi, wi in product(range(H), range(W)):
    # hi, wiをスタート位置とする場合
    if S[hi, wi] == '#': continue

    # 必要な諸々を定義
    # flag = np.zeros_like(S, dtype='int')
    # flag[:] = NOT_VISITED
    # flag[hi, wi] = VISITED
    VisitOrScheduled = np.zeros_like(S, dtype='bool')
    VisitOrScheduled[hi, wi] = True
    nummove = np.zeros_like(S, dtype='int')
    # queue = Queue()
    deq = deque()

    # queue.put((hi, wi))
    deq.append((hi, wi))
    # while queue.empty() == False:
    while True:
        try:
            # hj, wj = queue.get()
            hj, wj = deq.popleft()
        except IndexError:
            break
        # flag[hj, wj] = VISITED
        VisitOrScheduled[hj, wj] = True
        for neighbour in [(hj, wj-1), (hj, wj+1), (hj+1, wj), (hj-1, wj)]:
            if not (0 <= neighbour[0] < H and 0 <= neighbour[1] < W): continue
            if S[neighbour] == '#':
                continue
            # if flag[neighbour] == NOT_VISITED:
            if not VisitOrScheduled[neighbour]:
                nummove[neighbour] = nummove[hj, wj] + 1
                # queue.put(neighbour)
                deq.append(neighbour)
                # flag[neighbour] = SCHEDULED
                VisitOrScheduled[neighbour] = True
    
    maxmove[hi, wi] = np.max(nummove)

print(np.max(maxmove))

Submission status: Accepted

Solution code:
from collections import deque

#キューを使った幅優先探索を使うのが正解らしい

#グラフを隣接リストで表現するときに使う関数
def make_list(i, j):
    global c
    global h
    global w

    l = []
    a = [-1, 0, 1]
    b = [-1, 0, 1]

    for y in a:
        for x in b:
            if i+y < 0 or j+x < 0 or i+y >= h or j+x >= w:
                continue
            if (x == 0 and y == 0) or (abs(x) == 1 and abs(y) == 1):
                continue
            if c[i][j] == 1:
                continue
            if c[i + y][j + x] == 0:
                l.append((i+y)*w + (j+x))

    return l

hw = list(map(int, input().split()))
h = hw[0]
w = hw[1]

c = [[0] * w for i in range(h)]

for i in range(h):
    line = input()
    for j in range(w):
        if line[j] == '.':
            c[i][j] = 0
        else:
            c[i][j] = 1

rlist = []
for i in range(h):
    for j in range(w):
        rlist.append(make_list(i, j))

def bfs(u):
    color[u] = 'gray'
    d[u] = 0
    queue.append(u)

    while(len(queue) > 0):
        u = queue.popleft()
        for rl in rlist[u]:
            if color[rl] == 'white':
                queue.append(rl)
                color[rl] = 'gray'
                d[rl] = d[u] + 1
        color[u] = 'black'

result = 0
for i in range(len(rlist)):
    color = ['white'] * len(rlist)
    queue = deque([])
    d = [-1] * len(rlist)
    if len(rlist[i]) > 0:
        bfs(i)
        if result < max(d):
            result = max(d)

print(result)

Submission status: Accepted

Solution code:
from collections import deque

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

area = [[] for _ in range(h+2)]

for i in range(h+2):
    if i == 0 or i == h+1:
        area[i] = ['#'] * (w+2)
    else:
        area[i] = list(input())
        area[i].insert(0, '#')
        area[i].append('#')

def bfs(i, j):
    distance_matrix = [[1000 for _ in range(w+2)] for _ in range(h+2)]
    distance_matrix[i][j] = 0
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    d = deque()
    d.append([i, j])
    max_distance = 0
    while len(d) > 0:
        x, y = d.popleft()
        for q, v in move:
            if area[x+q][y+v] =='.' and distance_matrix[x+q][y+v] == 1000:
                d.append([x+q,y+v])
                distance = distance_matrix[x][y] + 1
                distance_matrix[x+q][y+v] = distance
                if distance > max_distance:
                    max_distance = distance
    return max_distance

max_distance = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if area[i][j] == '#':
            continue
        else:
            distance = bfs(i, j)
            if distance > max_distance:
                max_distance = distance


print(max_distance)

Submission status: Accepted

Solution code:
""""
3 5
...#.
.#.#.
.#...
"""
from collections import deque
import numpy as np

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


def make_wall(W, Map):
    for map_row in Map:
        map_row.append("#")
        map_row.insert(0, "#")

    wall = ["#"]*(W+2)
    Map.append(wall)
    Map.insert(0, wall)
    return Map


start_list = deque()
search_list = deque()
Map = make_wall(W, Map)
H += 2
W += 2

start_h = 0
for h in range(H):
    start_w = 0
    for w in range(W):
        if Map[h][w] == ".":
            start_list.append([start_h, start_w])
        start_w += 1
    start_h += 1



max_cost = 0
while start_list != deque():
    search_list.append(start_list.popleft())
    cost_map = np.array([[0] * W for i in range(H)])
    search_map = np.array([[0] * W for i in range(H)])

    while search_list != deque():
        tmp = search_list.popleft()
        x = tmp[0]
        y = tmp[1]
        search_map[x][y] = 1
        if Map[x][y+1] == "." and search_map[x][y+1] == 0 and [x, y+1] not in search_list:
            search_list.append([x, y+1])
            cost_map[x][y+1] = cost_map[x][y]+1
        if Map[x][y-1] == "." and search_map[x][y-1] == 0 and [x, y-1] not in search_list:
            search_list.append([x, y-1])
            cost_map[x][y-1] = cost_map[x][y]+1
        if Map[x+1][y] == "." and search_map[x+1][y] == 0 and [x+1, y] not in search_list:
            search_list.append([x+1, y])
            cost_map[x+1][y] = cost_map[x][y]+1
        if Map[x-1][y] == "." and search_map[x-1][y] == 0 and [x-1, y] not in search_list:
            search_list.append([x-1, y])
            cost_map[x-1][y] = cost_map[x][y]+1
    cost_map = np.array(cost_map)
    if max_cost < np.amax(cost_map):
        max_cost = np.amax(cost_map)

print(max_cost)

Submission status: Accepted

Solution code:
from queue import Queue
INF = 999999


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

m = 0
for si in range(H):
    for sj in range(W):
        if S[si][sj] == '#':
            continue
        
        q = Queue()
        q.put((si, sj, 0))
        done = [None] * H
        for i in range(H):
            done[i] = [False] * W
        done[si][sj] = True

        unit = ((1, 0), (-1, 0), (0, 1), (0, -1))
        while not q.empty():
            i, j, w = q.get()

            for u in unit:
                nexti = i + u[0]
                nextj = j + u[1]
                if nexti >= 0 and nexti < H and nextj >= 0 and nextj < W and S[nexti][nextj] == '.' and (not done[nexti][nextj]):
                    q.put((nexti, nextj, w+1))
                    m = max(m, w + 1)
                    done[nexti][nextj] = True
print(m)

Submission status: Accepted

Solution code:
import copy
H,W=map(int,input().split())

maze=[]
maze.append(["#"]*(W+2))
for h in range(H):
    line=list(input())

    maze.append(["#"]+line+["#"])

maze.append(["#"]*(W+2))


maze_ori=copy.deepcopy(maze)

maxd=0

for h in range(1,H+1):
    for w in range(1,W+1):
        maze=copy.deepcopy(maze_ori)
        if maze[h][w]=="#":
            continue
        else:
            next_flag=True


        direction=[[-1,0],[0,-1],[1,0],[0,1]]
        distance=0
        maze[h][w]=distance

        next_list=[]
        next_list.append([h,w])
        while next_flag is True:
            p_list=next_list
            next_list=[]
            distance+=1
            next_flag=False
            for p in p_list:
                for d in direction:
                    i=p[0]+d[0]
                    j=p[1]+d[1]

                    if maze[i][j]==".":
                        maze[i][j]=distance
                        next_list.append([i,j])
                        next_flag=True
            
        maxd=max(maxd,distance-1)

print(maxd)

Submission status: Accepted

Solution code:
from itertools import count, combinations, product

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

H += 2
W += 2

visited = [2**31]*(W*H)

for i in range(1,H-1):
    S = input()
    for j,v in zip(range(1,W-1),S):
        if v == '.':
            visited[i*W + j] = 0

res = 1
D = (W,-W,1,-1)

for i in range(W*H):
    if visited[i] == 2**31:
        continue
    q = [i]
    visited[i] = i
    for dist in count():
        if not q:
            break
        nq = []
        for j in q:
            for d in D:
                if visited[j+d] < i:
                    visited[j+d] = i
                    nq.append(j+d)
        q = nq
    res = max(dist, res)

print(res-1)

Submission status: Accepted

Solution code:
from itertools import count, combinations, product

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

grid = [[False]*(W+2) for _ in range(H+2)]

for i in range(1,H+1):
    S = input()
    for j,v in zip(range(1,W+1),S):
        grid[i][j] = v == '.'

visited = [[0 if v else float('inf') for v in row] for row in grid]
cnt = 1
res = 0
for i,j in product(range(H+2),range(W+2)):
    if not grid[i][j]:
        continue
    q = [(i,j)]
    visited[i][j] = cnt 
    for d in count():
        if not q:
            break
        nq = []
        for x,y in q:
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                if visited[x+dx][y+dy] < cnt:
                    visited[x+dx][y+dy] = cnt
                    nq.append((x+dx,y+dy))
        q = nq
    cnt += 1
    res = max(d-1, res)

print(res)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain
INF = 10**18 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def main():
    max_num = 0
    for sy in range(H):
        for sx in range(W):
            if S[sy][sx] == "#":
                continue
            m = check_max_route(sx, sy)
            max_num = max(max_num, m)
    print(max_num)
    
def check_max_route(x,y):
    state=[[INF for _ in range(W)] for _ in range(H)]
    state[y][x]=0
    q = deque([(x, y)])
    while q:
        tx, ty = q.popleft()
        tr = state[ty][tx]
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            x, y = tx+dx, ty+dy
            if not (0 <= x < W and 0 <= y < H):
                continue
            if S[y][x] == "#":
                continue
            if state[y][x] <= tr+1:
                continue
            state[y][x] = tr+1
            q.append((x, y))
    m = max([x for x in chain(*state) if x != INF])
    return m    
main()

Submission status: Accepted

Solution code:
from itertools import count, combinations, product

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

grid = [[False]*(W+2) for _ in range(H+2)]

for i in range(1,H+1):
    S = input()
    for j,v in zip(range(1,W+1),S):
        grid[i][j] = v == '.'

visited = [[0 if v else float('inf') for v in row] for row in grid]
cnt = 1
def dist(p1,p2):
    global cnt
    q = [p1]
    visited[p1[0]][p1[1]] = cnt 
    for d in count():
        if not q:
            break
        nq = []
        for x,y in q:
            if (x,y) == p2:
                cnt += 1
                return d
            else:
                for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                    if visited[x+dx][y+dy] < cnt:
                        visited[x+dx][y+dy] = cnt
                        nq.append((x+dx,y+dy))
        q = nq
    cnt += 1
    return float('inf')

emp = [(i,j) for i,j in product(range(H+2),range(W+2)) if grid[i][j]]

print(max(dist(*p) for p in combinations(emp,2)))

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain

INF = 10**18

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

def check_max_route(sx, sy):
    r = [[INF for _ in range(W)] for _ in range(H)]
    r[sy][sx] = 0
    q = deque([(sx, sy)])
    while q:
        tx, ty = q.popleft()
        tr = r[ty][tx]

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            x, y = tx+dx, ty+dy
            if not (0 <= x < W and 0 <= y < H):
                continue
            if S[y][x] == "#":
                continue
            if r[y][x] <= tr+1:
                continue
            r[y][x] = tr+1
            q.append((x, y))
    
    m = max([x for x in chain(*r) if x != INF])
    return m

max_num = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == "#":
            continue
        m = check_max_route(sx, sy)
        max_num = max(max_num, m)

print(max_num)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = ''
for _ in range(h):
    maze += input() + '#'
n = h*(w+1)
graph = [[] for _ in range(n)]
dire = [-w-1, -1, 1, w+1]
for i in range(n):
    if maze[i]=='#':
        continue
    for j in dire:
        ind = i+j
        if ind < 0 or n <= ind or maze[ind]=='#':
            continue
        graph[i].append(ind)
que = deque()
def BFS(node):
    for i in graph[node]:
        if lengths[i]<0:
            lengths[i] = lengths[node]+1
            que.append(i)
    if len(que)>0:
        BFS(que.popleft())
starts = [i for i, j in enumerate(graph) if len(j)>0]
max_len = 0
for start in starts:
    lengths = [-1]*n
    lengths[start] = 0
    BFS(start)
    max_len = max(max_len, max(lengths))
print(max_len)

Submission status: Accepted

Solution code:
from queue import Queue

def solve(h, w, SS):
    m = {
        (x, y): S[x] == '.'
        for y, S in enumerate(SS)
        for x in range(len(S))
    }
    conditions = {
        (-1, 0): lambda x, y: x > 0,
        (1, 0): lambda x, y: x < w - 1,
        (0, -1): lambda x, y: y > 0,
        (0, 1): lambda x, y: y < h - 1
    }

    def calc_max_len(x0, y0):
        q = Queue(maxsize = h * w)
        q.put((x0, y0))
        d = {(x0, y0): 0}
        max_len = 0
        while not q.empty():
            x, y = q.get(block=False)
            for dx, dy in conditions:
                key = (x + dx, y + dy)
                if conditions[(dx, dy)](x, y) and m[key] and key not in d:
                    q.put(key)
                    d[key] = d[(x, y)] + 1
            if max_len < d[(x, y)]:
                max_len = d[(x, y)]
        return max_len

    return max(calc_max_len(x, y) for x, y in filter(lambda key: m[key], m))

_h, _w = map(int, input().split())
_SS = [input() for _ in range(_h)]
print(solve(_h, _w, _SS))

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]
ls = []
count = 0
for i in range(H):
    tmp = list(input())
    maze.append(tmp)
    for j in range(W):
        if tmp[j] != "#":
            ls.append([i,j])
            count += 1
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 ls:
        sx,sy = i[0],i[1]
        cs = bfs(sx,sy)
        for k in range(len(cs)):
            if ans == count:
                break
            if max(cs[k]) > ans:
                ans = max(cs[k])
    return ans
print(solve())

Submission status: Accepted

Solution code:
import itertools
H,W= [int(x) for x in input().split()]
meiro=[list(input())for _ in range(H)]
#print(meiro)
ans=0
dx = [1,0,-1,0]
dy=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    result=[[0]*W for _ in range(H)]
    cnt=0
    #print(i,j)
    if meiro[i][j]=="#":
      continue
    elif meiro[i][j]==".":
      stk =[[i,j]]
      result[i][j]=1
      while stk:
        x,y = stk.pop(0)
        
        for r in range(4):
          xx,yy=x+dx[r],y+dy[r]
          if yy<0 or xx<0 or W<=yy or H<=xx or meiro[xx][yy]=="#" or result[xx][yy]!=0:
            continue
          result[xx][yy]=result[x][y]+1
          stk.append([xx,yy])
      for l in range(H):
        for t in range(W):
          ans = max(ans,result[l][t])
print(ans-1)

Submission status: Accepted

Solution code:
import numpy as np
def min_rounte(s, sta, path):
    move = [[0,1],[0,-1],[1,0],[-1,0]]
    for i in move:
        ax = [sta[0]+i[0], sta[1]+i[1]]
        if s[ax[0]][ax[1]] == -1:
            continue
        if s[ax[0]][ax[1]] > path:
            s[ax[0]][ax[1]] = path
    return s
 
def bfs(s, sta):
    s_ = np.array(s)
    s_[sta[0]][sta[1]] = 0
    tmp = sta
    for i in range(400):
        ind = np.where(s_==i)
        for j in range(len(ind[0])):
            s_ = min_rounte(s_, [ind[0][j], ind[1][j]], i+1)
        if len(ind[0]) == 0:
            break
        tmp = [[ind[0][k], ind[1][k]] for k in range(len(ind[0]))]
    return i-1, tmp
        

h, w = map(int, input().split())
#s_ = [[0 if i=="." else -1 for i in input()] for j in range(h)]
s = [[-1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == ".":
            s[i+1][j+1] = 512
        else:
            s[i+1][j+1] = -1

for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == -1:
            continue
        temp, ax = bfs(s, [i,j])
        break
ans = 1
for i in ax:
    ans_, t = bfs(s, i)
    if ans_ > ans:
        ans = ans_

print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]  # H*W個

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    ans = 0
    for s in st:
        dist = [[-1]*W for h in range(H)]
        if c[s[0]][s[1]] == "#":
            continue
        bfs(*s)
        for t in st:
            if s == t or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, dist[t[0]][t[1]])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]  # H*W個

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    ans = 0
    for s in st:
        dist = [[-1]*W for h in range(H)]
        if c[s[0]][s[1]] == "#":
            continue
        bfs(s[0], s[1])
        for t in st:
            if s == t or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, dist[t[0]][t[1]])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

# input
H, W = map(int, input().split())
H += 2
W += 2

S = [["#"]*W]+[list("#"+input()+"#") for _ in range(H-2)]+[["#"]*W]

# process
ans = 0

# (r,c)がスタートの場合を順に確認
for r in range(1, H-1):
    for c in range(1, W-1):
        if S[r][c] == "#":
            continue

        # スタートから該当マスまでの移動回数
        dist = [[-1]*W for _ in range(H)]
        dist[r][c] = 0

        dq = deque([(r, c)])

        while dq:
            cr, cc = dq.popleft()
            
            if dist[cr][cc] > ans:
                # 移動回数の最大値更新
                ans = dist[cr][cc]
            
            for nr, nc in ((cr+1, cc), (cr-1, cc), (cr, cc+1), (cr, cc-1)):
                if S[nr][nc] == "." and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[cr][cc]+1
                    dq.append((nr, nc)) 

# output
print(ans)

Submission status: Accepted

Solution code:

def get_next_str():
    return input().rstrip("\n")
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])
def solve(maze, start_r, start_c):
    
    distances = {}
    offsets = [(-1,0),(1,0),(0,-1),(0,1)]
    
    distances[start_r, start_c] = 0
    candidates = [(start_r, start_c)]
    
    while candidates:
        r, c= candidates.pop(0)
        
        for offset_r, offset_c in offsets:
            move_r, move_c = r + offset_r, c + offset_c
            if not (move_r, move_c) in distances and maze[move_r, move_c] == ".":
                distances[move_r, move_c] = distances[r, c] + 1
                candidates.append((move_r, move_c))
    
    return max(distances.values())
    

def main():
    h, w = get_next_ints()
    from collections import defaultdict
    maze = defaultdict(str)
    for r in range(h):
        line = get_next_str()
        for c in range(w):
            maze[r,c] = line[c]
    
    results = []
    for r in range(h):
        for c in range(w):
            if maze[r,c] != "#":
                result = solve(maze, r, c)
                results.append(result)
    
    print(max(results))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def BFS(dziecko, listy_znajomosci): 
    do_przejrzenia = [dziecko]
    odleglosc = {dziecko:0}
    nr_przegladanego = 0 
    while nr_przegladanego < len(do_przejrzenia): 
        aktualnie_przegladany = do_przejrzenia[nr_przegladanego]
        for kumpel in listy_znajomosci[aktualnie_przegladany]: 
            if kumpel not in odleglosc: 
                do_przejrzenia.append(kumpel)
                odleglosc[kumpel] = odleglosc[aktualnie_przegladany] + 1 
        nr_przegladanego +=1
    return max(odleglosc.values())

def labirynt(): 
    H, W = wczytaj_liste()
    labirynt = []
    for i in range(H): 
        rzadek = [x for x in (input() + '#')]
        labirynt.append(rzadek)
    labirynt.append(['#']*W)
    lista_krawedzi = []
    for i in range(H):
        for j in range(W):
            if labirynt[i][j] == '.':
                if labirynt[i+1][j] == '.':
                    lista_krawedzi.append(((i,j),(i+1,j)))
                if labirynt[i][j+1] == '.':
                    lista_krawedzi.append(((i,j),(i,j+1)))
    listy_krawedzi = {}
    for x, y in lista_krawedzi:
        listy_krawedzi[x] = []
        listy_krawedzi[y] = []
    for x, y in lista_krawedzi:  
        listy_krawedzi[x].append(y)
        listy_krawedzi[y].append(x)
    maksymalny = 0
    for i in range(H):
        for j in range(W):
            if labirynt[i][j] == '.':
                kandydat = BFS((i,j),listy_krawedzi)
                if kandydat > maksymalny: 
                    maksymalny = kandydat
    print(maksymalny)

labirynt()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
]

def bfs(start):

    visited = [[False] * w for _ in range(h)]
    que = deque([start + (0,)])

    max_cnt = -1
    while que:
        y, x, cnt = que.popleft()
        if 0 <= x < w and 0 <= y < h and maze[y][x] == '.' and not visited[y][x]:
            max_cnt = max(cnt, max_cnt)
            visited[y][x] = cnt + 1
            for dy, dx in directions:
                que.append((y + dy, x + dx, visited[y][x]))
    # print("\n".join([" ".join(map(str, v)) for v in visited]))
    return max_cnt

ans = 0
for sx in range(w):
    for sy in range(h):
        ans = max(ans, bfs((sy, sx)))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)