Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s

    ma = 0

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

    for sj in range(H):
        for si in range(W):
            if A[sj][si] == "#":
                continue
            d = [[-1 for i in range(W)] for j in range(H)]
            q = deque([])
            q.append((sj, si))
            d[sj][si] = 0

            while q:
                p = q.popleft()
                for i in range(4):
                    nj = p[0] + dj[i]
                    ni = p[1] + di[i]

                    if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "#" and d[nj][ni] == -1:
                        q.append((nj, ni))
                        d[nj][ni] = d[p[0]][p[1]] + 1

            for gj in range(H):
                for gi in range(W):
                    ma = max(ma, d[gj][gi])

    print(ma)





    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H,W = [int(n) for n in input().split()]
    grid = [[0 if n=="." else 1 for n in input()] for _ in range(H)]
    INF = 10**10
    graph = [[INF]*H*W for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == 0:
                graph[i*W+j][i*W+j]=0
                if i<H-1 and grid[i+1][j]==0:
                    graph[i*W+j][(i+1)*W+(j)] = 1
                    graph[(i+1)*W+(j)][i*W+j] = 1
                if j>0 and grid[i][j-1] == 0:
                    graph[i*W+j][(i)*W+j-1] = 1
                    graph[(i)*W+j-1][i*W+j] = 1
                if j<W-1 and grid[i][j+1] == 0:
                    graph[i*W+j][(i)*W+(j+1)] = 1
                    graph[(i)*W+(j+1)][i*W+j] = 1
                if i>0 and grid[i-1][j] == 0:
                    graph[i*W+j][(i-1)*W+(j)] = 1
                    graph[(i-1)*W+(j)][i*W+j] = 1
    
    
    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    # for i in range(H*W):
    #     for j in range(W*H):
    #         print(graph[i][j], end="\t")
    #     print()
    m = 0
    for i in range(H*W):
        for j in range(H*W):
            if graph[i][j] == INF:
                continue
            m = max(m,graph[i][j])
    print(m)
main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ans = 0
s = []
a = []
q = []
for i in range(h):
    s.append(input())


for yy in range(h):
    for xx in range(w):
        a = []
        for i in range(h):
            a.append([0] * w)

        d = 1
        q = [(xx, yy)]
        while True:
            nq = []
            while len(q) > 0:
                p = q.pop()
                x, y = p
                if x < 0 or x >= w or y < 0 or y >= h:
                    continue
                if s[y][x] == '#':
                    continue
                if a[y][x] > 0:
                    continue
                a[y][x] = d
                nq.append((x - 1, y))
                nq.append((x + 1, y))
                nq.append((x, y - 1))
                nq.append((x, y + 1))
            if len(nq) == 0:
                break
            q = nq
            d += 1

        b = []
        for i in range(h):
            b.extend(a[i])
        b = sorted(b, reverse=True)
        ans = max(ans, b[0])
print(ans - 1)

Submission status: Accepted

Solution code:
import numpy as np

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

maze = np.ones((h + 2, w + 2), dtype=np.int)

for i in range(1, h + 1):
    row = input().strip()
    for j in range(1, w + 1):
        maze[i, j] = 0 if row[j - 1] == '.' else 1


def bfs(maze, si, sj):
    assert maze[si, sj] == 0
    infty = -1
    distances = np.full((h + 2, w + 2), infty, dtype=np.int)
    queue = []
    queue.append((si, sj))
    distances[si, sj] = 0
    while len(queue) > 0:
        ci, cj = queue.pop(0)
        d = distances[ci, cj]
        left = (ci, cj - 1)
        right = (ci, cj + 1)
        up = (ci - 1, cj)
        down = (ci + 1, cj)
        nexts = [left, right, up, down]
        for ni, nj in nexts:
            if not (1 <= ni and ni <= h \
               and 1 <= nj and nj <= w):
                continue
            if distances[ni, nj] != infty:
                continue
            if maze[ni, nj] == 1:
                continue
            distances[ni, nj] = d + 1
            queue.append((ni, nj))

    return distances


max_dist = 0
for si in range(1, h + 1):
    for sj in range(1, w + 1):
        if maze[si, sj] == 0:
            distances = bfs(maze, si, sj)
            mx = np.max(distances)
            max_dist = max(max_dist, mx)

print(max_dist)

Submission status: Accepted

Solution code:
from queue import Queue
INF = float("inf")
R, C = map(int,input().split())
M = [input() for k in range(R)]
ans = 0
for k in range(C):
    for l in range(R):
        if M[l][k] == ".":
            D = [[INF for k in range(C)] for l in range(R)]
            sx, sy = l, k
            Q = Queue()
            Q.put([sx,sy])
            D[sx][sy] = 0
            dx = [1,0,-1,0]
            dy = [0,1,0,-1]
            while not Q.empty():
                t = Q.get()
                x = t[0]
                y = t[1]
                for d in range(4):
                    if 0 <= x + dx[d] < R and 0 <= y + dy[d] < C:
                        if M[x+dx[d]][y+dy[d]] == "." and D[x+dx[d]][y+dy[d]] > D[x][y]+1:
                            D[x+dx[d]][y+dy[d]] = D[x][y]+1
                            Q.put([x+dx[d],y+dy[d]])
            for p in range(C):
                for q in range(R):
                    if D[q][p] != float("inf"):
                        ans = max(ans,D[q][p])
print(ans)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter,mul
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left,bisect_right
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache,reduce
#from math import factorial
#import sys
#from fractions import gcd
setrecursionlimit(10**6)
input=stdin.readline
def m(t):
    r=0
    for i in t:
        r=max(r,max(i))
    return r

h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
ans=0
rf=range(4)
rh=range(h)
rw=range(w)
for sy in rh:
    for sx in rw:
        if s[sy][sx]=="#":
            continue
        dis=[[-1]*w for _ in rh]
        dis[sy][sx]=0
        q=deque([(sy,sx)])
        while len(q)>0:
            y,x=q.popleft()
            for i in rf:
                ny=y+dy[i]
                nx=x+dx[i]
                if ny<0 or nx<0 or ny==h or nx==w:
                    continue
                if s[ny][nx]=="#":
                    continue
                if dis[ny][nx]==-1:
                    dis[ny][nx]=dis[y][x]+1
                    q.append((ny,nx))
        ans=max(ans,m(dis))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def main():
    def dijkstra_search(s):
        d = [INF] * size
        searched = [False] * size
        d[s] = 0
        searched[s] = True
        edge_list = []
        count = 1
        for i in edge[s]:
            heappush(edge_list,i)
        while edge_list:
            min_d,min_v = heappop(edge_list)
            if searched[min_v] or min_d > d[min_v]:
                continue
            v = min_v
            d[v] = min_d
            searched[v] = True
            count += 1
            for i,j in edge[v]:
                next_d = i+d[v]
                if not searched[j]:
                    heappush(edge_list,(next_d,j))
            if count == size:
                break
        return d
    def judge(a,b):
        if a >= 0 and a < h and b >= 0 and b < w and s[a][b] == ".":
            return True
        else:
            return False
    h,w = map(int,input().split())
    s = [list(input()) for _ in range(h)]
    size = h*w
    INF = float('inf')
    edge = [[] for _ in range(size)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                if judge(i+1,j):
                    edge[i*w+j].append((1,((i+1)*w+j)))
                if judge(i-1,j):
                    edge[i*w+j].append((1,((i-1)*w+j)))
                if judge(i,j+1):
                    edge[i*w+j].append((1,(i*w+(j+1))))
                if judge(i,j-1):
                    edge[i*w+j].append((1,(i*w+(j-1))))
    ans = []
    for i in range(size):
        if s[i//w][i%w-1] == ".":
            d_list = dijkstra_search(i)
            for j in d_list:
                if not j == INF:
                    ans.append(j)
    print(max(ans))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
from scipy.sparse.csgraph import shortest_path

H, W = list(map(int, input().split()))
s_table = []
node_index = 0

for _ in range(H):
    s_list = list(input())
    s_table.append(s_list)

adj = [[0] * (W * H) for _ in range(W * H)]
node_index = -1
for h_i, s_list in enumerate(s_table):
    for w_i, s in enumerate(s_list):
        node_index += 1
        if s == "#":
            continue
        if w_i + 1 < W:
            # 右隣と隣接しているか
            if s_list[w_i + 1] == ".":
                adj[node_index][node_index + 1] = 1
                adj[node_index + 1][node_index] = 1
        if h_i + 1 < H:
            # 下と隣接しているか
            if s_table[h_i + 1][w_i] == ".":
                adj[node_index][(h_i + 1) * W + w_i] = 1
                adj[(h_i + 1) * W + w_i][node_index] = 1

adj = np.array(adj)
d_matrix = shortest_path(adj)

d_matrix[d_matrix == float("inf")] = -1
ans = int(d_matrix.max())
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=-1
s=[]
for i in range(h):
	ss=input()
	s.append(ss)
from collections import deque as dq
for i in range(h):
	for j in range(w):
		if s[i][j]=="#":
			continue
		dis=[[10**3 for _ in range(w)]for _ in range(h)]
		dis[i][j]=0
		queue=dq([[i,j]])
		while queue:
			r=queue.popleft()
			if r[0]+1<h:
				if s[r[0]+1][r[1]]=="." and dis[r[0]+1][r[1]]==10**3:
					queue.append([r[0]+1,r[1]])
					dis[r[0]+1][r[1]]=dis[r[0]][r[1]]+1
			if r[0]-1>=0:
				if s[r[0]-1][r[1]]=="." and dis[r[0]-1][r[1]]==10**3:
					queue.append([r[0]-1,r[1]])
					dis[r[0]-1][r[1]]=dis[r[0]][r[1]]+1
			if r[1]+1<w:
				if s[r[0]][r[1]+1]=="." and dis[r[0]][r[1]+1]==10**3:
					queue.append([r[0],r[1]+1])
					dis[r[0]][r[1]+1]=dis[r[0]][r[1]]+1
			if r[1]-1>=0:
				if s[r[0]][r[1]-1]=="." and dis[r[0]][r[1]-1]==10**3:
					queue.append([r[0],r[1]-1])
					dis[r[0]][r[1]-1]=dis[r[0]][r[1]]+1
		for k in range(h):
			for l in range(w):
				if dis[k][l]!=10**3:
					ans=max(ans,dis[k][l])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product
from copy import deepcopy

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

sls = list(product(range(h),range(w)))
ans = 0
move = [[0,1], [1,0],[0,-1], [-1,0]]
for s in sls:
    if ls[s[0]][s[1]] == '#':
        continue
    else:
        lss = deepcopy(ls)
        d=deque()
        d.append(s)
        lss[s[0]][s[1]] = 0
        while d:
            x,y = d.popleft()
            c = lss[x][y]
            for dx,dy in move:
                if 0<=x+dx<h and 0<=y+dy<w and lss[x+dx][y+dy] == '.' :
                    lss[x+dx][y+dy] = c+1
                    d.append([x+dx, y+dy])
                    

        dist = 0
        for i in range(h):
            for j in range(w):
                if type(lss[i][j]) is int:
                    dist = max(dist, lss[i][j])

        ans = max(ans, dist)

print(ans)

Submission status: Accepted

Solution code:
h, w = [int(i) for i in input().split()]

s = [input() for _ in range(h)]

def search(s_h, s_w):
    stack = []
    isuse = [[False] * w for _ in range(h)]
    def add(a, b,score):
        nonlocal stack, isuse
        if not (0 <= a < h and 0 <= b < w):
            return 0
        if s[a][b] == "#":
            return 0
        if isuse[a][b]:
            return 0
        isuse[a][b] = True
        stack.append((a,b,score+1))
        
    add(s_h, s_w, -1)
    c=0
    while stack:
        a,b,c = stack.pop(0)
        add(a + 1, b, c)
        add(a , b + 1, c)
        add(a, b - 1, c)
        add(a - 1, b, c)
    return c

search(0,0)

ans = 0
for s_h in range(h):
    for s_w in range(w):
        ans = max(search(s_h, s_w), ans)
        #print(s_h,s_w,search(s_h, s_w))
print(ans)

Submission status: Accepted

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


def f(S, H, W, y, x):
    if S[y][x] == '#':
        return 0
        
    C = [-1]*(H*W)
    C[y*W + x] = 0
    Q = [(y, x)]

    while len(Q) > 0:
        Q2 = []
        for y2, x2 in Q:
            c = C[y2*W + x2]

            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                y3 = y2 + dy
                x3 = x2 + dx

                if (y3 >= 0 and y3 < H and x3 >= 0 and x3 < W and
                    S[y3][x3] == '.' and C[y3*W + x3] == -1):

                    C[y3*W + x3] = c + 1
                    Q2.append((y3, x3))

        Q = Q2

    return max(C)
                

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

    print(max(f(S, H, W, y, x) for y in range(H) for x in range(W)))
        


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

class BreadthFirstSearch:
    def __init__(self, h, w, start_xy, board):
        self.h, self.w = h, w
        (self.sx, self.sy) = start_xy
        self.board = board
        self.hist = [[False] * w for i in range(h)]

    def get_step(self, wall="#"):
        '''
        区切り文字を指定する(デフォルトは#)
        ゴールに着くまでの最短距離を出力
        ゴールにたどり着かない場合は0を出力
        '''
        q = queue.Queue()
        q.put((self.sx, self.sy))
        self.hist[self.sy][self.sx] = True
        step = 0
        count = 1
        next_count = 1
        ans = 0
        # キューが空になるまで
        while not q.empty():
            x, y = q.get()
            count -= 1
            if count == 0:
                step += 1
                count = next_count
                next_count = 0
            # ゴールにたどり着くまでのステップ
            for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                # 範囲内か
                if not(0 <= x+i <= w - 1) or not(0 <= y+j <= h - 1):
                    continue
                # 壁では無いか
                if self.board[y+j][x+i] == wall:
                    continue
                # 既に通ったところか
                if self.hist[y+j][x+i]:
                    continue
                # 通った印をつける
                self.hist[y+j][x+i] = True
                q.put((x+i, y+j))
                next_count += 1
        return step


# 図の形
h, w = map(int, input().split())
# ボードの読み込み
board = [[i for i in list(str(input()))] for i in range(h)]
# スタート地点
ans_ = []
for s_i in range(h):
    for s_j in range(w):
        if board[s_i][s_j] == "#":
            continue
        s_xy = (s_j, s_i)
        bfs = BreadthFirstSearch(h, w, s_xy, board[:])
        ans = bfs.get_step()
        ans_.append(ans)
print(max(ans_) - 1)

Submission status: Accepted

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

def search(sh,sw):

    if S[sh][sw] == "#":
        return -1
    ans = 0
    queue = [(sh,sw)]
    M = [[0]*(W + 2) for _ in range(H+2)]
    M[sh][sw] =  1

    while len(queue) > 0:
        h,w = queue.pop(0)
        if S[h + 1][w] == "." and M[h + 1][w] == 0:
            queue.append((h+1,w))
            M[h+1][w] = M[h][w] + 1
        if S[h - 1][w] == "." and M[h - 1][w] == 0:
            queue.append((h-1,w))
            M[h-1][w] = M[h][w] + 1
        if S[h][w + 1] == "." and M[h][w + 1] == 0:
            queue.append((h,w+1))
            M[h][w+1] = M[h][w] + 1
        if S[h][w - 1] == "." and M[h][w - 1] == 0:
            queue.append((h,w-1))
            M[h][w-1] = M[h][w] + 1
        
    for mm in M:
        ans = max(ans,max(mm))
    return ans-1


def main():
    ans = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            ans = max( ans, search(i,j) )
    print(ans)
    return 


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 単純にbfsによる探索を行う
# 入力、初期設定など
H, W = map(int,input().split())
maze = list(list(input()) for _ in range(H))
INF = -1
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]



def bfs():
    while queue:
        now_row,now_column = queue.pop(0)

        # 上下左右を探索
        # 探索結果が迷路内かつ訪れていないかつ壁でなければvisitedを更新し、そのマスをqueueに追加(いわゆるbfs)
        for i in range(4):
            next_row, next_column = now_row + dy[i] , now_column + dx[i]
            if 0 <= next_row < H and 0 <= next_column < W and \
                    maze[next_row][next_column] != "#" and visited[next_row][next_column] == INF:
                visited[next_row][next_column] = visited[now_row][now_column] + 1
                queue.append([next_row,next_column])


ans = 0
for column in range(W):
    for row in range(H):
        if maze[row][column] == "#":
            continue
        # dequeが使えるかわからないのでリストで代用
        queue = [[row, column]]
        # visitedにはスタートから最短何マスかかるか格納
        visited = [[INF] * W for _ in range(H)]
        visited[row][column] = 0
        bfs()
        tmp_max = 0
        for i in range(H):
            if tmp_max < max(visited[i]):
                tmp_max = max(visited[i])
        if tmp_max > ans:
            ans = tmp_max
print(ans)

Submission status: Accepted

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

def dfs(maze,visited, sh, sw):
    a = 0
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        #print(visited)
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #4近傍について探索
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W: #リスト外でないならelif条件へ
                continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == 0: #行ったことがないかつ、壁でないなら
                visited[new_h][new_w] = visited[h][w]+1
                stack.append([new_h, new_w])
    a = 0
    for s in range(H):
        for x in range(W):
            a = max(a,visited[s][x])
    return a

ans = 0

for i in range(H):
    for q in range(W):
        visited = [[0]*W for _ in range(H)]
        if lst1[i][q] == ".":
            ans = max(ans,dfs(lst1,visited,i,q))
print(ans-1)

Submission status: Accepted

Solution code:
map_height,map_width=map(int,input().split())
d={'.':0,'#':-1}
map_data= [list(map(lambda x: d[x],list(input()))) for _ in range(map_height)]

import itertools
Z= map_width*map_height

#m = np.ones((map_width*map_height,map_width*map_height))*float("inf")
m = [[401 for _ in range(Z)] for _ in range(Z)]
for i,j in itertools.product(range(map_height),range(map_width)):
    if map_data[i][j] == 0:
        for i_n, j_n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 0 <= i_n < map_height and 0 <= j_n < map_width:
                if map_data[i_n][j_n] == 0:
                    m[map_width*i+j][map_width*i_n+j_n] = 1
for i in range(Z):
    m[i][i]=0
for k in range(Z):
    for i in range(Z):
        for j in range(Z):
            temp = min(m[i][j],m[i][k] + m[k][j])
            m[i][j] = temp
                
ans = 0
for i in range(Z):
    for j in range(Z):
        temp = m[i][j]
        if temp != 401:
            if ans < m[i][j]:
                ans = m[i][j]
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque

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

    s = [input() for _ in range(h)]

    drdc = (1, 0), (-1, 0), (0, 1), (0, -1)

    ret = -1
    for r in range(h):
        for c in range(w):
            if s[r][c] == '.':
                dist = [[-1] * w for _ in range(h)]
                dist[r][c] = 0

                q = deque()
                q.append((r, c, 0))

                md = -1
                while q:
                    qr, qc, d = q.popleft()
                    for dr, dc in drdc:
                        nr = qr + dr
                        if nr < 0 or h <= nr:
                            continue
                        nc = qc + dc
                        if nc < 0 or w <= nc:
                            continue
                        if s[nr][nc] == '#':
                            continue
                        if dist[nr][nc] != -1:
                            continue
                        nd = d + 1
                        dist[nr][nc] = nd
                        if md < nd:
                            md = nd

                        q.append((nr, nc, nd))

                ret = max(ret, md)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#%%
def dfs_deep_measure(st, h, w, reach):
    #木の深さを、各ノードに対して求める。
    deep = [[500] * w for _ in range(h)]
    check = [[0] * w for _ in range(h)]
    stack = [st]
    st_i, st_j = st[0], st[1]
    check[st_i][st_j] = 1
    deep[st_i][st_j] = 0
    while len(stack) > 0:
        tmp = stack.pop(0)
        tmp_i, tmp_j = tmp[0], tmp[1]
        tmp_list = reach[tmp_i][tmp_j]
        for i in range(len(tmp_list)):
            t_i, t_j = tmp_list[i][0], tmp_list[i][1]
            if check[t_i][t_j] != 1:
                stack.append((t_i, t_j))
                check[t_i][t_j] = 1
                for j in range(len(reach[t_i][t_j])):
                    ii = (reach[t_i][t_j])[j][0]
                    jj = (reach[t_i][t_j])[j][1]
                    deep[t_i][t_j] = min(deep[ii][jj]+1, deep[t_i][t_j])
    return deep


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

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
reach = [[[] for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        for k in range(len(move)):
            if s[i][j] == '#':
                pass
            else:
                x = i + move[k][0]
                y = j + move[k][1]
                if 0 <= x <= h-1 and 0 <= y <= w-1:
                    if s[x][y] == '.':
                        reach[i][j].append((x, y))




ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            pass
        else:
            tmp_deep = dfs_deep_measure((i, j), h, w, reach)
            #print(tmp_deep)
            #print(tmp_deep)
            for k in range(h):
                for l in range(w):
                    if tmp_deep[k][l] != 500:
                        ans = max(ans, tmp_deep[k][l])


print(ans)

Submission status: Accepted

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

G = [[] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if sl[i][j] == "#":
            continue
        a = i*w + j
        if j != w - 1:
            if sl[i][j+1] != "#":
                b = i*w + j + 1
                G[a].append(b)
        if j != 0:
            if sl[i][j-1] != "#":
                b = i*w + j - 1
                G[a].append(b)
        if i != 0:
            if sl[i-1][j] != "#":
                b = i*w + j - w
                G[a].append(b)
        if i != h - 1:
            if sl[i+1][j] != "#":
                b = i*w + j + w
                G[a].append(b)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

ans = 0
from collections import deque
for i in range(h*w):
    if sl[i//w][i%w] == "#":
        continue
    dist = [-1]*(w*h)
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for p in G[v]:
            if dist[p] > -1:
                continue
            dist[p] = d + 1
            que.append(p)
    ans = max(ans, max(dist))
    
print(ans)

Submission status: Accepted

Solution code:
import copy
import itertools
from collections import deque
INF = float('inf')
ROAD = '.'
WALL = '#'
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def main():
    H, W = map(int, input().split())
    
    # 迷路の初期化
    initial_maze = [None] * H

    # 迷路の読み込み
    for i in range(H):
        initial_maze[i] = list(input())
        for j in range(W):
            if initial_maze[i][j] == ROAD:
                initial_maze[i][j] = INF
    
    ans = 0
    for sy, sx in itertools.product(range(H), range(W)):
        if initial_maze[sy][sx] == WALL:
            continue

        maze = copy.deepcopy(initial_maze)
        maze[sy][sx] = 0
        que = deque([[sy, sx]])

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

            for (i, j) in STEPS:
                ny, nx = y+i, x+j
                if ny < 0 or ny >= H or nx < 0 or nx >= W:
                    continue

                target = maze[ny][nx]
                if target != WALL:
                    if target > maze[y][x]+1:
                        maze[ny][nx] = maze[y][x] + 1
                        if maze[ny][nx] > ans:
                            ans = maze[ny][nx]
                        que.append([ny,nx])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(p):
    q = deque()
    q.append((p[0], p[1], 0))
    dis = 0
    path[p[0]][p[1]] = 0
    while len(q):
        x, y, s = q.popleft()
        dis = max(dis, s)  
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and path[nx][ny] > s + 1 and maze[nx][ny] == '.':
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    return dis

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

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            path = [[1000] * W for _ in range(H)]
            ans = max(ans, bfs((i, j)))

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

ans = 0
for h in range(H):
    for w in range(W):
        visited = [[False] * W for _ in range(H)]
        queue = [(0, h, w)]
        max_move = 0
        while queue:
            move, nh, nw = heapq.heappop(queue)
            if not (0 <= nh < H and 0 <= nw < W):
                continue
            if visited[nh][nw]:
                continue
            if maze[nh][nw] == "#":
                continue
            visited[nh][nw] = True
            max_move = max(max_move, move)
            heapq.heappush(queue, (move + 1, nh + 1, nw))
            heapq.heappush(queue, (move + 1, nh - 1, nw))
            heapq.heappush(queue, (move + 1, nh, nw + 1))
            heapq.heappush(queue, (move + 1, nh, nw - 1))
        ans = max(ans, max_move)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[0 for i in range(W)] for j in range(H)]
maze = [input() for i in range(H)]
X = []
for i in range(H):
  for j in range(W):
    if maze[i][j] == '.':
      p = [i, j]
      Al = [p]
      luck = 0
      A[p[0]][p[1]] = -1
      while Al != []:
        luck += 1
        n = len(Al)
        for m in range(n):
          if Al[0][0] > 0 and maze[Al[0][0]-1][Al[0][1]] == '.' and A[Al[0][0]-1][Al[0][1]] == 0:
            A[Al[0][0]-1][Al[0][1]] = luck
            Al.append([Al[0][0]-1, Al[0][1]])
          if Al[0][0] < H - 1 and maze[Al[0][0]+1][Al[0][1]] == '.' and A[Al[0][0]+1][Al[0][1]] == 0:
            A[Al[0][0]+1][Al[0][1]] = luck
            Al.append([Al[0][0]+1, Al[0][1]])
          if Al[0][1] > 0 and maze[Al[0][0]][Al[0][1]-1] == '.' and A[Al[0][0]][Al[0][1]-1] == 0:
            A[Al[0][0]][Al[0][1]-1] = luck
            Al.append([Al[0][0], Al[0][1]-1])
          if Al[0][1] < W - 1 and maze[Al[0][0]][Al[0][1]+1] == '.' and A[Al[0][0]][Al[0][1]+1] == 0:
            A[Al[0][0]][Al[0][1]+1] = luck
            Al.append([Al[0][0], Al[0][1]+1])
          Al = Al[1:]
      X.append(luck-1)
      A = [[0 for i in range(W)] for j in range(H)]
print(max(X))

Submission status: Accepted

Solution code:
from collections import deque

INF = 10**5
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy):
    if maze[sx][sy] == "#":
        return [[-1]]
    # すべての点を INF で初期化
    d = [[-INF] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # for i in range(n):
    #     for j in range(m):
            # スタートとゴールの座標を探す
            # if maze[i][j] == "S":
            #     sx = i
            #     sy = j
            # if maze[i][j] == "G":
            #     gx = i
            #     gy = j

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        # if p[0] == gx and p[1] == gy:
        #     break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == -INF:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d


n, m = map(int, input().split())
ma = [list(input()) for i in range(n)]
maxm=0
for i in range(m):
    for j in range(n):
        a = bfs(ma, j, i)
        # print(a)
        for x in a:
            for y in x:
                maxm = maxm if maxm>y else y
print(maxm)