Problem:


Score : 400 points

Problem Statement

Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.

The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Accepted

Solution code:
from queue import Queue
import itertools
def solve():

    H, W = map(int, input().split())
    S = []
    for i in range(H):
        tmp = list(input())
        S.append(tmp)
    
    dw = (1,0,-1,0)
    dh = (0,1,0,-1)

    comb = itertools.permutations(tuple(range(20)), 2)
    mx = 0

    for c in comb:
        
        startH = c[0]
        startW = c[1]
        if startH >= H or startW >= W or S[startH][startW] == '#':
            continue

        q = Queue()
        cur = P(startH, startW)
        q.put(cur)

        time = [[float('inf')] * W for i in range(H)]
        time[startH][startW] = 0

        while not q.empty():
            p = q.get()
            
            for i in range(4):
                nh = p.H + dh[i]
                nw = p.W + dw[i] 
                if 0 <= nh and nh < H and 0 <= nw and nw < W and time[nh][nw] == float('inf') and S[nh][nw] != '#':
                    q.put(P(nh, nw))
                    time[nh][nw] = time[p.H][p.W] + 1
        
        flatten = list(itertools.chain.from_iterable(time))
        for i in range(len(flatten)):
            if flatten[i] == float('inf'):
                flatten[i] = -1 

        localmx = max(flatten)
        mx = max(localmx, mx)


    print(mx)

class P():
    def __init__(self, H, W):
        self.H = H
        self.W = W

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	global Y
	global X
	global q
	global maps
	global maze

	H,W = inputMap()
	Y = H
	X = W
	mapmap = []
	ser = []
	for i in range(H):
		tmp = input()
		tmp = tmp[:-1]
		mapmap.append(tmp)

		for j,val in enumerate(tmp):
			if val == ".":
				ser.append((i,j))

	maps = [[-1 for _ in range(X)] for _ in range(Y)]
	maze = mapmap
	q = Queue()

	ans = 0
	for i,val in enumerate(ser):
		s,e = val
		tmp = serchs(s,e,s,e)

		for i in maps:
			tmptmp = max(i)
			#print(tmptmp)
			if tmptmp > ans:
				ans = tmptmp

		maps = [[-1 for _ in range(X)] for _ in range(Y)]

	print(ans)

def serchs(start_y,start_x, goal_y,goal_x):
	q.enqueue((start_y, start_x))
	maps[start_y][start_x] = 0
	run()

	return(maps[goal_y][goal_x])

def run():
	while True:
		tmp = q.dequeue()
		if tmp == None:
			return

		y, x = tmp

		counts = maps[y][x] + 1
		if not y <= 0 and maps[y-1][x] == -1 and maze[y-1][x] == ".":
			q.enqueue((y-1, x))
			maps[y-1][x] = counts
		if not x <= 0 and maps[y][x-1] == -1 and maze[y][x-1] == ".":
			q.enqueue((y, x-1))
			maps[y][x-1] = counts
		if not y >= Y-1 and maps[y+1][x] == -1 and maze[y+1][x] == ".":
			q.enqueue((y+1, x))
			maps[y+1][x] = counts
		if not x >= X-1 and maps[y][x+1] == -1 and maze[y][x+1] == ".":
			q.enqueue((y, x+1))
			maps[y][x+1] = counts

class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import deque
import copy

def bfs(graph, sh, sw):
    td = deque([[sh, sw]])
    graph[sh][sw] = "0"
    mx = 0
    while td:
        h, w = td.popleft()
        num = int(graph[h][w])
        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 graph[new_h][new_w] == ".":
                graph[new_h][new_w] = str(num+1)
                if int(graph[new_h][new_w]) > mx:
                    mx = int(graph[new_h][new_w])
                td.append([new_h, new_w])

    return mx

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

ans = []

for i in range(H):
    for j in range(W):
        if ls[i][j] == ".":
            sh = i
            sw = j
            graph = copy.deepcopy(ls)
            ans.append(bfs(graph, sh, sw))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque

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

def solve(x, y):
    offset = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = [[-1] * W for _ in range(H)]
    visited[y][x] = 0
    
    q = deque()
    q.append((x, y))

    while q:
        x, y = q.popleft()

        for u, v in offset:
            if not (0 <= x + u < W) or not (0 <= y + v < H):
                continue

            if visited[y + v][x + u] > -1 or S[y + v][x + u] == "#":
                continue

            visited[y + v][x + u] = visited[y][x] + 1
            q.append((x + u, y + v))
            
    return visited

ans = 0
for y, ss in enumerate(S):
    for x, s in enumerate(ss):
        if s == ".":
            ans = max(ans, max(max(v) for v in solve(x, y)))

print(ans)

Submission status: Accepted

Solution code:
import queue
r,c=map(int,input().split())
#sy,sx=map(int,input().split())
#gy,gx=map(int,input().split())
a=[list(input()) for i in range(r)]
sy,sx = (1,1)
#gy,gx = (2,2)
def minload(sy,sx,a):
    sy-=1
    sx-=1
    #gy-=1
    #gx-=1
    q = queue.Queue()
    d=[(-1,0),(1,0),(0,-1),(0,1)]
    a[sy][sx]=0
    for i in d:
        if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
            a[sy+i[0]][sx+i[1]]=1
            q.put((sy+i[0],sx+i[1]))
    while True:
        if queue.Queue.empty(q):
            break
        y,x=q.get()
        #if y==r and x==c:
            #break
        for i in d:
            if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                a[y+i[0]][x+i[1]]=a[y][x]+1
                q.put((y+i[0],x+i[1]))
    #print(a[gy][gx])
    max = 0
    for i in a:
        for j in i:
            if j != '#' and j !='.':
                if j > max:
                    max = j
    return(max)
ans = 0
for sy in range(1,r+1): 
    for sx in range(1,c+1):
        b = []
        for i in a:
            b.append(list(i))
        if a[sy-1][sx-1]==".":
            local_max = minload(sy,sx,b)
            #print(local_max)
            #print(b)
        else:
            local_max = 0
        if local_max > ans:
            ans = local_max
print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

def warshall_floyd(d, n):
    # pprint(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def solve(h, w, s):
    
    n_node = 0
    nodes = [] 
    # pprint(nodes)
    for y in range(h):
        nodes.append([])
        for x in range(w):
            nodes[y].append(n_node)
            n_node += 1
    edges = [[float("inf") for i in range(n_node)] for j in range(n_node)]
    # pprint(nodes)
    for y in range(h):
        for x in range(w):
            if s[y][x] != ".":
                continue
            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] == ".":
                    edges[nodes[y][x]][nodes[y+dy][x+dx]] = 1
    for i in range(n_node):
        edges[i][i] = 0
    
    dist = warshall_floyd(edges, n_node)
    # pprint(dist)
    ans = -1
    for y in range(n_node):
        for x in range(n_node):
            if dist[y][x] < float("inf"):
                ans = max(ans, dist[y][x])
    print(ans)


if __name__ == '__main__':
    h, w = map(int, sys.stdin.readline().strip().split(" "))
    s = []
    for i in range(h):
        s.append(list(sys.stdin.readline().strip()))
    # debug
    # pprint(s)
    solve(h, w, s)

Submission status: Accepted

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

S = [[True]*(W+2)]
S += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
S.append([True]*(W+2))

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

edge = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]:
            continue
        for d in range(4):
            x = dx[d]
            y = dy[d]
            if (not S[i+y][j+x]) and (not ((i+y-1)*W+(j+x),(i-1)*W+j) in edge):
                edge.append(((i-1)*W+j,(i+y-1)*W+(j+x)))

S = [[float("inf")] * (H*W) for _ in range(H*W)]
for i in range(H*W):
    S[i][i] = 0
for a,b in edge:
    S[a-1][b-1] = 1
    S[b-1][a-1] = 1

from scipy.sparse.csgraph import floyd_warshall
S = floyd_warshall(S)

answer = 0
for i in range(H*W):
    for j in range(i):
        if S[i][j] < float("inf"):
            answer = max(answer, S[i][j])

print(int(answer))

Submission status: Accepted

Solution code:
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


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

fld = [""] * H
for i in range(H):
    fld[i] = input()

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

d = [[float("inf") for i in range(H * W)] for i in range(H * W)]
for i in range(H):
    for j in range(W):
        if fld[i][j] == '#':
            continue
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]
            if x < 0 or x >= H or y < 0 or y >= W:
                continue
            if fld[x][y] == ".":
                d[i*W+j][x*W+y] = 1


for i in range(H*W):
    d[i][i] = 0

warshall = warshall_floyd(d, H*W)
ans = 0
for val in warshall:
    for v in val:
        if v != float("inf"):
            ans = max(ans, v)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(sx,sy):
    if l[sy][sx]=="#":
      return 0
    
    d=[[float("inf")]*w for i in range(h)]
    
    que=deque([])
    que.append((sx,sy))
    d[sy][sx]=0

    while que:
      p = que.popleft()
 
      for i in range(4):
          nx=p[0]+dx[i]
          ny=p[1]+dy[i]

          if 0<=nx<w and 0<=ny<h and l[ny][nx] != "#" and d[ny][nx] == float("inf"):
              que.append((nx,ny))
              d[ny][nx] = d[p[1]][p[0]] + 1
              gx=nx
              gy=ny
 
    return d[gy][gx]

for i in range(h):
  for k in range(w):
    ma = max(ma,bfs(k,i))
    
print(ma)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

def cl(sx, sy, m):
    Z = -1
    dist = [[Z for i in range(w)] for j in range(h)]
    for i in range(h):
        for j in range(w):
            if m[i][j] == '#':
                dist[i][j] = -1

    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dist[sy][sx] = 0
        while len(q):
            x, y = q.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx < w and 0 <= ny < h and m[ny][nx] != '#' and dist[ny][nx] == Z):
                    q.insert(0, (nx, ny))
                    dist[ny][nx] = dist[y][x] + 1
        return dist
    return bfs()

S = [list(input()) for _ in range(h)]
ans = 0
for y in range(h):
    for x in range(w):
        e = S[y][x]
        if e != '#':
            num = cl(x, y, S)
            for k in range(h):
                ans = max(ans, max(num[k]))
print(ans)

Submission status: Accepted

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


def dfs(start_h,start_w):
    q=deque()
    maze_copy=copy.deepcopy(maze)
    walk_count=[[0 for _ in range(w)] for _ in range(h)]
    q.append([start_h,start_w])
    maze_copy[start_h][start_w]="#"
    max_count=0
    while(len(q)!=0):
        position=q.popleft()
        now_h=position[0]
        now_w=position[1]
        now_count=walk_count[now_h][now_w]
        if(now_h>0 and maze_copy[now_h-1][now_w]=='.'):
            walk_count[now_h-1][now_w]=now_count+1
            maze_copy[now_h-1][now_w]="#"
            q.append([now_h-1,now_w])
            if(max_count<now_count+1):
                max_count=now_count+1

        if(now_h<h-1 and maze_copy[now_h+1][now_w]=='.'):
            walk_count[now_h+1][now_w]=now_count+1
            maze_copy[now_h+1][now_w]="#"
            q.append([now_h+1,now_w])
            if(max_count<now_count+1):
                max_count=now_count+1

        if(now_w>0 and maze_copy[now_h][now_w-1]=='.'):
            walk_count[now_h][now_w-1]=now_count+1
            maze_copy[now_h][now_w-1]="#"
            q.append([now_h,now_w-1])
            if(max_count<now_count+1):
                max_count=now_count+1

        if(now_w<w-1 and maze_copy[now_h][now_w+1]=='.'):
            walk_count[now_h][now_w+1]=now_count+1
            maze_copy[now_h][now_w+1]="#"
            q.append([now_h,now_w+1])
            if(max_count<now_count+1):
                max_count=now_count+1
    return max_count

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

Submission status: Accepted

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

input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
m = [['#' for _ in range(w+2)] for _ in range(h+2)]
hs = []
ws = []
for hi in range(1, h+1):
    for wi, s in enumerate(input().strip(), start=1):
        m[hi][wi] = s
        if s == '.':
            hs.append(hi)
            ws.append(wi)

def bfs(hs, ws, m):
    cost = 0
    q = deque([])
    m[hs][ws] = '#'
    for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
        if m[hs+offset[0]][ws+offset[1]] == '.':
            q.append((hs+offset[0], ws+offset[1]))
    while q:
        cost += 1
        q_ = deque(q)
        q = deque([])
        for h, w in q_:
            m[h][w] = '#'
            for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
                if m[h+offset[0]][w+offset[1]] == '.':
                    m[h+offset[0]][w+offset[1]] = '#'
                    q.append((h+offset[0], w+offset[1]))

    return cost, h, w

maxi = -1
for hss, wss in zip(hs, ws):
    maxi_, hh, ww = bfs(hss, wss, deepcopy(m[:]))
    maxi = max(maxi, maxi_)

print(maxi)

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+1][j] == 1:
            #if W*(i+1)+j ==1:
                #print("a")
            #G[W*(i+1)+j].append(W*i+j)
            G[W*i+j].append(W*(i+1)+j)

        if i>=1:
            if A[i-1][j] == 1:
                #if W*(i-1)+j ==1:
                    #print("b")
                #G[W*(i-1)+j].append(W*i+j)
                G[W*i+j].append(W*(i-1)+j)            
            
        
        if A[i][j+1] == 1:
            #if W* ==1:
                #print("c")
            #G[W*i+(j+1)].append(W*i+j)
            G[W*i+j].append(W*i+(j+1))
        
        if j>=1:
            if A[i][j-1] == 1:
                #if W*(i+1)+j ==1:
                    #print("d")
                #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

#print(G)

for i in range(N):
    #print(i)
    I = i//W
    J = i%W
    #print(I,J)
    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))

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
p = [(0,1),(1,0),(-1,0),(0,-1)]
mx = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            start = (i,j)
            n1 ={start}
            corse = {}
            corse[start]=1
            cnt = 1
            while n1 != set():
                n2 = set()
                for k in n1:
                    for l in p:
                        nk = (k[0]+l[0],k[1]+l[1])
                        if 0<=nk[0]<h and 0<=nk[1]<w:
                         if s[nk[0]][nk[1]] != '#' and corse.get(nk) == None:
                            corse[nk] = 1
                            mx = max(cnt,mx)
                            n2.add(nk)
                cnt += 1
                n1 = n2
print(mx)

Submission status: Accepted

Solution code:
#D幅優先探索
from collections import deque
h, w = list(map(int,input().split()))

def bfs(que,c):
    while que:
        c += 1
        qq = que
        que = deque([])
        while qq:
            x, y = qq.popleft()
            field[x][y] = "#"
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
        
                if 0 <= nx <= h-1 and 0 <= ny <= w-1 and field[nx][ny] == ".":
                    if (nx,ny) not in que:
                        que.append((nx,ny))
            
    return c-1
            
A = [list(input()) for _ in range(h)]



dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque([]) 
ans = []

for p in range(h):
    for q in range(w):
        if A[p][q] == ".":
            field = [k[:] for k in A]
            
            que.append((p,q))
            ans.append(bfs(que,0))
print(max(ans))

Submission status: Accepted

Solution code:
def main():

    from collections import deque
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    cost = [[600] * w for _ in range(h)]
    nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    ans = 0

    def bfs(sx, sy):
        q = deque([(sx, sy)])
        cost[sx][sy] = 0
        value = 0
        while q:
            x, y = q.popleft()
            for dx, dy in nb:
                nx = x + dx
                ny = y + dy
                if 0 <= nx and nx < h and 0 <= ny and ny < w and s[nx][ny] == "." and cost[nx][ny] == 600:
                    q.append((nx, ny))
                    cost[nx][ny] = cost[x][y] + 1
                    value = max(value, cost[nx][ny])
        return value

    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                cost = [[600] * w for _ in range(h)]
                tmp = bfs(i, j)
                ans = max(tmp, ans)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

def cl(sx, sy, m):
    Z = -1
    x_len = len(m[0])
    y_len = len(m)
    dist = [[Z for i in range(x_len)]
                for j in range(y_len)]
    for i in range(y_len):
        for j in range(x_len):
            if m[i][j] == '#':
                dist[i][j] = -1

    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dist[sy][sx] = 0
        while len(q):
            x, y = q.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx < x_len and 0 <= ny < y_len and m[ny][nx] != '#' and dist[ny][nx] == Z):
                    q.insert(0, (nx, ny))
                    dist[ny][nx] = dist[y][x] + 1
        
        return dist
    return bfs()

S = [list(input()) for _ in range(h)]
ans = 0
for y in range(h):
    for x in range(w):
        start = S[y][x]
        if start != '#':
            num = cl(x, y, S)
            for k in range(h):
                ans = max(ans, max(num[k]))
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
max_step = 0

for h_i in range(h):
  for w_i in range(w):
    grid = [[-1]*w for _ in range(h)]
    
    if maze[h_i][w_i] == '.':
      grid[h_i][w_i] = 0
      loc = [[h_i,w_i]]
      
      for k in range(1, h*w):
        next_loc = []
        for y,x in loc:
          for i,j in ([1,0], [-1,0], [0,1], [0,-1]):
            next_h = y+i
            next_w = x+j
            
            if 0 <= next_h < h and 0 <= next_w < w and maze[next_h][next_w] == '.' and grid[next_h][next_w]==-1: 
              grid[next_h][next_w] = k
              next_loc.append([next_h, next_w])
        loc=next_loc
      # print(grid)
      temp_max_step = max(max(grid_w) for grid_w in grid)
      max_step = max(max_step, temp_max_step)
      
print(max_step)

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    H, W = map(int, input().split())
    S = stdin.read().splitlines()

    maze = ['#' * (W + 2)]
    for s in S:
        maze.append('#' + s + '#')
    maze.append('#' * (W + 2))

    def func(sx, sy):
        c1 = deque([(sx, sy)])
        c2 = [[None for _ in range(W + 1)] for _ in range(H + 1)]
        c2[sx][sy] = 0
        ret = 0
        while c1:
            x, y = c1.popleft()
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                if '.' in maze[x+i][y+j] and c2[x+i][y+j] is None:
                    c1.append((x+i, y+j))
                    c2[x+i][y+j] = c2[x][y] + 1
                    ret = max(ret, c2[x+i][y+j])
        return ret

    ans = 0
    for i, a in enumerate(maze[1:-1], start=1):
        for j, b in enumerate(a[1:-1], start=1):
            if b == '.':
                ans = max(ans, func(i, j))
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import deque


def solve(h, w, s_list):

    g = dict()
    for i in range(h):
        for j in range(w):
            if s_list[i][j] == ".":
                g[i * 100 + j] = dict()

    for i in range(h):
        for j in range(w - 1):
            if s_list[i][j] == "." and s_list[i][j + 1] == ".":
                g[i * 100 + j][i * 100 + j + 1] = 1
                g[i * 100 + j + 1][i * 100 + j] = 1

    for i in range(h - 1):
        for j in range(w):
            if s_list[i][j] == "." and s_list[i + 1][j] == ".":
                g[i * 100 + j][i * 100 + j + 100] = 1
                g[i * 100 + j + 100][i * 100 + j] = 1

    d_max = 0
    for x in g.keys():
        d_dict = {v: 10000 for v in g.keys()}
        queue = deque([x])
        d_dict[x] = 0
        while len(queue) > 0:
            p = queue.popleft()
            for q in g[p].keys():
                if d_dict[q] > d_dict[p] + 1:
                    d_dict[q] = d_dict[p] + 1
                    queue.append(q)
        d_max = max(d_max, max(d_dict.values()))

    return d_max


def main():
    h, w = map(int, input().split())
    s_list = []
    for _ in range(h):
        s = input()
        s_list.append(s)
    res = solve(h, w, s_list)
    print(res)


def test():
    assert solve(3, 3, ["...", "...", "..."]) == 4
    assert solve(3, 5, ["...#.", ".#.#.", ".#..."]) == 10


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
s = ["#"*(W+2)] + ["#" + input() + "#" for _ in range(H)] + ["#"*(W+2)]
DH, DW = [0, 0, 1, -1], [1, -1, 0, 0]

def bfs(start):
	que = deque([start])
	dist = [[-1 for _ in range(W+2)] for _ in range(H+2)]
	dist[start[0]][start[1]] = 0
	num = 0

	while que:

		label = que.pop()
		h, w = label[0], label[1]
		
		for dh, dw in zip(DH, DW):
			hh, ww = h+dh, w+dw
			if s[hh][ww] == "." and dist[hh][ww] < 0:
				que.appendleft((hh, ww))
				dist[hh][ww] = dist[h][w] + 1
				num = max(num, dist[hh][ww])

	return num

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

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10**7)

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

S = list('#' * (W + 2))
for _ in range(H):
    S.extend('#')
    S.extend(list(input()))
    S.extend('#')
S.extend(list('#' * (W + 2)))

dxs = [-1, 1, -(W + 2), W + 2]
sx, sy = 0, 0


def f(s):
    dist = [-1] * len(S)
    # s = sx * W + sy
    # print('s', s)
    if S[s] == '#':
        return -1
    q = [s]
    dist[s] = 0
    while q:
        qq = []
        for x, dx in itertools.product(q, dxs):
            y = x + dx
            if S[y] == '#':
                continue
            if dist[y] != -1:
                continue
            dist[y] = dist[x] + 1
            qq.append(y)
        q = qq
    return max(dist)


ans = 0
for i in range(len(S)):
    v = f(i)
    if ans < v:
        ans = v
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path

H, W = map(int, input().split())
m = []
for i in range(H):
  s = input()
  z = []
  for x in s:
    if x == '.':
      z.append(0)
    if x == '#':
      z.append(1)
  m.append(z)
m = np.array(m)

graph = np.array([[0] * (H * W) for _ in range(H * W)])
for i in range(H):
  for j in range(W):
    if m[i][j] == 0:
      if i-1 >= 0:
        if m[i-1][j] == 0:
          graph[W * i + j][W * (i-1) + j] = 1
      if i+1 <= H-1:
        if m[i+1][j] == 0:
          graph[W * i + j][W * (i+1) + j] = 1
      if j-1 >= 0:
        if m[i][j-1] == 0:
          graph[W * i + j][W * i + (j-1)] = 1
      if j+1 <= W-1:
        if m[i][j+1] == 0:
          graph[W * i + j][W * i + (j+1)] = 1

a = shortest_path(graph)
print(int(np.nanmax(a[a != np.inf])))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


h, w = LI()
maze = SRL(h)


def solve(sy, sx):
    min_cost = deepcopy(maze)
    min_cost[sy][sx] = 0
    que = deque([(sy, sx)])
    max_c = 0
    while que:
        cy, cx = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny = cy + i
            nx = cx + j
            if 0 <= ny < h and 0 <= nx < w:
                if min_cost[ny][nx] == '.':
                    min_cost[ny][nx] = min_cost[cy][cx] + 1
                    que += [(ny, nx)]
                    max_c = max(max_c, min_cost[ny][nx])
    return max_c



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


print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
C = [['#' for j in range(W + 2)] for i in range(H + 2)]

for i in range(H):
    s = input()
    for j in range(W):
        C[i + 1][j + 1] = s[j]
ans = 0

for sy in range(1, H + 1):
    for sx in range(1, W + 1):

        q = deque()
        q.append((sy, sx, 0))
        S = set([])
        while len(q) > 0:
            t = q.popleft()
            y, x, d = t[0], t[1], t[2]
            ans = max(d, ans)
            if C[y][x] == '#':
                continue
            if (y, x) in S:
                continue
            else:
                S.add((y, x))

            q.append((y + 1, x , d + 1))
            q.append((y - 1, x, d + 1))
            q.append((y, x + 1, d + 1))
            q.append((y, x - 1, d + 1))




print(ans - 1)