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 copy import copy
from itertools import product
h, w = map(int, input().split())
maze = []
max_d = 0
for i in range(h):
    maze.append(input())
for i, j in product(range(h), range(w)):
    if maze[i][j] == '#':
        continue
    s = (i, j)
    pathes = [[s]]
    seen = {s}
    while pathes:
        path = pathes.pop(0)
        a, b = path[-1]
        for point in [(0, 1), (1, 0), (0, -1),(-1, 0)]:
            di, dj = point
            if a + di >= 0 and a + di < h and b + dj >= 0 and b + dj < w and (a+di, b+dj) not in seen and maze[a+di][b+dj]=='.':
                copy_path = copy(path)
                copy_path.append((a + di, b + dj))
                seen.add((a+di, b+dj))
                pathes.append(copy_path)
                max_d = max(max_d, len(copy_path)-1)
print(max_d)

Submission status: Accepted

Solution code:
import collections

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


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw))
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[sh][sw] = 0

    while que:
        h, w = que.popleft()
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '.' and dist[h + dh][w + dw] == -1:
                dist[h + dh][w + dw] = dist[h][w] + 1
                que.append((h + dh, w + dw))

    ans = 0
    for row in dist:
        ans = max(ans, max(row))
    return ans


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

Submission status: Accepted

Solution code:
from collections import deque
import sys

r,c = map(int,input().split())
m = [input() for _ in range(r)]


def maze(sy,sx):
    q = deque()
    vm = [[-1] * c for _ in range(r)]

    vm[sy][sx] = 0
    q.append([sy,sx])

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

        for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            xi , yj = x + i , y + j
            if xi >= 0 and yj >= 0 and xi < c and yj < r and vm[yj][xi] == -1 and m[yj][xi] != "#":
                vm[yj][xi] = vm[y][x] + 1
                q.append([yj,xi])

    ret=0
    for ss in vm:
        ret=max(ret,max(ss))

    return ret

res=0
for h in range(r):
    for w in range(c):
        if m[h][w] == '#':
            continue

        res=max(res,maze(h,w))

print(res)

Submission status: Accepted

Solution code:
from collections import*
from copy import*
n,m=map(int,input().split())

grid=[list("#"*(m+2))]+[list("#"+input()+"#")for i in range(n)]+[list("#"*(m+2))]
#print(grid)

start=[]
for i in range(1,n+1):
    for j in range(1,m+1):
        start.append((i,j))

ans=0
for s in start:
    G=deepcopy(grid)
    if G[s[0]][s[1]]!="#":
        G[s[0]][s[1]]=0
    else:
        continue
    Q=deque([s])
    while Q:
        y,x=Q.pop()
        for my,mx in (-1,0),(1,0),(0,-1),(0,1):
            if G[y+my][x+mx]==".":
                G[y+my][x+mx]=G[y][x]+1
                Q.appendleft((y+my,x+mx))
    
    x=max( max([0]+[j for j in i  if type(j)==int]) for i in G)
    if x>ans:
        ans=x
print(ans)

Submission status: Accepted

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

def bfs(sy, sx):
    dst = [[-1]*w for _ in range(h)]
    dst[sy][sx] = 0
    que = deque([])
    que.append([sy, sx])

    while que:
        y, x = que.popleft()
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            if s[ny][nx] == '#':
                continue
            if dst[ny][nx] != -1:
                continue

            dst[ny][nx] = dst[y][x] + 1
            maxd[0] = dst[y][x] + 1
            que.append([ny, nx])



ans = -float('inf')
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        maxd = [0]
        bfs(i, j)
        ans = max(ans, maxd[0])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

S = [['#'] * (W + 2)]
for _ in range(H):
    tmp = ['#'] + list(input()) + ['#']
    S.append(tmp)
S.append(['#'] * (W + 2))
#迷路の周りを全て壁で覆うことでどの場所からでも四方に探索できるようにした

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

ans = 0
# スタート位置を変えながら全探索
for X in range(1, H + 1):
    for Y in range(1, W + 1):
        if S[X][Y] == '#':
            continue
#if ~ continue分はtrueなら下の操作を行うことなく次の番号に移るという意味
        check = [[-1] * (W + 2) for _ in range(H + 2)]
        check[X][Y] = 0
        que = deque()
        que.append([X, Y])
        while que:
            tmp = que.popleft()
            x = tmp[0]
            y = tmp[1]
            flag = True
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if S[nx][ny] == '.' and check[nx][ny] == -1:
                    que.append([nx, ny])
                    check[nx][ny] = check[x][y] + 1
                    flag = False
#flagの使い方が上手、真似したい
            if flag:
                ans = max(ans, check[x][y])


print (ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import queue

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

	for i in range(H):
		S[i] = [x for x in input()]

	max_d = [[-1 for x in range(W)] for y in range(H)]
	for i in range(H):
		for j in range(W):
			if S[i][j] == "#":
				continue
			d = [[-1 for x in range(W)] for y in range(H)]
			q = queue.Queue()
			q.put([i, j])
			d[i][j] = 0
			while not q.empty():
				n = q.get()
				for y, x in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
					if (n[0] == 0   and y == -1) or\
					   (n[0] == H-1 and y ==  1) or\
					   (n[1] == 0   and x == -1) or\
					   (n[1] == W-1 and x ==  1) or\
					   S[n[0]+y][n[1]+x] == "#"  or\
					   d[n[0]+y][n[1]+x] != -1:
						continue
					d[n[0]+y][n[1]+x] = d[n[0]][n[1]] + 1
					q.put([n[0]+y, n[1]+x])
			for y in range(H):
				for x in range(W):
					if max_d[i][j] < d[y][x]:
						max_d[i][j] = d[y][x]

	max = 0
	for i in range(H):
		for j in range(W):
			if max < max_d[i][j]:
				max = max_d[i][j]

	print(str(max))

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math
from queue import Queue
import copy

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

q = Queue()
ans = 0

for y in range(h):
    for x in range(w):
        li = copy.deepcopy(ili)
        if li[y][x] == "#": continue
        q.put([x, y])
        li[y][x] = 0
        while not q.empty():
            c = q.get()
            # 上(0, -1) 右(1, 0) 下(0, 1) 左(-1, 0)
            for dr in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
                nX = c[0] + dr[0]
                nY = c[1] + dr[1]

                if not (0 <= nX <= w - 1): continue
                if not (0 <= nY <= h - 1): continue

                if li[nY][nX] == ".":
                    li[nY][nX] = li[c[1]][c[0]] + 1
                    q.put([nX, nY])

        li = list(
            map(lambda item: 0 if item == "#" or item == "." else item,
                sum(li, [])))
        ans = max(li + [ans])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

maze = []
for _ in range(H):
    maze.append(list(input()))

#bfsならうまく解ける!!
def bfs(i, j):
    q = deque([(i, j, 0)])
    seen = set([(i, j)])
    ans = 0
    while q:
        i, j, d = q.popleft()
        ans = max(ans ,d)
        for dx, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x = i + dx
            y = j + dj
            if 0 <= x < H and 0 <= y < W and maze[x][y] == "." :
                if (x, y) not in seen:
                    seen.add((x, y))
                    q.append((x, y, d + 1))           
    return ans


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

Submission status: Accepted

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

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

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

import sys
from collections import deque

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# data = [ns() for _ in range(H)]

data = [list("#" * (W + 2))]
# 周りを'#'で埋めておく
for _ in range(H):
    data.append(["#"] + list(input()) + ["#"])
data += [list("#" * (W + 2))]


def bfs(h, w):
    dist = [[-1] * (W+2) for _ in range(H+2)]
    q = deque()

    max_dist = 0
    dist[h][w] = 0
    q.append((h, w, 0))

    # while len(q) > 0:
    while len(q) > 0:
        h, w, val = q.popleft()

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if data[h_new][w_new] == '.' and dist[h_new][w_new] == -1:
                q.append((h_new, w_new, val+1))
                dist[h_new][w_new] = val + 1
                max_dist = max(max_dist, val + 1)

    return max_dist


ans = 0
for h in range(H+2):
    for w in range(W+2):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
que = deque([])

def bfs(sy,sx):
    d = [[float("inf")] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que.append((sy,sx))
    d[sy][sx] = 0
    route = []
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0<=ny<H and 0<=nx<W and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                route.append(d[ny][nx])
    return max(route)

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

M = 0
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] != "#":
            num = bfs(sy,sx)
            if M <= num:
                M = num
print(M)

Submission status: Accepted

Solution code:
from collections import deque
  

H,W = map(int, input().split())
s = ["#"*(W+2)]+["#"+input()+"#" for i in range(H)]+["#"*(W+2)]
def bfs(sh,sw):
  if s[sh][sw] == "#":
    return 0
  queue = deque([(sh,sw)])
  dist = [[-1] * (W+1) for i in range(H+1)]
  dist[sh][sw] = 0
  while queue:
    h,w = queue.popleft()
    d = dist[h][w]
    for i in [h-1,h+1]:
      if s[i][w] == "." and dist[i][w] == -1:
        dist[i][w] = d + 1
        queue.append((i,w))
    for j in [w-1,w+1]:
      if s[h][j] == "." and dist[h][j] == -1:
        dist[h][j] = d + 1
        queue.append((h,j))
          
  max_dist = 0
  for i in dist:
    max_dist = max(max_dist,max(i))
  return max_dist
      

ans = 0          
for i in range(1,H+1):
  for j in range(1,W+1):
    now = bfs(i,j)
    ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
def dfs(world,i,j):#コピーした世界と開始場所
  c=0
  mc=-1
  pos=deque()
  pos.append((i,j,c))
  while pos:
    i,j,c=pos.popleft()
    if world[i][j]=="#":
      continue
    if world[i+1][j]!="#":
      pos.append((i+1,j,c+1))
    if world[i-1][j]!="#":
      pos.append((i-1,j,c+1))
    if world[i][j+1]!="#":
      pos.append((i,j+1,c+1))
    if world[i][j-1]!="#":
      pos.append((i,j-1,c+1))
    world[i][j]="#"
    if mc<c:
      mc=c
  return mc
ans=0
H,W=map(int,input().split())
#１．シャープが壁の迷路を作る
world=[]
world.append(["#"]*(W+2))
for i in range(H):
  world.append(["#"]+list(input())+["#"])
world.append(["#"]*(W+2))
#作った
#dfsをすべての場所で行う
for i in range(H+2):
  for j in range(W+2):
    if world[i][j]==".":
      mc=dfs(deepcopy(world),i,j)
      if ans<mc:
        ans=mc
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(maze, visited, sh, sw, H, W):
    q = deque([(sh, sw)])
    visited[sh][sw] = 0
    M = 0
    while q:
        h, w = q.popleft()
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if maze[nh][nw] == "." and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))
                    if visited[nh][nw] > M:
                        M = visited[nh][nw]

    return M


ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == "#":
            continue
        visited = [[-1] * W for _ in range(H)]
        tmp = bfs(maze, visited, h, w, H, W)
        if tmp > ans:
            ans = tmp
print(ans)

Submission status: Accepted

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

# WFS
ans = []
d = [(1,0), (0,1), (-1,0), (0,-1)]
from collections import deque
for i in range(1, h+1):
    for j in range(1, w+1): # start = s[i][j]
        if s[i][j] == '#':
            continue
        seen = [[-1 for _ in range(w+2)] for __ in range(h+2)]
        seen[i][j] = 0
        todo = deque([(i, j)])
        num = 0
        while todo != deque([]):
            x, y = todo.popleft()
            for k in d:
                xk = x + k[0]
                yk = y + k[1]
                if seen[xk][yk] == -1 and s[xk][yk] == '.':
                    num = seen[x][y] + 1
                    seen[xk][yk] = num
                    todo.append((xk,yk))
        ans.append(num)
print(max(ans))

Submission status: Accepted

Solution code:
import copy
from collections import deque

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


def check(tup):
    global H
    global W
    global S

    tup_x=tup[0]
    tup_y=tup[1]
    if 0<=tup_x<H and 0<=tup_y<W:
        if S[tup_x][tup_y]=='.':
            return True
    else:
        return False

def neighbor(tup):
    x=tup[0]
    y=tup[1]
    cand=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    List=[]
    for c in cand:
        if check(c):
            List.append(c)
    return List

def bfs(start):#startはtuple型
    global H
    global W

    if check(start):
        deq=deque()#as queue
        Dict=[]
        component=[]
        for i in range(W):
            component.append(-1)
        for j in range(H):
            Dict.append(copy.copy(component))

        deq.append(start)
        Dict[start[0]][start[1]]=0
        while deq:
            now=deq.popleft()
            nexts=neighbor(now)
            for next in nexts:
                next_x=next[0]
                next_y=next[1]
                if Dict[next_x][next_y]>=0:
                    continue
                #if next in deq:
                    #continue
                deq.append(next)
                Dict[next_x][next_y]=Dict[now[0]][now[1]]+1

        M=[]
        for d in Dict:
            M.append(max(d))
        return max(M)
    
    else:
        return 0

Ans=[]
for k in range(H):
    for l in range(W):
        Ans.append(bfs((k,l)))

print(max(Ans))

Submission status: Accepted

Solution code:
import copy
from collections import deque

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


def check(tup):
    global H
    global W
    global S

    tup_x=tup[0]
    tup_y=tup[1]
    if 0<=tup_x<H and 0<=tup_y<W:
        if S[tup_x][tup_y]=='.':
            return True
    else:
        return False

def neighbor(tup):
    x=tup[0]
    y=tup[1]
    cand=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    List=[]
    for c in cand:
        if check(c):
            List.append(c)
    return List

def bfs(start):#startはtuple型
    global H
    global W

    if check(start):
        deq=deque()#as queue
        Dict=[]
        component=[]
        for i in range(W):
            component.append(-1)
        for j in range(H):
            Dict.append(copy.copy(component))

        deq.append(start)
        Dict[start[0]][start[1]]=0
        while deq:
            now=deq.popleft()
            nexts=neighbor(now)
            for next in nexts:
                next_x=next[0]
                next_y=next[1]
                if Dict[next_x][next_y]>=0:
                    continue
                if next in deq:
                    continue
                deq.append(next)
                Dict[next_x][next_y]=Dict[now[0]][now[1]]+1

        M=[]
        for d in Dict:
            M.append(max(d))
        return max(M)
    
    else:
        return 0

Ans=[]
for k in range(H):
    for l in range(W):
        Ans.append(bfs((k,l)))

print(max(Ans))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(input())
nodes = []
nodedict = {}
for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':
            node_id = len(nodes)
            nodedict[(r,c)] = node_id
            nodes.append((r,c))
N = len(nodes)
INF = H*W+100
dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

def connect(r1, c1, r2, c2):
    n1 = nodedict[(r1, c1)]
    n2 = nodedict[(r2, c2)]
    dist[n1][n2] = 1
    dist[n2][n1] = 1

def solve():
    for i in range(N):
        r, c = nodes[i]
        if r > 0 and maze[r-1][c] == '.':
            connect(r, c, r-1, c)
        if r < H-1 and maze[r+1][c] == '.':
            connect(r, c, r+1, c)
        if c > 0 and maze[r][c-1] == '.':
            connect(r, c, r, c-1)
        if c < W-1 and maze[r][c+1] == '.':
            connect(r, c, r, c+1)

    # Warshall Floyd
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    maxd = 0
    di, dj = None, None
    for i in range(N):
        for j in range(N):
            d = dist[i][j]
            if d < INF and maxd < d:
                maxd = d
                di = nodes[i]
                dj = nodes[j]
    return maxd  #, di, dj


print(solve())

Submission status: Accepted

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

queue = []
visited = [[0 for i in range(w)] for i in range(h)] #始点からの距離を格納、未踏なら0
ans = 0

for i in range(h): #始点(i,j)を全探索して最長経路を調べる
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]] #[y][x]の順番に注意

            while len(queue) > 0:
                now = queue.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if C[y][x] == '.' and visited[y][x] == 0:
                            visited[y][x] = visited[now[0]][now[1]]+1 #移動回数のカウント
                            queue.append([y,x])
                    
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])
            
        queue = []
        visited = [[0 for i in range(w)] for i in range(h)]              
        
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
maze=[input() for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
res=0
for sx in range(w):
  for sy in range(h):
    if maze[sy][sx]==".":
      d=[[-1 for _ in range(w)] for _ in range(h)]
      que=deque([[sx,sy]])
      d[sy][sx]=0
      while que:
        x,y=que.popleft()
        for i in range(4):
          nx=x+dx[i]
          ny=y+dy[i]
          if 0<=nx<w and 0<=ny<h and d[ny][nx]==-1 and maze[ny][nx]==".": 
            que.append([nx,ny])
            d[ny][nx]=d[y][x]+1
            if res<d[ny][nx]:
              res=d[ny][nx] 
print(res)

Submission status: Accepted

Solution code:
from collections import deque
import pprint
import numpy as np

h, w = map(int, input().split())
maze = [['*']*(w+2) for j in range(h+2)]
for i in range(1,h+1):
    maze[i][1:] = map(str,list(input()))
    maze[i].append('*')

score = []
def bfs(maze):
    for i in range(1,h+1):
        for l in range(1,w+1):
            if maze[i][l] == '#':
                continue
            visited = [[-1]*(w+1) for j in range(h+1)]
            queue = deque()
            queue.append([i, l])
            visited[i][l] = 0
            while(queue):
                y, x = queue.popleft()
                for j,k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    new_x, new_y = x+j, y+k
                    if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                        queue.append([new_y, new_x])
                        visited[new_y][new_x] = visited[y][x] + 1
            idx = np.unravel_index(np.argmax(np.array(visited)), np.array(visited).shape)
            score.append(np.array(visited)[idx])
    return (max(score))

print(bfs(maze))

Submission status: Accepted

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

from queue import Queue

def main():
     h, w = map(int, input().split())
     maze = list()
     ans = -1

     for i in range(h):
          maze.append(list(input()))
     # print(maze)

     for i in range(h):
          for j in range(w):
               ans = max(ans, solver(maze, h, w, i, j))
     
     print(ans)

def solver(maze, h, w, i, j):
     # スタート地点が壁の場合、return
     if maze[i][j] == '#':
          return -1

     # スタート地点が道の場合、探索
     solve = [['inf' for x in range(w)] for y in range(h)]
     check = [[False for x in range(w)] for y in range(h)]
     q = Queue()

     # スタート地点をキューに登録
     solve[i][j] = 0
     q.put((i, j))
     check[i][j] = True

     # スタート地点から探索
     while(not q.empty()):
          # baseを取り出す
          point = q.get()
          # print(point)
          # up:
          if point[0] - 1 >= 0:
               target = (point[0] - 1, point[1])
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

          # down
          if point[0] + 1 < h:
               target = (point[0] + 1, point[1])
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

          # left
          if point[1] - 1 >= 0:
               target = (point[0], point[1] - 1)
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

          # right
          if point[1] + 1 < w:
               target = (point[0], point[1] + 1)
               if maze[target[0]][target[1]] == '.':
                    solve[target[0]][target[1]] = checker(solve[target[0]][target[1]], solve[point[0]][point[1]] + 1)
                    if not check[target[0]][target[1]]:
                         q.put(target)
                         check[target[0]][target[1]] = True

     # print(solve)
     # print(check)

     ret = 0
     for i in range(h):
          line = [x for x in solve[i] if type(x) == int]
          if not len(line) == 0:
               ret = max(ret, max(line))

     return ret


def checker(now, new):
     if now == 'inf':
          return new
     else:
          return min(now, new)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
def dfs(world,i,j):#コピーした世界と開始場所
  c=0
  mc=-1
  pos=deque()
  pos.append((i,j,c))
  while pos:
    i,j,c=pos.popleft()
    if world[i][j]=="#":
      continue
    if world[i+1][j]!="#":
      pos.append((i+1,j,c+1))
    if world[i-1][j]!="#":
      pos.append((i-1,j,c+1))
    if world[i][j+1]!="#":
      pos.append((i,j+1,c+1))
    if world[i][j-1]!="#":
      pos.append((i,j-1,c+1))
    world[i][j]="#"
    if mc<c:
      mc=c
  return mc
ans=0
H,W=map(int,input().split())
#１．シャープが壁の迷路を作る
world=[]
world.append(["#"]*(W+2))
for i in range(H):
  world.append(["#"]+list(input())+["#"])
world.append(["#"]*(W+2))
#作った
#dfsをすべての場所で行う
for i in range(H+2):
  for j in range(W+2):
    if world[i][j]==".":
      mc=dfs(deepcopy(world),i,j)
      if ans<mc:
        ans=mc
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W  = [int(v) for v in input().split()]
S = ['#'+input()+'#' for _ in range(H)]
S.insert(0,"#"*(W+2))
S.append("#"*(W+2))

ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == "#": continue
        queue = deque([[x,y,0]])
        visited = [[False] * (W+2) for _ in range(H+2)]
        visited[y][x] = True

        while queue:
            x,y,c = queue.pop()
            for ny,nx in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
                if visited[ny][nx] or S[ny][nx] == '#': continue
                visited[ny][nx] = True
                queue.appendleft([nx,ny,c+1])
            ans = max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h,w = l_in()
S = [s_in() for _ in range(h)]
    
from collections import deque

res = 0
for i in range(h):
    for j in range(w):
        q = deque()
        s = set()
        check = lambda x,y: (not (x,y) in s) and x >= 0 and x < h and y >=0 and y < w and S[x][y] == '.'
        
        if S[i][j] == '.':
            q.append((i,j,0))

        while len(q) > 0:
            i,j,d = q.popleft()
            s.add((i,j))
            res = max(d,res)
            
            if check(i+1,j):
                s.add((i+1,j))
                q.append((i+1,j,d+1))
            if check(i-1,j):
                s.add((i-1,j))                
                q.append((i-1,j,d+1))
            if check(i,j+1):
                s.add((i,j+1))            
                q.append((i,j+1,d+1))
            if check(i,j-1):
                s.add((i,j-1))            
                q.append((i,j-1,d+1))

print(res)

Submission status: Accepted

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

dxy = [[-1, 0], [0, 1], [1, 0], [0, -1]]

ans = 0
for h in range(H):
  for w in range(W):
    if maze[h][w] == '#':
      continue
    d_maze = [[-1]*W for _ in range(H)]
    d_maze[h][w] = 0
    p = deque([[h, w]])
    while p:
      rh, rw =  p.popleft()
      for i, j in dxy:
        nh = rh + i
        nw = rw + j
        if 0 <= nh < H and 0 <= nw < W and maze[nh][nw] == '.' and d_maze[nh][nw] == -1:
          d_maze[nh][nw] = d_maze[rh][rw] + 1
          p.append([nh, nw])
    ans = max(ans, max([max(l) for l in d_maze]))
print(ans)

Submission status: Accepted

Solution code:
import copy as cp
import sys
from collections import deque


def func(s,i,j):
  dot = 0
  for c in s:
    dot += len(c.replace('#',''))
    
  d = deque()
  d.append((i,j,0))
  h = len(s)
  w = len(s[0])
  m = [[-1 for i in range(w)] for j in range(h)]
  
  count = 0
  while True:
    i,j,n = d.popleft()
    if i < 0 or j < 0 or i >= h or j >= w or s[i][j] == '#' or m[i][j] != -1:
      continue
    
    m[i][j] = n
    
    d.append((i+1,j,n+1))
    d.append((i,j+1,n+1))
    d.append((i-1,j,n+1))
    d.append((i,j-1,n+1))
    count += 1
    
    if count == dot:
      break
      
  
  ans = 0
  for i in range(len(m)):
    ans = max(ans,max(m[i]))

  return ans

h,w = map(int,input().split())
s = []
for i in range(h):
  s.append(input())

ans = 0
for i in range(h):
  for j in range(w):
    if s[i][j] == '#':
      continue
      
    tmp = func(s,i,j)
    ans = max(ans, func(s,i,j))

print(ans)

Submission status: Accepted

Solution code:
def dfs(h, w): 
    m = -1
    visited = [[-1] * W for _ in range(H)]
    stack = []
    visited[h][w] = 0
    stack.append([h, w])
    while stack:
        h, w = stack.pop()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if s[nh][nw] == "." and visited[nh][nw] == -1:
                visited[nh][nw] = visited[h][w] + 1
                stack.append([nh, nw])
            if s[nh][nw] == "." and visited[nh][nw] != -1:
                if visited[nh][nw] > (visited[h][w]+1):
                    visited[nh][nw] = visited[h][w] + 1
                    stack.append([nh, nw])
    for i in range(H):
        if m <= max(visited[i]):
            m = max(visited[i])
    return m

H, W = map(int, input().split())
s = [input() for _ in range(H)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
m = -1
dist = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = dfs(i, j)
            if m <= dist:
                m = dist
print(m)