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:
#!/usr/bin/env python3
from itertools import product

def main():
    field_y_length,field_x_length =  map(int, input().split())
    maze = [input() for i in range(field_y_length)]

    INF = 10**8
    
    max_distance = 0

    def bfs(sy,sx):
        distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]
        queue = []

        queue.insert(0,(sy,sx))

        distance[sy][sx] = 0

        res = 0

        while len(queue):
            y,x = queue.pop()

            for i in range(0,4):
                ny,nx = y + [1, 0, -1, 0][i], x + [0, 1, 0, -1][i]

                if (0 <= nx and nx < field_x_length and 0 <= ny):
                    if (ny < field_y_length and maze[ny][nx] != '#'):
                        if (distance[ny][nx] == INF):
                            queue.insert(0, (ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                            res = max(res,distance[y][x] + 1)
        
        return res

    
    for y,x in product(range(field_y_length),range(field_x_length)):
        if maze[y][x] == '#':
            continue
        max_distance = max(max_distance,bfs(y,x))
    print(max_distance)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = 998244353
INF = int(1e15)


def bfs(S, H, W, s):
    if S[s[1]][s[0]] == '#':
        return 0
    q = []
    q.append(s)
    M = [[-1 for _ in range(W)]for _ in range(H)]
    M[s[1]][s[0]] = 0
    while q != []:
        p = q.pop(0)
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for i in range(4):
            n = (p[0] + DIR[i][0], p[1] + DIR[i][1])
            if not (0 <= n[0] < W and 0 <= n[1] < H):
                continue
            if S[n[1]][n[0]] == "#":
                continue
            if M[n[1]][n[0]] != -1:
                continue
            M[n[1]][n[0]] = M[p[1]][p[0]] + 1
            q.append(n)
    res = 0
    for h in range(H):
        res = max(res, max(M[h]))
    return res


def main():
    # sys.stdin = open("sample.txt")
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, bfs(S, H, W, (w, h)))
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

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

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


def bfs(x, y):
    que = deque()
    res = 0
    dist = [[-1 for _ in range(W)] for _ in range(H)]

    que.append((x, y))
    dist[x][y] = 0
    while que:
        x, y = que.pop()
        res = max(res, dist[x][y])

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            if Shw[nx][ny] == "#":
                continue

            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                que.appendleft((nx, ny))
    return res


ans = 0
for x, y in product(range(H), range(W)):
    if Shw[x][y] == "#":
        continue
    ans = max(ans, bfs(x, y))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

print(int(ans))

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from heapq import heappop, heappush

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

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

def dfs(x, y):
    dist = [[float("inf")]*w for i in range(h)]
    heap = [(0, x, y)]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == "." and dist[nx][ny] > c+1:
                heappush(heap, (c+1, nx, ny))
    ret = 0
    for i in range(h):
        for j in range(w):
            if dist[i][j] != float("inf"):
                ret = max(ret, dist[i][j])
    return ret

ans = 0
for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            ans = max(ans, dfs(i,j))

print(ans)

Submission status: Accepted

Solution code:
import sys,copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	H,W = MI()
	maze = [[-1 for _ in range(W)] for _ in range(H)]
	for i in range(H):
		S = IS()
		for j,s in enumerate(S):
			if s == '#':
				maze[i][j] = '#'

	def bfs(sx,sy):
		from collections import deque
		que = deque()
		dist_map = copy.deepcopy(maze)
		dist_map[sy][sx]=0
		que.append((sx,sy))
		res = 0
		while len(que) > 0:
			x,y=que.popleft()
			for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
				nx = x+dx
				ny = y+dy
				if(0<=nx<W and 0<=ny<H):
					if(dist_map[ny][nx]==-1):
						dist_map[ny][nx] = dist_map[y][x]+1
						res = max(res, dist_map[ny][nx])
						que.append((nx,ny))
		return res

	ans = -1
	for i in range(H):
		for j in range(W):
			if(maze[i][j]==-1):
				dist = bfs(j,i)
				if(dist > ans):
					ans = dist
	print(ans)

main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
n = h * w
raw = []
for i in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(1)
  raw += add
wf = [[1000 for _ in range(n)] for _ in range(n)]
for i in range(n):
  if raw[i] == 0:
    wf[i][i] = 0
    d = []
    if i-w >= 0:
      d.append(i-w)
    if i+w < n:
      d.append(i+w)
    if i%w != 0:
      d.append(i-1)
    if (i+1)%w != 0:
      d.append(i+1)
    for e in d:
      if raw[e] == 0:
        wf[i][e] = 1
#for x in wf:
  #print(x)
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][k] + wf[k][j] < wf[i][j]:
        wf[i][j] = wf[i][k] + wf[k][j]
ans = 0
for i in range(n):
  for j in range(n):
    if ans < wf[i][j] % 1000:
      ans = wf[i][j]
print(ans)
#for x in wf:
  #print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from itertools import product
from collections import deque

def bfs(maze, s):
  dq = deque()
  count = 0
  dq.append((s[0], s[1], count))
  visited = numpy.zeros(maze.shape, dtype=numpy.int)
  visited[s] = 1
  dxdys = [tuple(map(lambda x:int(x.real), [(0+1j)**(id), (0+1j)**(id+1)])) for id in range(4)]
  while dq:
    x, y, count = dq.popleft()
    for dx, dy in dxdys:
      if x+dx < 0 or y+dy < 0 or maze.shape[0] <= x+dx or maze.shape[1] <= y+dy:
        continue
      if maze[x+dx, y+dy]==1 and visited[x+dx, y+dy]!=1:
        dq.append((x+dx, y+dy, count+1))
        visited[(x+dx, y+dy)] = 1
  return count


def main():
  h, w = map(int, input().strip().split())
  maze = numpy.zeros((h, w), dtype=numpy.int)
  scores = numpy.full((h, w), -1, dtype=numpy.int)
  for ih in range(h):
    maze[ih] = [(0 if c=='#' else 1)for c in input().strip()]
  for sx, sy in product(range(h), range(w)):
    if maze[sx, sy] == 0:
      continue
    scores[sx, sy] = bfs(maze, (sx, sy))
  print(numpy.max([numpy.max(scores), 0]))


if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

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

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [float('inf') for w in range(W)] for h in range(H)]
        que.append([h, w])
        history[h][w] = 0
        current_max_cost = 0
        while len(que) != 0:
            [x, y] = que.popleft()
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx and newx < H and 0 <= newy and newy < W and S[newx][newy] != "#" and history[newx][newy] == float('inf'):
                    history[newx][newy] = history[x][y] + 1
                    if current_max_cost < history[newx][newy]:
                        current_max_cost = history[newx][newy]
                    que.append([newx, newy])
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(h,w,m,sy,sx):
    INF = 10**12
    max_length = 0
    # すべての点を INF で初期化
    d = [[INF for j in range(w)] for i in range(h)]
    
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    # スタート地点をキューに入れ、その点の距離を0にする
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0
    
    # キューが空になるまでループ
    while q:
        #キューの先頭を取り出す
        p = q.popleft()
        #四方向移動
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] != '#' and d[ny][nx] == INF:
                q.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
                if d[ny][nx] > max_length:
                    max_length = d[ny][nx]
    return max_length

h,w = map(int, input().split())
m = []
max_len = 0
for i in range(h):
    m.append(input())
for i in range(h):
    for j in range(w):
        if m[i][j] == '.':
            length = bfs(h,w,m,i,j)
            if length > max_len:
                max_len = length
print(max_len)

Submission status: Accepted

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

#迷路の作成
graph = [list(input()) for i in range(H)]
#迷路と同じ形の何もない空間を作成
ans = 0
for i in range(H):
    for j in range(W):
        costs = []
        for l in range(H):
            costs.append([-1] * W)
        sy = i
        sx = j
        if graph[sy][sx] == "#":
            continue
        costs[sy][sx] = 0
        q = [[sy, sx]]
        #移動方向
        di = [1, -1, 0, 0]
        dj = [0, 0, -1, 1]

        while len(q) != 0:
            y, x = q.pop(0)

            for k in range(4):
                t = y + di[k]
                u = x + dj[k]
                if not (0<=t<H and 0<=u<W):
                    continue
                if graph[t][u] == '#':
                    continue
                if costs[t][u] != -1:
                    continue
                costs[t][u] = costs[y][x] + 1
                q.append([t, u])
        ans = max(ans, max([max(d) for d in costs]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
INF = 1e9
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(sy,sx):
  if wall[sy][sx] == "#":
    return 0
  que = deque()
  que.append((sy,sx))
  d[sy][sx] = 0
  m = 0
  
  while len(que) > 0:
    y, x = que.popleft()
    
    for i in range(4):
      ny = y+dy[i]
      nx = x+dx[i]
      if 0 <= ny and ny < h and 0 <= nx and nx < w and wall[ny][nx] != "#" and d[ny][nx] == INF:
        que.append((ny,nx))
        d[ny][nx] = d[y][x]+1
        m = max(d[ny][nx],m)
  return m
     
    
h, w = map(int, input().split())
wall = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
  for j in range(w):
    d = [[INF]*w for _ in range(h)]
    a = bfs(i,j)
    ans = max(ans,a)
print(ans)

Submission status: Accepted

Solution code:
import queue

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


def bfs():
    max_dist = 0
    while not que.empty():
        pos = que.get()
        for y, x in zip(dy, dx):
            ty = pos[0] + y
            tx = pos[1] + x
            if ty < 0 or H <= ty:
                continue
            if tx < 0 or W <= tx:
                continue
            if visited[ty][tx]:
                continue
            if S[ty][tx] == "#":
                continue
            que.put((ty, tx, pos[2] + 1))
            visited[ty][tx] = True
            max_dist = max(max_dist, pos[2] + 1)
    return max_dist


H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append([c for c in input()])
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == "#":
            continue
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[sy][sx] = True
        que = queue.Queue()
        que.put((sy, sx, 0))
        ans = max(ans, bfs())
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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

    def bfs(i, j):
        dist = [[-1 for _ in range(W)] for _ in range(H)] # dist to each node
        dist[i][j] = 0
        q = deque([(i, j)])
        max_d = 0

        while q:
            i, j = q.popleft()
            max_d = max(max_d, dist[i][j])
            if i+1 < H and maze[i+1][j] == '.' and dist[i+1][j] == -1:
                q.append((i+1, j))
                dist[i+1][j] = dist[i][j] + 1
            if i-1 >= 0 and maze[i-1][j] == '.' and dist[i-1][j] == -1:
                q.append((i-1, j))
                dist[i-1][j] = dist[i][j] + 1
            if j+1 < W and maze[i][j+1] == '.' and dist[i][j+1] == -1:
                q.append((i, j+1))
                dist[i][j+1] = dist[i][j] + 1
            if j-1 >= 0 and maze[i][j-1] == '.' and dist[i][j-1] == -1:
                q.append((i, j-1))
                dist[i][j-1] = dist[i][j] + 1

        return max_d
   
    ret = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                ret = max(ret, bfs(i, j))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
import queue
 
H, W = map(int, input().split())
road_grid = list()
for _ in range(H):
  road_grid.append(input())

# for each start point, find the furthest travellable point
# then return largest path length of all these
# ps y is down, x is right
furthest_so_far = -1
for y_init, x_init in product(range(H), range(W)):
    if road_grid[y_init][x_init] == "#": continue
    boundary = queue.Queue()
    boundary.put((y_init, x_init))
    steps_taken = [[-1]*W for _ in range(H)]
    steps_taken[y_init][x_init] = 0
    while not boundary.empty():
        y, x = boundary.get()
        neighbours = [(y+1, x), (y, x+1), (y-1, x), (y, x-1)]
        for (new_y, new_x) in neighbours:
            if (0 <= new_y < H and 0 <= new_x < W
                and steps_taken[new_y][new_x] == -1 and road_grid[new_y][new_x] == "."):
                steps_taken[new_y][new_x] = steps_taken[y][x] + 1
                boundary.put((new_y, new_x))
    furthest_here = max(max(row) for row in steps_taken)
    furthest_so_far = max(furthest_so_far, furthest_here)
print(furthest_so_far)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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

    # BFS is better-suited for distances from a given node

    def bfs(i, j):
        dist = [[-1 for _ in range(W)] for _ in range(H)] # dist to each node
        dist[i][j] = 0
        q = deque([(i, j)])

        while q:
            i, j = q.popleft()
            if i+1 < H and maze[i+1][j] == '.' and dist[i+1][j] == -1:
                q.append((i+1, j))
                dist[i+1][j] = dist[i][j] + 1
            if i-1 >= 0 and maze[i-1][j] == '.' and dist[i-1][j] == -1:
                q.append((i-1, j))
                dist[i-1][j] = dist[i][j] + 1
            if j+1 < W and maze[i][j+1] == '.' and dist[i][j+1] == -1:
                q.append((i, j+1))
                dist[i][j+1] = dist[i][j] + 1
            if j-1 >= 0 and maze[i][j-1] == '.' and dist[i][j-1] == -1:
                q.append((i, j-1))
                dist[i][j-1] = dist[i][j] + 1

        return max(max(i) for i in dist)
   
    ret = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                ret = max(ret, bfs(i, j))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
field = [input() for _ in range(H)]
MOVE = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def dfs(h, w):
    q = deque([(0, (h, w))])
    visited = [[-1] * W for _ in range(H)]
    count = -1
    
    while q:
        count, (y, x) = q.popleft()
        # 訪問済みならskip
        if visited[y][x] != -1:
            continue
        # 訪問済みにする
        visited[y][x] = count

        for a, b in MOVE:
            next_x = x + a
            next_y = y + b
            # グリッドの外ならskip
            if next_x < 0 or next_x >= W or next_y < 0 or next_y >= H:
                continue
            # 訪問済みならskip
            if visited[next_y][next_x] != -1:
                continue
            # # 壁ならskip
            if field[next_y][next_x] == '#':
                continue
            q.append((count + 1, (next_y, next_x)))
    return count


def solve():
    ans = 0
    for h in range(H):
        for w in range(W):
            if field[h][w] == '#':
                continue
            count = dfs(h, w)
            ans = max(ans, count)
    return ans

print(solve())

Submission status: Accepted

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

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            q=queue.Queue()
            d=0
            q.put([i,j])
            x[i][j]=0
            while q.qsize()!=0:
                d+=1
                l=q.qsize()
                for t in range(l):
                    I,J=q.get()
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))

Submission status: Accepted

Solution code:
import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]
        route[h][w] = 0

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()

            for dx,dy in zip(dxs, dys):
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]!=-1:
                    continue
                route[y][x] = nn + 1
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    #print(l)
    if s[k][l]=="#":
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)
#print(wf)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def f(i, j):
    global H, W, S
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


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

    result = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != '#':
                result = max(result, f(i, j))
    print(result)


if __name__ == "__main__":

    main()

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
field_org = [-1] * (W * H)
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = deque()
        q.append((i, j, 0))
        field = copy(field_org)
        field[j * W + i] = 0
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                f_idx = y * W + x
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[f_idx] != -1:
                    continue
                field[f_idx] = p[2] + 1
                q.append((x, y, p[2] + 1))
        cand.append(max(field))
print(max(cand))

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
field_org = [[-1] * W for _ in range(H)]
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = deque()
        q.append((i, j, 0))
        field = deepcopy(field_org)
        field[j][i] = 0
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                field[y][x] = p[2] + 1
                q.append((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))

Submission status: Accepted

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = deque()
        q.append((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        field[j][i] = 0
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                field[y][x] = p[2] + 1
                q.append((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))

Submission status: Accepted

Solution code:
import queue
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        field[j][i] = 0
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                field[y][x] = p[2] + 1
                q.put((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))

Submission status: Accepted

Solution code:
import collections as cl
def check(y,x):
    if 0 <= x and x < w and 0 <= y and y < h :
        return True
    else:
        return False

def func():
    while q:
        y,x,count= q.popleft()
        if check(y,x) == False or s[y][x] == '#' or (y,x) in conf:
            continue
        else:
            q.append([y-1,x,count+1])
            q.append([y+1,x,count+1])
            q.append([y,x-1,count+1])
            q.append([y,x+1,count+1])
            ans.append(count)
            conf.add((y,x))
    return max(ans)
q = cl.deque()
conf = set()
h,w = map(int,input().split())
s = []
step_max = []
for i in range(h):
    s.append(list(map(str,input())))
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            q.append([i,j,0])
            step_max.append(func())
            conf = set()
            ans = []
print(max(step_max))