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 collections import deque
H, W = map(int, input().split())
dif = [(-1, 0), (1, 0), (0, 1), (0, -1)]
Map = [list(input()) for i in range(H)]
visited = [[False for i in range(W)] for j in range(H)]
deq = deque()


def bfs(node):
    nx, ny = node
    deq.append(node)

    visited[nx][ny] = True
    distance = [[float("inf") for i in range(W)] for j in range(H)]
    distance[nx][ny] = 0
    while deq:
        x, y = deq.popleft()
        for dx, dy in dif:
            if 0 <= x+dx < H and 0 <= y+dy < W and Map[x+dx][y+dy] == "." and visited[x+dx][y+dy] == False:
                visited[x+dx][y+dy] = True
                distance[x+dx][y+dy] = distance[x][y]+1
                deq.append((x+dx, y+dy))
    return distance


def s_bfs(node):
    nx, ny = node
    deq.append(node)
    Visited = [[False for i in range(W)] for j in range(H)]
    Visited[nx][ny] = True
    distance = [[float("inf") for i in range(W)] for j in range(H)]
    distance[nx][ny] = 0
    while deq:
        x, y = deq.popleft()
        for dx, dy in dif:
            if 0 <= x+dx < H and 0 <= y+dy < W and Map[x+dx][y+dy] == "." and Visited[x+dx][y+dy] == False:
                Visited[x+dx][y+dy] = True
                distance[x+dx][y+dy] = distance[x][y]+1
                deq.append((x+dx, y+dy))
    return distance


ans = 1
roads = deque()
for i in range(H):
    for j in range(W):
        if Map[i][j] == ".":
            roads.append((i, j))

while roads:
    x, y = roads.popleft()
    if visited[x][y] == False:
        B = s_bfs((x, y))
        s = -1
        choice=[]
        most_far_distance = 0
        for i in range(H):
            for j in range(W):
                if B[i][j] != float("inf") and B[i][j] > most_far_distance:
                    most_far_distance = B[i][j]
        for i in range(H):
            for j in range(W):
                if B[i][j] == most_far_distance:
                    choice.append((i, j))

        for s in choice:
            C = s_bfs(s)
            for i in range(H):
                for j in range(W):
                    if C[i][j] != float("inf"):
                        ans = max(ans, C[i][j])
print(ans)

Submission status: Accepted

Solution code:
# 幅優先探索
from collections import deque
H, W = map(int, input().split())
dif = [(-1, 0), (1, 0), (0, 1), (0, -1)]
Map = [list(input()) for i in range(H)]
visited = [[False for i in range(W)] for j in range(H)]
deq = deque()


def bfs(node):
    nx, ny = node
    deq.append(node)

    visited[nx][ny] = True
    distance = [[float("inf") for i in range(W)] for j in range(H)]
    distance[nx][ny] = 0
    while deq:
        x, y = deq.popleft()
        for dx, dy in dif:
            if 0 <= x+dx < H and 0 <= y+dy < W and Map[x+dx][y+dy] == "." and visited[x+dx][y+dy] == False:
                visited[x+dx][y+dy] = True
                distance[x+dx][y+dy] = distance[x][y]+1
                deq.append((x+dx, y+dy))
    return distance


def s_bfs(node):
    nx, ny = node
    deq.append(node)
    Visited = [[False for i in range(W)] for j in range(H)]
    Visited[nx][ny] = True
    distance = [[float("inf") for i in range(W)] for j in range(H)]
    distance[nx][ny] = 0
    while deq:
        x, y = deq.popleft()
        for dx, dy in dif:
            if 0 <= x+dx < H and 0 <= y+dy < W and Map[x+dx][y+dy] == "." and Visited[x+dx][y+dy] == False:
                Visited[x+dx][y+dy] = True
                distance[x+dx][y+dy] = distance[x][y]+1
                deq.append((x+dx, y+dy))
    return distance


ans = 1
roads = deque()
for i in range(H):
    for j in range(W):
        if Map[i][j] == ".":
            roads.append((i, j))

while roads:
    x, y = roads.popleft()
    if visited[x][y] == False:
        B = s_bfs((x, y))
        s = -1
        choice=[]
        most_far_distance = 0
        for i in range(H):
            for j in range(W):
                if B[i][j] != float("inf") and B[i][j] > most_far_distance:
                    most_far_distance = B[i][j]
        for i in range(H):
            for j in range(W):
                if B[i][j] == most_far_distance:
                    choice.append((i, j))

        for s in choice:
            C = s_bfs(s)
            for i in range(H):
                for j in range(W):
                    if C[i][j] != float("inf"):
                        ans = max(ans, C[i][j])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def MI(): return map(int, input().split())

def bfs(field,s):
  MOVE=[(0,1),(1,0),(0,-1),(-1,0)]
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  #d,i,j=-1,-1,-1
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if dist[ni][nj]!=-1:
        continue
      if field[ni][nj]=='#':
        continue
      q.append((d+1,(ni,nj)))
  return d
ans=0
H,W=MI()
field=[input() for _ in range(H)]
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def bfs(field,s):
  MOVE=[(0,1),(1,0),(0,-1),(-1,0)]
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  d,i,j=-1,-1,-1
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if dist[ni][nj]!=-1:
        continue
      if field[ni][nj]=='#':
        continue
      q.append((d+1,(ni,nj)))
  return d
ans=0
H,W=MI()
field=[input() for _ in range(H)]
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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


def solve_maze(s):
    bias = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    inf = 10 ** 9

    d = [[inf] * W for _ in range(H)]
    d[s[0]][s[1]] = 0

    q = deque()
    q.append(s)
    while q:
        u, v = q.popleft()
        for i, j in bias:
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and d[u + i][v + j] > d[u][v] + 1):
                d[u + i][v + j] = d[u][v] + 1
                q.append((u + i, v + j))

    res = 0
    for i in range(H):
        for j in range(W):
            if d[i][j] < inf:
                res = max(res, d[i][j])
                
    return res


ans = 0
for i in range(H):
    for j in range(W):
        if X[i][j] == ".":
            ans = max(ans, solve_maze((i, j)))

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 
H,W = map(int,readline().split())
grid = ''
grid += '#'* (W+2)
for _ in range(H):
    grid += '#' + readline().decode().rstrip() + '#'
grid += '#'*(W+2)
L = len(grid)
INF = float('inf')

def bfs(start):
    dist = [-INF] * L
    q = [start]
    dist[start] = 0
    while q:
        qq = []
        for x,dx in itertools.product(q,[1,-1,W+2,-W-2]):
            y = x+dx
            if dist[y] != -INF or grid[y] == '#':
                continue
            dist[y] = dist[x] + 1
            qq.append(y)
        q = qq
    return max(dist) 

ans = 0
for i in range(L):
    if grid[i] == '.':
        start = i
        max_dist = bfs(start)
        ans = max(ans,max_dist)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

v = {(1,0), (-1,0), (0,1), (0,-1)}
q = deque()
ans = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
                    
            #bfs
            dist = [[-1 for _ in range(W)] for _ in range(H)]
            dist[i][j] = 0
            q.append([j, i])
            while len(q) > 0:
                now = q.popleft()
                x, y = now[0], now[1]
                d = dist[y][x]
                for dx, dy in v:
                    nx, ny = x+dx, y+dy
                    if 0<=nx<W and 0<=ny<H and dist[ny][nx]==-1 and maze[ny][nx]=='.':
                        dist[ny][nx] = d+1
                        q.append([nx, ny])
            
            ans = max(ans, d)
print(ans)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
from collections import deque
def bfs(field,s):
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  d,i,j=-1,-1,-1
  MOVE=[(-1,0),(0,-1),(1,0),(0,1)]
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='#':
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
from collections import deque
def bfs(field,s):
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  d,i,j=-1,-1,-1
  MOVE=[(-1,0),(0,-1),(1,0),(0,1)]
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='#':
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d,i,j
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d,i,j=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
from collections import deque
def bfs(field,s):
  q=deque([(0,s)])
  MOVE=[(-1,0),(0,-1),(1,0),(0,1)]
  dist=[[-1]*W for i in range(H)]
  d,i,j=-1,-1,-1  
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni=i+di
      nj=j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='#':
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d,i,j
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d,i,j=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def MI(): return map(int, input().split())
def bfs(field,s):
  q=deque([(0,s)])
  MOVE=[(-1,0),(0,-1),(0,1),(1,0)]
  d,i,j=-1,-1,-1
  dist=[[-1]*W for i in range(H)]  
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni=i+di
      nj=j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='#':
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d,i,j
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d,i,j=bfs(field,(i,j))      
      ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7

# グリッドBFS
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        dis = [[-1 for k in range(w)] for k in range(h)]
        dis[i][j] = 0
        d = deque()
        d.append([i, j])
        while len(d):
            now = d.popleft()
            y = now[0]
            x = now[1]
            for k in range(4):
                ny = y + dy_dx[k][0]
                nx = x + dy_dx[k][1]
                if 0 <= ny < h and 0 <= nx < w:
                    if s[ny][nx] != '#' and dis[ny][nx] == -1:
                        dis[ny][nx] = dis[y][x] + 1
                        ans = max([ans, dis[ny][nx]])
                        d.append([ny, nx])

print(ans)

Submission status: Accepted

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

sy=0
sx=0
for i in range(H):
    for j in range(W):
        c=0
        route=deque([(i,j,0)])
        S=copy.deepcopy(S1)
        while route:
            a,b,n=route.popleft()
            c=n
            if 0<=a<=H-1 and 0<=b<=W-1:
                if S[a][b]=='.':
                    S[a][b]='#'
                    route.append((a+1,b,n+1))
                    route.append((a-1,b,n+1))
                    route.append((a,b+1,n+1))
                    route.append((a,b-1,n+1))
                    
        ans.append(c-1)

print(max(ans))

Submission status: Accepted

Solution code:
from itertools import product

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


def neighbors(ih, iw):
    for ih1, iw1 in (
        (ih - 1, iw),
        (ih + 1, iw),
        (ih, iw - 1),
        (ih, iw + 1),
    ):
        if 0 <= ih1 < h and 0 <= iw1 < w and maze[ih1][iw1] == '.':
            yield (ih1, iw1)



def len_maze(ih, iw):
    # BFS
    if maze[ih][iw] == '#':
        return 0

    stepped = [[False] * w for _ in range(h)]
    q0 = [(ih, iw)]
    l = -1
    while q0:
        q1 = set()
        for ih0, iw0 in q0:
            stepped[ih0][iw0] = True
            for ih1, iw1 in neighbors(ih0, iw0):
                if not stepped[ih1][iw1]:
                    q1.add((ih1, iw1))
        q0 = list(q1)
        l += 1

    return l


answer = max(len_maze(ih, iw) for ih, iw in product(range(h), range(w)))
print(answer)

Submission status: Accepted

Solution code:
import queue

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

def bfs(dist, i, j):
    q = queue.Queue()
    q.put((i, j, 0))
    while not q.empty():
        i, j, c = q.get()
        # print(i, j, c, dist)
        if i != 0 and dist[i-1][j] == 0:
            dist[i-1][j] = c+1
            q.put((i-1, j, c+1))
        if j != 0 and dist[i][j-1] == 0:
            dist[i][j-1] = c+1
            q.put((i, j-1, c+1))
        if i != h-1 and dist[i+1][j] == 0:
            dist[i+1][j] = c+1
            q.put((i+1, j, c+1))
        if j != w-1 and dist[i][j+1] == 0:
            dist[i][j+1] = c+1
            q.put((i, j+1, c+1))
    return dist, c

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            dist = [[(maze[y][x] == '#')*-1 for x in range(w)] for y in range(h)]
            dist[i][j] = -10
            dist, c = bfs(dist, i, j)
            tmp_ans = c
            if tmp_ans > ans:
                ans = tmp_ans

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
m = [[1, 0], [-1, 0], [0, 1], [0, -1]]
h, w = map(int, input().split())
l = []
l.append("#"*(w + 2))

for i in range(h):
    j = input()
    l.append("#" + j + "#")

l.append("#"*(w + 2))

def bfs(a, b):
    s = [[-1 for j in i] for i in l]
    s[a][b] = 0
    q = deque([[a, b]])
    while len(q) > 0:
        x, y = q.popleft()
        for i, j in m:
            if l[x + i][y + j] == "." and s[x + i][y + j] == -1:
                q.append([x + i, y + j])
                s[x + i][y + j] = s[x][y] + 1
                num = s[x + i][y + j]
    return num

ans = []

for i in range(h + 2):
    for j in range(w + 2):
        if l[i][j] == ".":
            ans.append(bfs(i, j))

print(max(ans))

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W = map(int, readline().split())
    S = [[0] * W for _ in range(H)]
    for i in range(H):
        S[i] = readline().strip()

    dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                continue
            dist = [[-1] * W for _ in range(H)]
            dist[i][j] = 0
            queue = deque([(i, j)])
            res = 0
            while queue:
                x, y = queue.popleft()
                for dx, dy in dxdy4:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                        dist[nx][ny] = dist[x][y] + 1
                        if res < dist[nx][ny]:
                            res = dist[nx][ny]
                        queue.append((nx, ny))
            if ans < res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
  h, w = map(int, input().split())
  area = [[s for s in sys.stdin.readline().strip()] for _ in range(h)]
  start_point = {0:set(), 1:set(), 2:set(), 3:set(), 4:set()}
  min_neighbor = 4
  for i in range(h):
    for j in range(w):
      if area[i][j] == '#':
        continue
      roads = 0
      if i > 0 and area[i - 1][j] == '.':
        roads += 1
      if i < h - 1 and area[i + 1][j] == '.':
        roads += 1
      if j > 0 and area[i][j - 1] == '.':
        roads += 1
      if j < w - 1 and area[i][j + 1] == '.':
        roads += 1
      min_neighbor = min(min_neighbor, roads)
      start_point[roads].add((i, j))
  max_cost = 0
  for start in start_point[min_neighbor]:
    queue = deque()
    queue.append(start)
    cost = 0
    visited = set()
    while len(queue) > 0:
      roads = len(queue)
      found = False
      for i in range(roads):
        s = queue.popleft()
        if s in visited:
          continue
        found = True
        visited.add(s)
        i = s[0]
        j = s[1]
        if i > 0 and area[i - 1][j] == '.':
          queue.append((i - 1, j))
        if i < h - 1 and area[i + 1][j] == '.':
          queue.append((i + 1, j))
        if j > 0 and area[i][j - 1] == '.':
          queue.append((i, j - 1))
        if j < w - 1 and area[i][j + 1] == '.':
          queue.append((i, j + 1))
      if not found:
        cost -= 1
      max_cost = max(cost, max_cost)
      if found:
        cost += 1
  print(max_cost)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
    for j,c in enumerate(s):
        u = i*cols+j
        if i>0:
            if c==OK and ss[i-1][j]==OK:
                v = u - cols
                ns[u].add(v)
                ns[v].add(u)
        if j>0:
            if c==OK and s[j-1]==OK:
                v = u - 1
                ns[u].add(v)
                ns[v].add(u)
                    
n = rows * cols

def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = d + 1
                q.appendleft(v)
    return seen
ans = -1
for i in range(rows):
    for j in range(cols):
        if ss[i][j] == "#":
            continue
        u = i*cols+j
        dist = bfs(u)
        ans = max(ans, max(num for num in dist if num is not None))
print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
dx = [-1,0,1,0]
dy = [0,-1,0,1]
h,w = readInts()
S = [list(input()) for _ in range(h)]
def bfs(y,x):
    dq = deque()
    dq.append((y,x))
    res = -1
    dist = [[-1] * w for _ in range(h)]
    dist[y][x] = 0
    while dq:
        y,x = dq.popleft()
        res = max(res,dist[y][x])
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if not(0 <= ny < h and 0 <= nx < w):
                continue
            if S[ny][nx] == '#' or dist[ny][nx] != -1:
                continue
            dist[ny][nx] = dist[y][x] + 1
            dq.append((ny,nx))
    return res
ans = -1
for y in range(h):
    for x in range(w):
        if S[y][x] != '#':
            ans = max(ans,bfs(y,x))
print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque

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

maze_o = [0]*h
for i in range(h):
    maze_o[i] = list(input())

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
#すべての "." をスタート位置にする
ans = 0
for y in range(h):
    for x in range(w):
        if maze_o[y][x] == "#":
            continue
        maze = copy.deepcopy(maze_o)
        distance = deque([0])
        rireki = deque([])
        stack = deque([(y, x)])
        maze[y][x] = "#"
        while stack:
            yy, xx = stack.popleft()
            d = distance.popleft()
            rireki.append(d)
            for dxi,dyi in zip(dx, dy):
                if not (0<=dxi+xx<w and 0<=dyi+yy<h):
                    continue
                if maze[dyi+yy][dxi+xx] == "#":
                    continue
                distance.append(d+1)
                stack.append((dyi+yy,dxi+xx))
                maze[dyi+yy][dxi+xx] = "#"
        ans = max(ans, max(rireki))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

ini = -1
q = deque()

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
ans = 0

for y in range(H):
    for x in range(W):
        dist = [[ini for _ in range(W)] for _ in range(H)]
        if grid[y][x] == "#": continue
        dist[y][x] = 0
        q.append((y, x))

        while(len(q) > 0):
            oy, ox = q.popleft()
            for di in range(4):
                ny = oy + dy[di]
                nx = ox + dx[di]

                if (ny < 0 or ny >= H or nx < 0 or nx >= W): continue
                if grid[ny][nx] == "#": continue
                if dist[ny][nx] != ini: continue

                dist[ny][nx] = dist[oy][ox] + 1
                q.append((ny, nx))

        ans = max(np.max(dist), ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ini = -1
q = deque()

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
ans = 0

for y in range(H):
    for x in range(W):
        dist = [[ini for _ in range(W)] for _ in range(H)]
        if grid[y][x] == "#": continue
        dist[y][x] = 0
        q.append((y, x))

        while(len(q) > 0):
            oy, ox = q.popleft()
            for di in range(4):
                ny = oy + dy[di]
                nx = ox + dx[di]

                if (ny < 0 or ny >= H or nx < 0 or nx >= W): continue
                if grid[ny][nx] == "#": continue
                if dist[ny][nx] != ini: continue

                dist[ny][nx] = dist[oy][ox] + 1
                q.append((ny, nx))

        ans = max(max(map(max, dist)), ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque 
from copy import deepcopy
# 初期入力
import sys
input = sys.stdin.readline
H,W = (int(i) for i in input().split())
map_initial =[["#"]*(W+2) for i in range(H+2)] #周囲を壁にするため＋２
for h in range(1,H+1):
    map_initial[h] =["#"] +list(input().strip()) +["#"]

def BSF(x,y):
    dist =0
    map =deepcopy(map_initial)
    if map[x][y] =="#":
        return dist 
    dq =set()
    dq.add((x,y))
    dq_sarch =set()
    while len(dq) >0:
        h,w =dq.pop()
        map[h][w] ="#" #通り済を壁にする
        if map[h+1][w]==".":
            dq_sarch.add((h+1,w))
        if map[h-1][w]==".":
            dq_sarch.add((h-1,w))
        if map[h][w+1]==".":
            dq_sarch.add((h,w+1))
        if map[h][w-1]==".":
            dq_sarch.add((h,w-1))
        if len(dq)==0:
            dq =deepcopy(dq_sarch)
            dq_sarch.clear()
            dist +=1
        #print(h,w,dist,end="\t")
    return dist-1

#スタート位置を全探索し、最長距離を探す
dist_all =[]
for i in range(1,H+1):
    for j in range(1,W+1):
        dist_all.append(BSF(i,j) )
print(max(dist_all))

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

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

    # スタート地点をキューに入れ、その点の距離を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] == float("-inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    a = np.max(d) 
    return a

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
ans = 1

for x in range(n):
    for y in range(m):
        sx = x
        sy = y
        if maze[sx][sy] == "#":
            continue
        A = bfs(sx, sy)
        ans = max(A, ans)
print(int(ans))

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
check=[[0,-1],[0,1],[-1,0],[1,0]]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            d = deque()
            d.append([i,j])
            a = [[-1] * w for _ in range(h)]
            a[i][j]=0
            while d:
                v = d.popleft()
                ii=v[0]
                jj=v[1]
                for c in check:
                    x=c[0]
                    y=c[1]
                    if ii+x in range(h) and jj+y in range(w):
                        if a[ii+x][jj+y]==-1:
                            if s[ii+x][jj+y]==".":
                                a[ii+x][jj+y]=a[ii][jj]+1
                                d.append([ii+x,jj+y])
                            else:
                                a[ii+x][jj+y]=0
            ans2=sorted(sum(a,[]),reverse=True)[0]
            if ans<ans2:
                ans=ans2
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc151/tasks/abc151_d
# TODO: try
import sys
from collections import deque


def main():
    h, w = map(int, sys.stdin.readline().split())
    area = [[s for s in sys.stdin.readline().strip()] for _ in range(h)]
    start_point = {0: set(), 1: set(), 2: set(), 3: set(), 4: set()}
    min_neighbor = 4
    for i in range(h):
        for j in range(w):
            if area[i][j] == "#":
                continue
            roads = 0
            # 上
            if i > 0 and area[i - 1][j] == ".":
                roads += 1
            # 下
            if i < h - 1 and area[i + 1][j] == ".":
                roads += 1
            # 左
            if j > 0 and area[i][j - 1] == ".":
                roads += 1
            # 右
            if j < w - 1 and area[i][j + 1] == ".":
                roads += 1
            min_neighbor = min(min_neighbor, roads)
            start_point[roads].add((i, j))
    max_cost = 0
    for start in start_point[min_neighbor]:
        # 始点候補からもっとも遠い地点をそれぞれ求める
        queue = deque()
        queue.append(start)
        cost = 0
        visited = set()
        while len(queue) > 0:
            roads = len(queue)
            found = False
            for i in range(roads):
                s = queue.popleft()
                if s in visited:
                    continue
                found = True
                visited.add(s)
                i = s[0]
                j = s[1]
                # 上
                if i > 0 and area[i - 1][j] == ".":
                    queue.append((i - 1, j))
                # 下
                if i < h - 1 and area[i + 1][j] == ".":
                    queue.append((i + 1, j))
                # 左
                if j > 0 and area[i][j - 1] == ".":
                    queue.append((i, j - 1))
                # 右
                if j < w - 1 and area[i][j + 1] == ".":
                    queue.append((i, j + 1))
            if not found:
                cost -= 1
            max_cost = max(cost, max_cost)
            if found:
                cost += 1
    print(max_cost)


if __name__ == '__main__':
    main()