Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def bfs(start):
    que=deque([start])
    D=[-1]*(h*w)
    D[start]=0
    while que:
        x=que.popleft()
        for next_x in (x+1,x-1,x+w,x-w):
            if maze[next_x]=='.' and D[next_x]==-1:
                D[next_x]=D[x]+1
                que.append(next_x)
    return max(D)

def main():
    global h,w,maze
    h,w=map(int,input().split())
    h+=2
    w+=2
    maze="#"*w
    for _ in range(h-2):
        maze+="#"+input()+"#"
    maze+="#"*w 
    print(max(bfs(i) for i,c in enumerate(maze) if c=='.'))


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(meiro, start_x, start_y):
    visited = []
    for i in range(len(meiro)):
        visited.append([])
        for j in range(len(meiro[i])):
            visited[i].append(0)

    stack = deque()
    stack.append([start_x, start_y])
    visited[start_x][start_y] = 0
    max_distance = 0
    while len(stack) != 0:
        x, y = map(int, stack.popleft())
        distance = visited[x][y]
        for items in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
            x_n = x + items[0]
            y_n = y + items[1]
            if x_n < 0 or x_n >= H or y_n < 0 or y_n >= W or (start_x == x_n and start_y == y_n) or visited[x_n][y_n] != 0 or meiro[x_n][y_n] == "#":
                continue
            stack.append([x_n, y_n])
            visited[x_n][y_n] = distance+1
            if max_distance < distance+1:
                max_distance = distance+1
    return max_distance

H, W = map(int, input().split())
meiro = []
for h in range(H):
    meiro.append(list(input()))

max_dist = 0
for h in range(H):
    for w in range(W):
        if meiro[h][w] == ".":
            dis = bfs(meiro, h, w)
            if max_dist < dis:
                max_dist = dis
print(max_dist)

Submission status: Accepted

Solution code:
from collections import deque

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

ret = 0
for i in range(H):
    for j in range(W):
        s = S[i][j]
        queue = deque([(i,j,0)])
        footprint = [(i,j)]
        if s == '#':
            continue
        while True:
            x, y, d = queue.popleft()
            for p in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if p[0] < 0 or p[0] >= H or p[1] < 0 or p[1] >= W:
                    continue
                if p in footprint:
                    continue
                if S[p[0]][p[1]] == '#':
                    continue
                queue.append((p[0], p[1], d+1))
                footprint.append(p)

            if len(queue) == 0:
                break
        if d > ret:
            ret = d

print(ret)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
 
ans=0

for sh in range(H):
  for sw in range(W):
    if G[sh][sw]=="#":
      continue
      
    dist=[[-1]*W for _ in range(H)]
    dist[sh][sw]=0
    #二重[]に注意
    que=deque([[sh,sw]])
    
    while que:
      nh,nw=que.popleft()
      
      for dh,dw in directions:
        
        # 迷路からはみ出す
        if not 0<=nh+dh<=H-1 or not 0<=nw+dw<= W-1:
          continue
         
        # 移動先が通れないマス
        if G[nh+dh][nw+dw]== "#":
          continue
        
        # 探索済み
        if dist[nh+dh][nw+dw]!=-1:
          continue
          
        dist[nh+dh][nw+dw]=dist[nh][nw]+1
        que.append([nh+dh,nw+dw])
      
    ans=max(ans, max([max(d) for d in dist]))
    
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [readline().rstrip().decode() for _ in range(h)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
sg = []
memo = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sg.append((i, j))
        else:
            memo[i][j] = True
ans = 0
for ss in sg:
    q = [ss]
    cnt = 0
    dist = deepcopy(memo)
    dist[ss[0]][ss[1]] = True
    while q:
        cnt += 1
        qq = []
        for y, x in q:
            for dy, dx in move:
                xx, yy = x + dx, y + dy
                if xx < 0 or yy > h - 1 or yy < 0 or xx > w - 1:
                    continue
                if dist[yy][xx]:
                    continue
                dist[yy][xx] = True
                qq.append((yy, xx))
        q = qq
    ans = max(ans, cnt - 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

from sys import stdin, setrecursionlimit


def main():
    h, w = map(int, stdin.readline().split())
    g = [list(map(str, list(input()))) for _ in range(h)]

    ans = 0

    for i in range(h):
        for j in range(w):
            if g[i][j] == '.':
                d = [[-1 for _ in range(w)] for _ in range(h)]
                q = deque()

                d[i][j] = 0
                q.append([i, j])

                while q:
                    vi, vj = q.popleft()

                    if vi > 0:
                        if g[vi - 1][vj] == '.' and d[vi - 1][vj] == -1:
                            d[vi - 1][vj] = d[vi][vj] + 1
                            q.append([vi - 1, vj])
                    if vi < h - 1:
                        if g[vi + 1][vj] == '.' and d[vi + 1][vj] == -1:
                            d[vi + 1][vj] = d[vi][vj] + 1
                            q.append([vi + 1, vj])
                    if vj > 0:
                        if g[vi][vj - 1] == '.' and d[vi][vj - 1] == -1:
                            d[vi][vj - 1] = d[vi][vj] + 1
                            q.append([vi, vj - 1])
                    if vj < w - 1:
                        if g[vi][vj + 1] == '.' and d[vi][vj + 1] == -1:
                            d[vi][vj + 1] = d[vi][vj] + 1
                            q.append([vi, vj + 1])
                tmp_max = 0
                for hi in range(h):
                    for wj in range(w):
                        tmp_max = max(tmp_max, d[hi][wj])
                ans = max(ans, tmp_max)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [input() for i in range(h)]
def bfs(i0, j0):
    INF = 100
    search = deque([(i0, j0)])
    d = [[INF] * w for i in range(h)]
    d[i0][j0] = 0
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and d[ni][nj] == INF:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_d = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            max_dij = bfs(i, j)
            max_d = max(max_d, max_dij)
print(max_d)

Submission status: Accepted

Solution code:
h , w = input().split()
h , w = int(h) , int(w)

mp = [ '' for j in range(w * h)]
j = 0

for i in range (h) :
    tmp1 = list(input())
    for j in range (w) :
        mp[w * i + j] = tmp1[j]

def bfs (k) :
    used = [False for i in range(h * w)]
    q = [k]
    used[k] = True
    depth = [0 for i in range (h * w)]

    while len(q) > 0 :
        tmp = q.pop(0)
        if tmp > w - 1 and mp[tmp - w] == '.' and used[tmp - w] == False:
            q.append (tmp - w)
            used[tmp - w] = True
            depth [tmp - w] = depth[tmp] + 1

        if tmp < (h - 1) * w and mp[tmp + w] == '.' and used[tmp + w] == False :
            q.append (tmp + w)
            used[tmp + w] = True
            depth [tmp + w] = depth[tmp] + 1

        if tmp % w != 0 and mp[tmp - 1] == '.' and used[tmp - 1] == False :
            q.append (tmp - 1)
            used[tmp - 1] = True
            depth [tmp - 1] = depth[tmp] + 1

        if (tmp + 1) % w != 0 and mp[tmp + 1] == '.'and used[tmp + 1] == False :
            q.append (tmp + 1)
            used[tmp + 1] = True
            depth [tmp + 1] = depth[tmp] + 1
    
    mx = max(depth)

    return mx

ans = 0 

for i in range (h * w) :
    if mp[i] == '.' :
        ans = max(ans , bfs(i))

print (ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(h_i, w_i):
    visit = [[0] * w for _ in range(h)]
    visit[h_i][w_i] = 1
    d = deque()
    d.append([h_i, w_i])
    distance = [[0] * w for _ in range(h)]
    while d:
        x, y = d.popleft()
        for i, j in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            if (0 <= x + i <= h - 1) & (0 <= y + j <= w - 1):
                if visit[x + i][y + j] == 0:
                    visit[x + i][y + j] = 1
                    if s[x + i][y + j] == '.':
                        distance[x + i][y + j] = distance[x][y] + 1
                        d.append([x+i, y+j])
    ans = []
    for i in distance:
        ans += i
    return max(ans)

h, w = map(int, input().split())
s = []
for _ in range(h):
    t = list(input())
    s.append(t)
dist = []
for i in range(h * w):
    h_i = i % h
    w_i = i // h
    if s[h_i][w_i] == '.':
        dist.append(bfs(h_i, w_i))
print(max(dist))

Submission status: Accepted

Solution code:
from collections import deque 
INF = 10000

H,W = map(int,input().split())
S = [list(input()) for i in range(0,H,1)]
S_count=[[INF for j in range(0,W,1)]for i in range(0,H,1)]
task_list = deque([])

def bfs(x,y,count):
    if x<0 or H-1 < x or y < 0 or W-1<y:
        return False
    if S[x][y]=="#":
        return False
    if S_count[x][y] > count:
        S_count[x][y]=count
        task_list.append([x+1,y,count+1])
        task_list.append([x-1,y,count+1])
        task_list.append([x,y-1,count+1])
        task_list.append([x,y+1,count+1])
        return True

maxi = 0

for i in range(0,H,1):
    for j in range(0,W,1):
        S_count=[[INF for j in range(0,W,1)]for i in range(0,H,1)]
        task_list.append([i,j,0])
        while(len(task_list)):
            X,Y,T = task_list.popleft()
            if bfs(X,Y,T):
                maxi = max(T,maxi)

print(maxi)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [input() for _ in range(h)]
dires = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            continue        
        q = deque()
        q.append((i, j, 0))
        explored = set()
        explored.add((i, j))
        longest = 0
        while q:
            y, x, count = q.popleft()
            for d, r in dires:
                y_ = y+d
                x_ = x+r
                if (y_, x_) in explored or y_ >= h or x_ >= w or y_ < 0 or x_ < 0 or maze[y_][x_] == "#":
                    continue

                explored.add((y_, x_))
                q.append((y_, x_, count+1))
                longest = max(longest, count+1)

        ans = max(ans, longest)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
array = np.zeros((H * W, H * W), dtype=np.bool)
for n in range(H * W):
    if maze[n] == "#":
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
        array[n - 1][n] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
        array[n - W][n] = 1
dist = csgraph.shortest_path(array)
print(int(dist[dist < 401].max()))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csgraph
H, W = map(int, input().split())
maze = "".join(input() for _ in range(H))
array = np.zeros((H * W, H * W), dtype=np.bool)
for n in range(H * W):
    if maze[n] == "#":
        continue
    r, c = divmod(n, W)
    if c and maze[n - 1] == ".":
        array[n][n - 1] = 1
    if c != W - 1 and maze[n + 1] == ".":
        array[n][n + 1] = 1
    if r and maze[n - W] == ".":
        array[n][n - W] = 1
    if r != H - 1 and maze[n + W] == ".":
        array[n][n + W] = 1
dist = csgraph.shortest_path(array, directed=False)
print(int(dist[dist < 401].max()))

Submission status: Accepted

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

def BFS(i,j):
  v= deque([[i,j]])
  d= [[-1 for _ in range (W)] for _ in range(H)]
  d[i][j]=0
  
  while len(v)>0:
    a=v.popleft()
    s=a[0]
    t=a[1]
    if s>0:
      if d[s-1][t]==-1 and S[s-1][t]==".":
        d[s-1][t]= d[s][t]+1
        v.append([s-1,t])
    if s<H-1:
      if d[s+1][t]==-1 and S[s+1][t]==".":
        d[s+1][t]= d[s][t]+1
        v.append([s+1,t])
    if t>0:
      if d[s][t-1]==-1 and S[s][t-1]==".":
        d[s][t-1]= d[s][t]+1
        v.append([s,t-1])
    if t<W-1:
      if d[s][t+1]==-1 and S[s][t+1]==".":
        d[s][t+1]= d[s][t]+1
        v.append([s,t+1])
  maxi=0
  for i in range(H):
    for j in range(W):
      maxi=max(maxi,d[i][j])
  #print(d)
  return maxi

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(input()))
directions = [[-1,0],[1,0],[0,-1],[0,1]]
ans = []

for j in range(h):
    for k in range(w):
        if ma[j][k] == '#':
            continue

        bfs = [[-1]*w for _ in range(h)]
        bfs[j][k] = 0
        que = [[j,k]]

        while len(que)>0:
            s,t = que.pop(0)
            for x,y in directions:
                if s+x < 0 or s+x>=h or t+y<0 or t+y>=w:
                    continue
                if ma[s+x][t+y] == '#':
                    continue
                if bfs[s+x][t+y] != -1:
                    continue
                bfs[s+x][t+y] = bfs[s][t] + 1
                que.append([s+x,t+y])
        
        tmp = 0
        for bf in bfs:
            for b in bf:
                if b>tmp:
                    tmp = b
        ans.append(tmp)
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = []

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

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


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    check[start[0]][start[1]] = True
    queue = deque([start])
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.popleft()

        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        for p in move:
            next_x = x + p[0]
            next_y = y + p[1]
            if (next_x < 0)or(next_x == h)or(next_y < 0)or(next_y == w):
                continue
            if not check[next_x][next_y]:
                check[next_x][next_y] = True
                if maze[next_x][next_y] == ".":
                    queue.append([next_x, next_y, x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

moves = [[-1,0], [1,0], [0,-1], [0,1]]



min_val = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        todo = deque([[i,j]])
        
        shortest = [[-10e+10 for _ in range(W)] for _ in range(H)]
        shortest[i][j] = 0
        
        while len(todo) > 0:
            checking = todo.popleft()
            for move in moves:
                if checking[0] + move[0] >= 0 and checking[0] + move[0] < H and checking[1] + move[1] >= 0 and checking[1] + move[1] < W:
                    if shortest[checking[0]+move[0]][checking[1]+move[1]] == -10e+10 and S[checking[0]+move[0]][checking[1]+move[1]] == ".":
                        shortest[checking[0]+move[0]][checking[1]+move[1]] = shortest[checking[0]][checking[1]]+1
                        todo.append([checking[0]+move[0],checking[1]+move[1]])
        if min_val < max([max(row) for row in shortest]):
            min_val = max([max(row) for row in shortest])
print(min_val)

Submission status: Accepted

Solution code:
DIR = ((0, 1), (0, -1), (1, 0), (-1, 0))

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

ans = 0

for i in range (H) :
    for j in range (W) :
        if G[i][j] == '.' :
            use = [[False for ii in range (W)] for jj in range (H)]
            q = [(i, j, 0)]
            use[i][j] = True
            path = 0

            while len (q) :
                node = q.pop(0)
                path = max (path, node[2])
                for k in range (4) :
                    x, y = node[0] + DIR[k][0], node[1] + DIR[k][1]
                    if x < 0 or y < 0 or x >= H or y >= W :
                        continue
                    if use[x][y] or G[x][y] == '#':
                        continue
                    use[x][y] = True
                    q.append((x, y, node[2] + 1))
            ans = max (ans, path)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
import sys
def I(): return int(input())  # '123' -> 123
def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]
def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']
def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

h, w = Is()
maze = LSR(h)

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

    while que:
        py, px = que.popleft()
        for ymove, xmove in move:
            ny = py + ymove
            nx = px + xmove
            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] != '#' and vmaze[ny][nx] == INF:
                vmaze[ny][nx] = vmaze[py][px] + 1
                que.append((ny, nx))

    ret = 0
    for y in range(h):
        for x in range(w):
            if vmaze[y][x] != INF:
                ret = max(ret, vmaze[y][x])
    return ret

ans = 0
for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '#':
            continue
        ans = max(ans, bfs(sy, sx))

print(ans)

Submission status: Accepted

Solution code:
import queue

h, w = map(int, input().split())
s = '#'*(w+2)
for _ in range(h):
    s += '#' + input() +'#'
s += '#'*(w+2)

ans = 0
for i in range((w+2)*(h+2)):
    if s[i] == '#':
        continue
    dist = [10**5]*(w+2)*(h+2)
    dist[i] = 0
    q = queue.Queue()
    q.put(i)
    while not q.empty():
        x = q.get()
        for j in (1, -1, w+2, -w-2):
            if s[j+x] =='#':
                continue
            if dist[j+x] > dist[x] + 1:
                dist[j+x] = dist[x] + 1
                q.put(j+x)
    for k in range((w+2)*(h+2)):
      if dist[k] != 10**5:
        ans = max(ans, dist[k])

print(ans)

Submission status: Accepted

Solution code:
import queue

h, w = map(int, input().split())
s = '#'*(w+2)
for _ in range(h):
    s += '#' + input() +'#'
s += '#'*(w+2)

ans = 0
for i in range((w+2)*(h+2)):
    if s[i] == '#':
        continue
    dist = [10**10]*(w+2)*(h+2)
    dist[i] = 0
    q = queue.Queue()
    q.put(i)
    while not q.empty():
        x = q.get()
        for j in (1, -1, w+2, -w-2):
            if s[j+x] =='#':
                continue
            if dist[j+x] > dist[x] + 1:
                dist[j+x] = dist[x] + 1
                ans = max(ans, dist[j+x])
                q.put(j+x)

print(ans)

Submission status: Accepted

Solution code:
# 2020/05/06
# AtCoder Beginner Contest 151 - D

import copy

# Input
h, w = map(int,input().split())
s = list()
init_s = list('#' * (w+2))
s.append(init_s)

for i in range(h):
    ws = list(input())
    ws.insert(0, '#')
    ws.append('#')
    s.append(ws)

s.append(init_s)

q = list()
rflg = True

max_movecnt = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        wk_s = copy.deepcopy(s)
        
        if s[i][j] == '.':
            wk_s[i][j] = '#'
            init_idx = [i, j]
            q.append(init_idx)
            movecnt = 0
            cntupidx = len(q)
            popcnt = 0
            # BFS
            while(len(q) > 0):
                stidx = q.pop(0)
                popcnt = popcnt + 1
                # North
                if wk_s[stidx[0]-1][stidx[1]] == '.':
                    q.append([stidx[0]-1, stidx[1]])
                    wk_s[stidx[0]-1][stidx[1]] = '#'
                # East
                if wk_s[stidx[0]][stidx[1]+1] == '.':
                    q.append([stidx[0], stidx[1]+1])
                    wk_s[stidx[0]][stidx[1]+1] = '#'
                # South
                if wk_s[stidx[0]+1][stidx[1]] == '.':
                    q.append([stidx[0]+1, stidx[1]])
                    wk_s[stidx[0]+1][stidx[1]] = '#'
                # West
                if wk_s[stidx[0]][stidx[1]-1] == '.':
                    q.append([stidx[0], stidx[1]-1])
                    wk_s[stidx[0]][stidx[1]-1] = '#'

                if popcnt >= cntupidx:
                    movecnt = movecnt + 1
                    cntupidx = len(q)
                    popcnt = 0

            max_movecnt = max(movecnt-1, max_movecnt)

# Output
print(max_movecnt)

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(sx, sy):
    d = [[-1] * W for _ in range(H)]

    que = deque([])
    que.append((sx, sy))
    d[sy][sx] = 0

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

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

            if 0 <= nx < W and 0 <= ny < H and d[ny][nx] == -1 and c[ny][nx] == '.':
                que.append((nx, ny))
                tmp = d[y][x] + 1
                d[ny][nx] = tmp
                res = max(res, tmp)

    return res

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

print(ans)

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  H, W = map(int, input().split())
  graph = [['#'] * (W+2) for _ in range(H+2)]
  for i in range(H):
    S = input()
    for j in range(W):
      graph[i+1][j+1] = S[j]

  def dfs(sx, sy):
    q = deque([(sx, sy)])
    dist = [[-1] * (W+2) for _ in range(H+2)]
    dist[sx][sy] = 0
    s = 0
    while q:
      x, y = q.popleft()
      dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
      for dx, dy in dxy:
        nextx = x+dx
        nexty = y+dy
        if(dist[nextx][nexty] >= 0):
          continue
        if(graph[nextx][nexty] == '#'):
          continue
        dist[nextx][nexty] = dist[x][y] + 1
        q.append((nextx, nexty))
    for i in range(H+2):
      for j in range(W+2):
        if(dist[i][j] >= 0):
          s = max(s, dist[i][j])
    return s

  ans = 0  
  for sx in range(1, H+1):
    for sy in range(1, W+1):
      if(graph[sx][sy] == '.'):
          tmp = dfs(sx, sy)
          ans = max(ans, tmp)
          
  print(ans)
  
main()

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
H, W = map(int, input().split())
maze = [[]for i in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        maze[i].append(S[j])

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = 0
Q = deque()

for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        mazenow = deepcopy(maze)
        Q.clear()
        Q.append((sy, sx))
        mazenow[sy][sx] = 0
        flag = True
        max_maze_now = 0
        while len(Q) > 0:
            y, x = Q.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W):
                    continue
                elif mazenow[ny][nx] == '.':
                    mazenow[ny][nx] = mazenow[y][x] + 1
                    max_maze_now = max(max_maze_now, mazenow[ny][nx])
                    Q.append((ny, nx))
        ans = max(max_maze_now, ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

# 辿り着けないと INF
def bfs(sx, sy):
    ma = 0
    # すべての点を 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()
        # 移動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))
                temp = d[p[0]][p[1]] + 1
                d[nx][ny] = temp
                if temp >= ma:
                  ma = temp
             
    return ma


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

ans = 0
for i in range(n):
  for j in range(m):
    if maze[i][j] != "#":
      a = bfs(i,j)
      if a >= ans:
        ans = a
    
print(ans)

Submission status: Accepted

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

def update(y, x, direction, d, q):
    next_y, next_x = (y + direction[0], x + direction[1])
    if (next_y < 0 or next_y >= H or next_x < 0 or next_x >= W): # 端なら
        return
    if (S[next_y][next_x] == '#') or (d[next_y][next_x] != -1): # 壁か既に訪問状態なら
        return 
    d[next_y][next_x] = d[y][x] + 1
    q.append((next_y, next_x))

def bfs(i, j):
    DIJ = ((-1, 0), (0, -1), (1, 0), (0, 1)) # (y, x):下, 左, 上, 右
    dist = [[-1] * W for _ in range(H)]
    dist[i][j] = 0 #始点は０

    queue = [(i, j)]
    while queue:
        cur_y, cur_x = queue.pop(0)
        for i in range(4):
            update(cur_y, cur_x, DIJ[i], dist, queue)
    return max(max(dd) for dd in dist)
    
max_results = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            max_results = max(bfs(i, j), max_results) 
print(max_results)

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:
H, W = list(map(int, input().split()))
S = [input() for _ in range(H)]

def update(y, x, direction, d, q, end_pos):
    next_y, next_x = (y + direction[0], x + direction[1])
    if (next_y < 0 or next_y >= H or next_x < 0 or next_x >= W): # 端なら
        return end_pos 
    if (S[next_y][next_x] == '#') or (d[next_y][next_x] != -1): # 壁か既に訪問状態なら
        return end_pos
    d[next_y][next_x] = d[y][x] + 1
    q[end_pos] = (next_y, next_x)
    return end_pos + 1
    
def bfs(i, j):
    DIJ = ((-1, 0), (0, -1), (1, 0), (0, 1)) # (y, x):下, 左, 上, 右
    dist = [[-1] * W for _ in range(H)]
    dist[i][j] = 0 #始点は０

    wall_num = sum(ss.count('#') for ss in S)
    queue = [(-1, -1) for _ in range(H * W - wall_num)]
    queue[0] = (i, j)
    queue_end_pos = 1 # 一番後ろの値の+1
    while queue:
        cur_y, cur_x = queue.pop(0)
        queue_end_pos -= 1
        for i in range(4):
            queue_end_pos = \
            update(cur_y, cur_x, DIJ[i], dist, queue, queue_end_pos)
    return max(max(dd) for dd in dist)
    
max_results = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            max_results = max(bfs(i, j), max_results) 
print(max_results)