Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Accepted

Solution code:
import queue

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

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

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

def bfs(i,j):
    max_d=0
    q=queue.Queue()
    q.put((i,j))
    d=[[0]*W for _ in range(H)]
    while not q.empty():
        loc=q.get()
        for k in range(len(dx)):
            x=loc[1]+dx[k]
            y=loc[0]+dy[k]
            if x>=0 and x<W and y>=0 and y<H:
                if S[y][x]==".":
                    if d[y][x]==0 and not(x==j and y==i):
                        q.put((y,x))
                        d[y][x]=d[loc[0]][loc[1]]+1
                        max_d=max(max_d,d[y][x])
    return max_d

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

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
s_list=[['#' for _ in range(w+2)]]
for i in range(h):
    s_list.append(['#'] + list(input()) + ['#'])
s_list.append(['#' for _ in range(w+2)])



def bfs(x, y):
    temp_maps =  [[None if s == '.' else -1 for s in s_row] for s_row in s_list]
    temp_maps[x][y] = 0
    que = deque()
    que.append((x,y))
    while que:
        i, j = que.popleft()
        for val_added_i, val_added_j in ((0,1),(0,-1),(1,0),(-1,0)):
            if temp_maps[i + val_added_i][j + val_added_j] is None:
                temp_maps[i + val_added_i][j + val_added_j] = temp_maps[i][j] + 1
                que.append((i + val_added_i, j + val_added_j))
    return max(max(maps_row)  for maps_row in temp_maps)


max_value = 0

for i in range(1, h+1):
    for j in range(1, w+1):
        if s_list[i][j] == '.':
            val = bfs(i, j)
            max_value = max(max_value, val)

print(max_value)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = -1
direc = [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(start):
  Dis = [[INF]*W for _ in range(H)]
  Dis[start[0]][start[1]]=0
  q = deque([])# スタック
  q.append(start)
  r = 0
  while len(q)!=0:
    h,w = q.popleft()# スタック取りだし（先頭）
    
    for d in direc:
      hs, ws = h + d[0], w + d[1]
      if not (0<=hs<H and 0<=ws<W):
        continue
      if Gd[hs][ws]=='.' and Dis[hs][ws]==INF:
          q.append([hs,ws])
          Dis[hs][ws] = Dis[h][w] + 1
          r = max(Dis[hs][ws],r)
  return r
ans = INF
for h in range(H):
  for w in range(W):
    if Gd[h][w]=='.':
      ans = max(ans,dfs([h,w]))
print(ans)

Submission status: Accepted

Solution code:
def grid_bfs():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    from collections import deque
    dire = ((0, -1), (-1, 0), (1, 0), (0, 1))
    def bfs(sx, sy):
        dist = [[-1]*W for _ in range(H)] # 未訪問は-1,訪問済みは距離
        dist[sx][sy] = 0
        que = deque([(sx, sy)]) # (sx, sy)からスタート
        while que:
            x, y = que.popleft()
            d = dist[x][y]
            for dx, dy in dire:
                nx,ny = x+dx,y+dy
                # 内部で、通行可能('.')で、未訪問なら距離を更新し、dequeに入れる
                if 0<=nx<H and 0<=ny<W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                    dist[nx][ny] = d+1
                    que.append((nx, ny))
        return max(map(lambda x: max(x), dist)) # これは(sx,sy)からの最長距離



    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                ans = max(ans, bfs(i, j))
    print(ans)

grid_bfs()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

nei = []
ans = 0
color = []

def dfs(i, fr, hop):
    global nei, color, ans
    ans = max(ans, hop)
    color[i] = 1
    for k in nei[i]:
        if k != fr and color[k] == -1:
            dfs(k, i, hop+1)

def dijkstra(n, start, nbl):
    """n: 頂点数, start: 始点, nbl: 隣接リスト"""
    import heapq
    WHITE = 1<<5
    GRAY = 1<<10
    BLACK = 1<<15
    INF = 1<<20
    color = [WHITE] * n
    distance = [INF] * n
    # parent = [-1] * n
    q = []

    distance[start] = 0
    heapq.heappush(q, (0, start))
    while len(q) != 0:
        du, u = heapq.heappop(q)
        # print("u: {}, du: {}".format(u, du))
        color[u] = BLACK
        if distance[u] < du:
            continue
        for next, cost in nbl[u]:
            if color[next] != BLACK and distance[u] + cost < distance[next]:
                distance[next] = distance[u] + cost
                color[next] = GRAY
                heapq.heappush(q, (distance[next], next))
    for i, v in enumerate(distance[:]):
        if v == INF:
            distance[i] = -1
    return distance

def main():
    global nei, color
    h, w = list(map(int, input().strip().split()))
    G = [0] * h
    nei = [[] for _ in range(w*h)]
    color = [-1] * (w*h)
    for i in range(h):
        G[i] = input().strip()
    for i in range(h):
        for j in range(w):
            if G[i][j] == '.':
                if i != 0 and G[i-1][j] == '.':
                    nei[w*i+j].append((w*(i-1)+j, 1))
                if i != h-1 and G[i+1][j] == '.':
                    nei[w*i+j].append((w*(i+1)+j, 1))
                if j != 0 and G[i][j-1] == '.':
                    nei[w*i+j].append((w*i+j-1, 1))
                if j != w-1 and G[i][j+1] == '.':
                    nei[w*i+j].append((w*i+j+1, 1))
    ans = 0
    for i in range(h):
        for j in range(w):
            if G[i][j] == '.':
                # print(dijkstra(w*h, w*i+j, nei))
                ans = max(max(dijkstra(w*h, w*i+j, nei)), ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

start = []
for i in range(h):
    for j in range(w):
        if s[i][j:j+1] == ".":
            start.append([i,j])
#print(start)

def meiro(ss,count):
    if len(ss) == 0:
  #      for i in range(h):
  #          print(jokyo[i])
  #      print()
        global ans
        ans = max(ans,count-1)
    else:
        kouho = [[0,1],[0,-1],[1,0],[-1,0]]
        next_s = []
        for hw in ss:
            for i in range(4):    
                next_w = hw[1]+kouho[i][1]
                next_h = hw[0]+kouho[i][0]
                if next_w < w and next_w >= 0:
                    if next_h < h and next_h >= 0:
                        if s[next_h][next_w:next_w+1] == "." and jokyo[next_h][next_w] == -1:
                            next_s.append([next_h,next_w])
                            jokyo[next_h][next_w] = count + 1
        meiro(next_s,count+1)

ans = 0
for i in range(len(start)):
    jokyo = [[-1 for i in range(w)] for j in range(h)]
    jokyo[start[i][0]][start[i][1]] = 0
    meiro([start[i]],0)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

#Start(sx, sy)から各頂点への最短距離を求める

def bfs(sx, sy):
    cnt = 0
    f_inf = float('inf')
    dist = [[f_inf] * m for _ in range(n)]

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

    #Start地点を0にする
    que = deque([])
    que.append((sx, sy))
    dist[sx][sy] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            #移動した点を(nx, ny)とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            #移動可能かと既に訪れたかの判定
            #dist[nx][ny] != f_infなら既に訪れた
            if n > nx >= 0 and \
               m > ny >= 0 and \
               s[nx][ny] != '#' and \
               dist[nx][ny] == f_inf:
                que.append((nx, ny))
                dist[nx][ny] = dist[p[0]][p[1]] + 1
                cnt = dist[nx][ny]

    return cnt


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

ans = 0
for i in range(n):
    for j in range(m):
        if s[i][j] == '#':
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

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


class node():
    def __init__(self):
        self.wall = 0
        self.reaf = []
        self.tansaku = 0
        self.cost = 0


nodelist = [node() for i in range(H * W)]
count = 0
for i in range(len(mp)):
    for j in range(len(mp[i])):
        if mp[i][j] == "#":
            nodelist[count].wall = 1
        count += 1
count2 = 0
for i in range(len(nodelist)):

    if count2 != 0:
        if nodelist[i-1].wall == 0:
            nodelist[i].reaf.append(i-1)
    if count2 != W-1:
        if nodelist[i+1].wall == 0:
            nodelist[i].reaf.append(i+1)
    if i+W < len(nodelist):
        if nodelist[i+W].wall == 0:
            nodelist[i].reaf.append(i+W)
    if i-W >= 0:
        if nodelist[i-W].wall == 0:
            nodelist[i].reaf.append(i-W)

    count2 += 1
    if count2 == W:
        count2 = 0

def tansaku(nodelist,que):
    data = que.popleft()
    for j in nodelist[data].reaf:
        if nodelist[j].tansaku == 0:
            que.append(j)
            nodelist[j].tansaku = 1
            nodelist[j].cost = nodelist[data].cost + 1
    if len(que) != 0:
        tansaku(nodelist, que)


def nodereset(nodelist):
    for i in range(len(nodelist)):
        nodelist[i].tansaku = 0
        nodelist[i].cost = 0
    return nodelist

maxnum = 0

for i in range(len(nodelist)):
    if nodelist[i].wall == 0:
        nodelist = nodereset(nodelist)
        que = deque()
        que.append(i)
        nodelist[i].tansaku = 1
        tansaku(nodelist, que)
        for j in range(len(nodelist)):
            if nodelist[j].cost > maxnum:

                maxnum = nodelist[j].cost
print(maxnum)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a) - 1
b = ['#'] * w
q = deque()
d = -1, 1, -w - 1, w + 1
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in d:
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a) - 1
b = ['#'] * w
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q = deque([i])
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
q = deque()
d = -1, 1, -w - 1, w + 1
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in d:
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q = deque([i])
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (-1, 1, -w - 1, w + 1):
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
w += 1
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[: 1 - w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (-1, 1, -w, w):
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q = deque([i])
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (i - 1, i + 1, i - w - 1, i + w + 1):
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

h,w = map(int,readline().split())
#壁を作りたいから、行と列に２ずつ足していく。
h += 2;w += 2
#壁を作成
grid = '#' * w
#_はとくに気にしなくてもいい　iと一緒
for _ in range(h - 2):
    #rstrip()末尾の空白を削除する
    grid += '#' + readline().rstrip().decode() + '#'
    #一列に壁と情報を足している
grid += "#" * w

def bfs(start):
    INF = 10**9
    dist = [INF] * ( h * w )
    dist[start] = 0
    queue = deque([start])
    while queue:
        v = queue.popleft()
        dv = dist[v]
        for move in (-1,1,w,-w):
            W = v + move
            if grid[W] == "#":
                continue
            dw = dv + 1
            if dw >= dist[W]:
                continue
            dist[W] = dw
            queue.append(W)
    return max(x for x in dist if x < INF)

#スタート位置をbfsに入れている
answer = max(bfs(v) for v in range(h*w) if grid[v] != "#")
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "#" else 0 for a in input()] + [1]
X += [1] * (W + 2)
H, W = H+2, W+2
 
def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for y in (x+W, x-W, x+1, x-1):
            if X[y] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append(y)
    return D
 
ma = 0
for i in range(H):
    for j in range(W):
        if X[i*W+j] == 0:
            ma = max(ma, max(BFS(i*W+j)))
print(ma)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "#" else 0 for a in input()] + [1]
X += [1] * (W + 2)
H, W = H+2, W+2

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for y in (x+W, x-W, x+1, x-1):
            if X[y] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append(y)
    return D

ma = 0
for i in range(H):
    for j in range(W):
        if X[i*W+j] == 0:
            ma = max(ma, max(BFS(i*W+j)))
print(ma)

Submission status: Accepted

Solution code:
#input
H, W = map(int, input().split())
import numpy as np
S = [input() for _ in range(H)]

#output
import numpy as np

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

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

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

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int, input().split())
PATH = "."
WALL = "#"
z=0
# 迷路の配列を作成する。
maze=list()
for a in range(h):
 mazew=list()
 mazeh = input()
 for b in range(w):
  mazew.append(mazeh[b])
 maze.append(mazew)
for c in range(h):
 for d in range(w):
   # 地図上の未訪問地点を-1とする。
   # また、移動するごとに+1することで、スタート地点からの移動距離を保持する
  if maze[c][d]==WALL:
   continue
  else:
   distance_visited = list()
   for l in range(h):
    distance_visited.append([-1] * w)
   # スタート地点を登録する。
   queue = deque([[c, d]])
   distance_visited[c][d] = 0
   while True:
    x,y = queue.popleft()
      # 現在地点の上下左右のマスを確認する。
    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
     new_x, new_y = x + i, y + j
       # それぞれのマスが移動できる場合、かつまだ移動したことが無い場合
     if new_x>=0 and new_x<=h-1 and new_y>=0 and new_y<=w-1:
      if maze[new_x][new_y] != WALL and distance_visited[new_x][new_y] == -1:
               # そのマスのスタートからの移動距離を設定し、またキューに登録する。
       distance_visited[new_x][new_y] = distance_visited[x][y] + 1
       queue.append([new_x, new_y])
       if distance_visited[new_x][new_y]>z:
        z=distance_visited[new_x][new_y]
    if queue==deque([]):
     break
print(z)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
a = [input() + '#' for _ in range(h)]
b = ['#' * (w + 1)]
r = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '.':
      b[:-1] = map(list, a)
      b[i][j] = 0
      q = deque([(i, j)])
      while(q):
        i, j = q.popleft()
        r = max(r, b[i][j])
        d = 0
        for i1 in range(i - 1, i + 2):
          for j1 in range(j - d, j + 2, 2):                
            if b[i1][j1] == '.':
              b[i1][j1] = b[i][j] + 1
              q.append((i1, j1))
          d ^= 1
print(r)

Submission status: Accepted

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

r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    f[i*w+j] =0
    while que:
        i,j,k = que.popleft()
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        f[ti*w+tj] = k+1
                        que.append([ti,tj,k+1])
    return max(f)


res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            tres = bfs(i,j)
            res = max(res,tres)
print(res)

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
S = []
for i in range(H):
    S.append(input())

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

def BFS(i,j,que):
    count = 0
    for k in range(4):
        row = i + di[k]
        col = j + dj[k]
        if H > row >=0 and W >col >= 0 \
            and dist[row][col] == float('inf')\
                and S[row][col] != "#":
            
            que.append([row,col])
            dist[row][col] = dist[i][j] + 1
            count = dist[row][col]
    return count


path_max = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        que = []
        stt = [i,j]
        que.append(stt)
        dist = [[float('inf') for ii in range(W)] for jj in range(H)]
        dist[i][j] = 0
        while que:
            idx = que[0]
            que.pop(0)
            count  = BFS(idx[0],idx[1],que)
            path_max = max(path_max,count)

print(path_max)

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
A = [list(input()) for i in range(H)]

#from queue import Queue #キューを使ったら1ケースだけTLEになった。
from collections import deque

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

sum_sharp = sum([A[i].count('#') for i in range(H)])

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        d_max = 0
        #q_i = Queue()
        q_i = deque()
        #q_j = Queue()
        q_j = deque()
        D = [[-1]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            #q_i.put(s_i)
            q_i.append(s_i)
            #q_j.put(s_j)
            q_j.append(s_j)
            #while q_i.empty() == False:
            while len(q_i)!=0:
                #i = q_i.get()
                i = q_i.popleft()
                #j = q_j.get()
                j = q_j.popleft()
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or D[ni][nj]!=-1:
                        continue
                    else:
                        flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        #q_i.put(ni)
                        q_i.append(ni)
                        #q_j.put(nj)
                        q_j.append(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
#A = [list(map(str,input().split())) for i in range(H)]
A = [list(input()) for i in range(H)]

#from queue import Queue
#from collections import deque

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

sum_sharp = sum([A[i].count('#') for i in range(H)])

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        #print(s_i,s_j)
        d_max = 0
        q_i = []
        #q_i = Queue()
        #q_i = deque()
        q_j = []
        #q_j = Queue()
        #q_j = deque()
        D = [[-1]*W for i in range(H)]
        #flag = [[0]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            #q_i.put(s_i)
            q_i.append(s_i)
            #q_j.put(s_j)
            q_j.append(s_j)
            #while sum(map(sum, flag)) != W*H - sum_sharp:
            #while flag < W*H - sum_sharp:
            #while q_i.empty() == False:
            while len(q_i)!=0:
            #for a in range(W*H):
                #i = q_i.get()
                i = q_i.pop(0)
                #i = q_i.popleft()
                #j = q_j.get()
                j = q_j.pop(0)
                #j = q_j.popleft()
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    #if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or 0<=D[ni][nj]<D[i][j]+1:
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or D[ni][nj]!=-1:
                    #if ni<0 or ni>=H or nj<0 or nj>=W:
                        continue
                    #elif A[ni][nj]== '#' or D[ni][nj] < D[i][j]+1:
                        #flag[ni][nj] = 1
                        #continue
                    else:
                        #if D[ni][nj] == -1:
                            #print(flag)
                        flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        #q_i.put(ni)
                        q_i.append(ni)
                        q_j.append(nj)
                        #q_j.put(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
a = ['#' + input() + '#' for _ in range(h)]
b = ['#' * (w + 1)] * 2
r = 0
for i in range(1, h + 1):
  for j in range(1, w + 1):
    if a[i - 1][j] == '.':
      b[1: -1] = map(list, a)
      b[i][j] = 0
      q = deque([(i, j)])
      while(q):
        i, j = q.popleft()
        r = max(r, b[i][j])
        d = 0
        for i1 in range(i - 1, i + 2):
          for j1 in range(j - d, j + 2, 2):                
            if b[i1][j1] == '.':
              b[i1][j1] = b[i][j] + 1
              q.append((i1, j1))
          d ^= 1
print(r)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
M=[]
for i in range(h):
    s=input()
    H=[]
    for j in range(w):
        H.append(0) if s[j]=="." else H.append(1)
    M.append(H)

def make2D(x,y):
    aM=[]
    for i in range(h):
        aH=[]
        for j in range(w):
            aH.append(0) if M[i][j]==0 else aH.append(-1)
        aM.append(aH)
    return aM

from collections import deque
ans=0
for i in range(h):
    for j in range(w):
        if M[i][j]==1:
            continue
        aM=make2D(h,w)
        q=deque()
        q.append([i,j])
        while q:
            now=q.popleft()
            for a,b in ([0,1],[1,0],[0,-1],[-1,0]):
                if 0<=now[0]+a<h and 0<=now[1]+b<w:
                    if aM[now[0]+a][now[1]+b]==0 and (now[0]+a!=i or now[1]+b!=j):
                        aM[now[0]+a][now[1]+b]=aM[now[0]][now[1]]+1
                        q.append([now[0]+a,now[1]+b])
            if len(q)==0:
                break
        m=0
        for z in range(h):
            m=max(m,max(aM[z]))
        ans=max(ans,m)
print(ans)

Submission status: Accepted

Solution code:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

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

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1
g = gridMan(S)
g.makeWall()
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == 0:
      ans = max(ans, g.dist([i, j])[1])

print(ans)

Submission status: Accepted

Solution code:
import sys
from queue import Queue


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_y in range(H):
        for start_x in range(W):
            if S[start_y][start_x] == '#':
                continue
            costs = [[0 for w in range(W)] for h in range(H)]
            costs[start_y][start_x] = 1
            queue = Queue()
            queue.put((start_y, start_x))
            cost = 1
            while not queue.empty():
                (y, x) = queue.get()
                # print("({},{}): {}".format(y, x, c))
                for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if 0 <= next_y < H and 0 <= next_x < W and S[next_y][next_x] == '.' and costs[next_y][next_x] == 0:
                        costs[next_y][next_x] = costs[y][x] + 1
                        if cost < costs[next_y][next_x]:
                            cost = costs[next_y][next_x]
                        queue.put((next_y, next_x))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def f(i, j):
   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)

result = 0
for i in range(h):
   for j in range(w):
      if s[i][j] != '#':
         result = max(result, f(i, j))
print(result)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

INF = 1001001001
dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

ans = 0
for i, j in product(range(H), range(W)):
    if S[i][j] == '#':
        continue
    d = [[INF] * W for i in range(H)]
    d[i][j] = 0
    q = deque([(i, j)])
    while len(q) > 0:
        x, y = q.popleft()
        for dx, dy in dr:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '#' and d[nx][ny] == INF:
                d[nx][ny] = d[x][y] + 1
                ans = max(d[nx][ny], ans)
                q.append((nx, ny))
print(ans)