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:
def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    looked = [[x,y]]
    ans = [0]
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if not (search[i] in looked):
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    looked.append([search[i][0],search[i][1]])
    return ans[-1]

h,w = map(int,input().split())
maze = [["#" for _ in range(w+2)]for p in range(h+2)]
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
if (len(anchor)) == (h*w):
    print(h+w-2)
    exit()
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
 
inf = float('inf')
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0
 
# bfs
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#':
            continue
        dist = [[inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0][0]
            j = q[0][1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '#':
                    continue
                update(ni, nj, dist[i][j] + 1)
         
        for i in range(h):
            for j in range(w):
                if dist[i][j] == inf:
                    continue
                ans = max(ans, dist[i][j])
 
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

inf = float('inf')
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

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

ans = 0

# bfs
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#':
            continue
        dist = [[-inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != -inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0][0]
            j = q[0][1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '#':
                    continue
                update(ni, nj, dist[i][j] + 1)

        # 2次元配列のmax
        dist_max = max(list(map(lambda x: max(x), dist)))
        ans = max(ans, dist_max)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    visited = [[-1]*W for _ in range(H)] 
    q = deque([])
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                visited[i][j] = 0
                q.append([i, j])
                
                dx_dy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
                while q:
                    nx, ny = q.popleft()
                    for k in range(4):
                        x, y = nx + dx_dy[k][0], ny + dx_dy[k][1]
                        if 0 <= x < H and 0 <= y < W and S[x][y] != '#' and visited[x][y] == -1:
                            visited[x][y] = visited[nx][ny] + 1
                            q.append([x, y])
                
                for l in range(H):
                    for m in range(W):
                        ans = max(ans, visited[l][m])
                
                q = deque([])
                visited = [[-1]*W for _ in range(H)] 
                
                
                
    
    print(ans)
                    
                
                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
H,W = map(int,input().split())
maze = list()
q = queue.Queue()
for i in range(H):
   maze.append( [x for x in input()])

maxim = 1
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." :
            maze_score = [[0]*W for k in range(H)]
            maze_score[i][j] = 1
            q.put([i,j])
            
        else :
            continue
        
        while(True):
            if q.empty() :
                if maze_score[x][y] > maxim:
                    maxim = maze_score[x][y]
                break
            [x,y] = q.get()
            
            
            
            
            ##top
            if x != 0:
                if maze_score[x-1][y] ==0 and maze[x-1][y] == ".":
                    maze_score[x-1][y] = maze_score[x][y] +1
                    q.put([x-1,y])
            ##right
            if y+1 != W:
                if maze_score[x][y+1] ==0 and maze[x][y+1] == ".":
                    maze_score[x][y+1] = maze_score[x][y] +1
                    q.put([x,y+1])
            ##bottom
            if x != H-1:
                if maze_score[x+1][y] ==0 and maze[x+1][y] == ".":
                    maze_score[x+1][y] = maze_score[x][y] +1
                    q.put([x+1,y])
            ##left
            if y != 0:
                if maze_score[x][y-1] ==0 and maze[x][y-1] == ".":
                    maze_score[x][y-1] = maze_score[x][y] +1
                    q.put([x,y-1])
        
print(maxim-1)

Submission status: Accepted

Solution code:
import scipy.sparse
H,W = (int(x) for x in input().split())
lines = [input() for i in range(H)]
lil = scipy.sparse.lil_matrix((H*W, H*W), dtype = int)
for i in range(H):
    for j in range(W):
        if i == j == 0: continue
        elif i == 0 and j > 0:
            if lines[0][j] == lines[0][j-1] == ".":
                lil[i*W+j, i*W+j-1] = 1
                lil[i*W+j-1, i*W+j] = 1
        elif i > 0 and j == 0:
            if lines[i][0] == lines[i-1][0] == ".":
                lil[i*W+j, (i-1)*W+j] = 1
                lil[(i-1)*W+j, i*W+j] = 1
        else:
            if lines[i][j] == lines[i][j-1] == ".":
                lil[i*W+j, i*W+j-1] = 1
                lil[i*W+j-1, i*W+j] = 1
            if lines[i][j] == lines[i-1][j] == ".":
                lil[i*W+j, (i-1)*W+j] = 1
                lil[(i-1)*W+j, i*W+j] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil, directed = False).astype(int)
print(lil2.max())

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
inf = -9999999999
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    h, w = nm()
    s = s = [['#'] * (w+1)]
    for _ in range(h):
        temp = ['#']
        temp.extend(list(ns()))
        temp.extend(['#'])
        s.append(temp)
    s.append(['#'] * (w+1))
        
    def bfs(arr, x, y):
        que = deque([[x, y]])
        dist = [[0]*(w+2) for _ in range(h+2)]
        visited = set((x, y))
        for i in range(h+2):
            for j in range(w+2):
                if i == 0 or i == h + 1 or j == 0 or j == w + 1 or arr[i][j] == '#':
                    dist[i][j] = inf
                    visited.add((i, j))
        while True:
            #print(x, y, que)
            #print(dist)
            now = que.popleft()
            visited.add((now[0], now[1]))
            if arr[now[0]][now[1]] == '.':
                if (now[0]+1, now[1]) not in visited:
                    que.append([now[0]+1, now[1]])
                    visited.add((now[0]+1, now[1]))
                    dist[now[0]+1][now[1]] += dist[now[0]][now[1]] + 1
                if (now[0], now[1]+1) not in visited:
                    que.append([now[0], now[1]+1])
                    visited.add((now[0], now[1]+1))
                    dist[now[0]][now[1]+1] += dist[now[0]][now[1]] + 1
                if (now[0]-1, now[1]) not in visited:
                    que.append([now[0]-1, now[1]])
                    visited.add((now[0]-1, now[1]))
                    dist[now[0]-1][now[1]] += dist[now[0]][now[1]] + 1
                if (now[0], now[1]-1) not in visited:
                    que.append([now[0], now[1]-1])
                    visited.add((now[0], now[1]-1))
                    dist[now[0]][now[1]-1] += dist[now[0]][now[1]] + 1
            if que == deque():
                break 
        mx = []
        for i in range(h+2):
            mx.append(max(dist[i]))       
        return max(mx)

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

    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque 

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

# print(maze)

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

# i,j をスタート地点に幅優先探索
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            continue

        visited = [[-1]*w for _ in range(h)]
        visited[i][j] = 0
        next_step = deque([[i,j]])

        while next_step:
            now_step = next_step.popleft()
            for move in moves:
                nh = now_step[0]+move[0]
                nw = now_step[1]+move[1]
                if 0<=nh<h and 0<=nw<w and maze[nh][nw] == '.' and visited[nh][nw] == -1:
                    visited[nh][nw] = visited[now_step[0]][now_step[1]] + 1
                    next_step.append([nh,nw])

        for tmp in visited:
            max_step = max(max_step, max(tmp))

print(max_step)

Submission status: Accepted

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

#[print(maze[i]) for i in range(h)]
from collections import deque

mx = 0
for i in range(h):
  for j in range(w):
    s_y, s_x = i, j
    if maze[s_y][s_x] == '#':
      continue
    visited = [[0]*w for _ in range(h)]
    dis = [[0]*w for _ in range(h)]
    
    d = deque()
    d.append([s_y, s_x])
    visited[s_y][s_x] = 1
    
    while len(d):
      y, x = d.popleft()
      for dy, dx in [[-1,0], [1,0], [0, -1], [0, 1]]:
        next_y, next_x = y+ dy, x+dx
        if next_y>=0 and next_y<h and next_x>=0 and next_x<w:
          if maze[next_y][next_x]=='.' and visited[next_y][next_x]==0:
            d.append([next_y, next_x])
            dis[next_y][next_x] = dis[y][x] + 1
            visited[next_y][next_x] = 1
            if dis[next_y][next_x]>mx:
              mx = dis[next_y][next_x]
              
print(mx)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy):
  dmap=[[h*w]*w for _ in range(h)]
  dmap[sx][sy]=0
  cand=deque()
  cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.popleft()
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.' and dmap[next_x][next_y]==h*w:
        dmap[next_x][next_y]=min(dmap[x][y]+1,dmap[next_x][next_y])
        cand.append([next_x,next_y])
  return max([dmap[i][j] for i in range(h) for j in range(w) if dmap[i][j]<h*w])
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      d=maze(l,ix,iy)
      if c<d:
        c=d
print(c)

Submission status: Accepted

Solution code:
from collections import deque

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

G = []
for i in range(H):
    G.append(list(input()))


move = [[0, 1], [0, -1], [-1, 0], [1, 0]]
saidai = 0
for sy in range(H):
    for sx in range(W):
        if G[sy][sx] == ".":
            queue = deque([[sy, sx]])
            visited = [[-1]*W for i in range(H)]
            visited[sy][sx] = 0
            while queue:
                y, x = queue.popleft()
                for i in move:
                    iy, ix = i[0], i[1]
                    if 0<=iy+y<H and 0<=ix+x<W and G[iy+y][ix+x] =="." and visited[iy+y][ix+x] == -1:
                        visited[iy+y][ix+x] = visited[y][x] + 1
                        queue.append([iy+y, ix+x])
        
            for i in range(H):
                for j in range(W):
                        saidai = max(saidai, visited[i][j])
            queue = []
            visited = [[0]*W for i in range(H)]
print(saidai)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

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

def mazemax(px, py):
    global ans
    maze = deepcopy(mazemother)
    dp = [[-1] * w for i in range(h)]
    dp[py][px] = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    pos = deque([[px, py]])

    while len(pos) > 0:
        x, y = pos.popleft()
        maze[y][x] = "#"
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == "." and dp[ny][nx] == -1:
                dp[ny][nx] = dp[y][x] + 1
                pos.append([nx, ny])
    for i in range(w):
        for j in range(h):
            ans = max(ans, dp[j][i])


for i in range(w):
    for j in range(h):
        if mazemother[j][i] == ".":
            mazemax(i, j)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [[s for s in input()] for _ in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            s = S[i][j]
            if s == '#':
                continue
            INF = 1000000000
            field = [[INF for _ in range(W)] for _ in range(H)]
            que = queue.Queue()
            que.put((i, j))
            field[i][j] = 0
            while not que.empty():
                ci, cj = que.get()
                d = ((0, 1), (1, 0), (-1, 0), (0, -1))
                for di, dj in d:
                    ni = ci + di
                    nj = cj + dj
                    if (ni < 0 or H <= ni or nj < 0 or W <= nj):
                        continue
                    if S[ni][nj] == '#':
                        continue
                    if field[ni][nj] > field[ci][cj] + 1:
                        field[ni][nj] = field[ci][cj] + 1
                        que.put((ni, nj))
            res = 0
            for k in range(H):
                for l in range(W):
                    if field[k][l] != INF:
                        res = max(res, field[k][l])
            ans = max(res, ans)

    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
INF = 114514191981036436433-4

c = [None]*h
for i in range(h):
    c[i] = input()
            
dx = [1,0,-1,0]
dy = [0,1,0,-1]

ans = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == "#":
            continue
        
        d = [[INF for i in range(w)] for j in range(h)]
        e = [[0 for i in range(w)] for j in range(h)]

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

        d[i][j] = 0
        que = deque([[i,j]])

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

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

                if 0<=nx and nx<w and 0<=ny and ny<h and c[ny][nx] != '#':
                    if d[ny][nx] > d[y][x]+1:
                        d[ny][nx]=d[y][x]+1
                        e[ny][nx] = d[ny][nx]
                        que.append([ny,nx])
                        
        tmax = 0
        for l in range(h):
            tmax = max(tmax,max(e[l]))
        ans = max(ans,tmax)
        
print(ans)

Submission status: Accepted

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

Di = [-1, 1, 0, 0] #Direction i
Dj = [0, 0, -1, 1] #Direction j
inf = 1000

def update_data(i:int, j:int, x:int):
    if Dist[i][j] == inf:
        Dist[i][j] = x
        Q.append([i, j])
    else:
        pass

ans = 0
for si in range(h):
    for sj in range(w):
        Dist = [[inf for j in range(w)] for i in range(h)]   #Distance
        if S[si][sj] == '.':
            Q = deque([])
            update_data(si, sj, 0)
            #BFS
            while len(Q) != 0:
                i, j  = Q[0][0], Q[0][1]
                Q.popleft()
                for dr in range(4):
                    ni , nj = i+Di[dr], j+Dj[dr]
                    if 0 <= ni and ni < h and 0 <= nj and nj < w:
                        if S[ni][nj] == '.':
                            update_data(ni, nj, Dist[i][j]+1)
                        else:
                            pass
                    else:
                        pass
            for i in range(h):
                for j in range(w):
                    if Dist[i][j] == inf:
                        pass
                    else:    
                        if ans < Dist[i][j]:
                            ans = Dist[i][j]
                        else:
                            pass
        else:
            pass
print(ans)

Submission status: Accepted

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

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


def bfs(x, y):
    V = [[-1] * w for i in range(h)]
    que = deque([])
    que.append([x, y])
    V[x][y] = 0
    while que:
        p=que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and L[nx][ny] == '.' and V[nx][ny] == -1:
                V[nx][ny] = V[p[0]][p[1]] + 1
                que.append([nx, ny])
    r=0
    for i in range(h):
        for j in range(w):
            r = max(r, V[i][j])
    return r

R = 0
for x in range(h):
    for y in range(w):
        if L[x][y] != '#':
            l = bfs(x, y)
            R=max(R,l)
print(R)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

H, W = rl()
M = []
for i in range(H):
    row = rs()
    M.append(row)

import collections
def get_dist(i, j):
    visited = {}
    queue = collections.deque()
    queue.append((i,j,0)) 
    max_l = 0
    while queue:
        i, j, l = queue.popleft()
        if (i,j) in visited: continue
        max_l = max(max_l, l)
        visited[(i,j)] = 1
        for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
            ni, nj = i+di, j+dj
            if 0 <= ni < H and 0 <= nj < W and M[ni][nj] != '#':
                queue.append((ni,nj,l+1))
    return max_l

max_move = 0
for i in range(H):
    for j in range(W):
        if M[i][j] == '#': continue
        d = get_dist(i, j)
        max_move = max(max_move, d)
print(max_move)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
queue = []
visited = [[0 for i in range(w)] for i in range(h)]
ans = 0

for i in range(h):
  for j in range(w):
    if c[i][j] == '.':
      queue.append([i, j])
      visited[i][j] = 1
      dy_dx = [[1, 0], [0, 1], [-1, 0], [0, -1]]
      while len(queue) > 0:
        now = queue.pop(0)
        for k in range(4):
          y = now[0] + dy_dx[k][0]
          x = now[1] + dy_dx[k][1]
          if 0 <= y < h and 0 <= x < w:
            if c[y][x] != '#' and visited[y][x] == 0:
              visited[y][x] = visited[now[0]][now[1]] + 1
              queue.append([y, x])
    for l in range(h):
      for m in range(w):
        ans = max(ans, visited[l][m])
    queue = []
    visited = [[0 for i in range(w)] for i in range(h)]
               
print(ans - 1)

Submission status: Accepted

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


def bfs(i, j):  # 引数はスタートの位置(i, j)
    q = deque()
    q.append((i, j))
    log = [[-1] * w for _ in range(h)]
    log[i][j] = 0
    distance = 0
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 右、上、左、下
    while q:
        p = q.popleft()
        for item in d:
            nx = p[0] + item[0]
            ny = p[1] + item[1]
            if not(0 <= nx < h and 0 <= ny < w):  # 迷路の外にはでれない
                continue
            elif s[nx][ny] == "#":  # 壁には進めない
                continue
            elif log[nx][ny] >= 0:  # 探索済みは探索しない
                continue
            else:
                log[nx][ny] = log[p[0]][p[1]] + 1
                q.append((nx, ny))
                if distance < log[nx][ny]:
                    distance = log[nx][ny]
    return distance


distance = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":  # start地点は壁でない
            continue
        else:
            temp = bfs(i, j)
            if temp >= distance:
                distance = temp
print(distance)

Submission status: Accepted

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


def bfs(i, j):  # 引数はスタートの位置(i, j)
    q = deque()
    q.append((i, j))
    log = [[-1] * w for _ in range(h)]
    log[i][j] = 0
    distance = 0
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q:
        p = q.popleft()
        for x, y in d:
            nx = p[0] + x
            ny = p[1] + y
            if not(0 <= nx < h and 0 <= ny < w):  # 迷路の外にはでれない
                continue
            elif s[nx][ny] == "#":  # 壁には進めない
                continue
            elif log[nx][ny] >= 0:  # 探索済みは探索しない
                continue
            else:
                log[nx][ny] = log[p[0]][p[1]] + 1
                q.append((nx, ny))
                if distance < log[nx][ny]:
                    distance = log[nx][ny]
    return distance


distance = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":  # start地点は壁でない
            continue
        else:
            temp = bfs(i, j)
            if temp >= distance:
                distance = temp
print(distance)

Submission status: Accepted

Solution code:
#BFS
from collections import deque
def bfs(i, j):
    q=deque()
    q.append((i, j))
    log = [[-1] * w for i in range(h)]
    log[i][j] = 0

    distance = 0
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q:
        #qの先頭を取り出す
        p=q.popleft()
        for x, y in d:
            nx = p[0] + x
            ny = p[1] + y
            if not(0 <= nx <h and 0 <= ny < w):continue
            if s[nx][ny] == "#":continue
            if log[nx][ny] >= 0:continue
            log[nx][ny] = log[p[0]][p[1]] + 1
            q.append((nx, ny))
            if distance < log[nx][ny]:distance = log[nx][ny]

    return distance

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

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":continue
        temp = bfs(i, j)
        if temp >= distance:distance = temp
print(distance)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]#迷路の入力

ans = 0
for x in range(H):#すべてのマスからスタート
    for y in range(W):
        #壁からはスタートできない：スルー
        if maze[x][y] == "#":
            continue

        #初期化：0埋め、HとWの順番に注意
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])#デキューに入れる

        while stack:#スタックが有るあいだ
            h,w = stack.popleft()#スタックの先頭を取ってくる
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:#マスの四方
                new_h, new_w = h+i, w+j#新しいマス
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue#範囲外ならスルー
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1#BFS、+1
                    stack.append([new_h, new_w])#新しいマスをスタックへ

        #start位置は0で初期化
        distance[x][y] = 0
        ans = max(ans, np.max(distance))#npは二次元のmax取れる

print(ans)

Submission status: Accepted

Solution code:
from queue import deque
from copy import deepcopy

    
H, W = map(int, input().split())
S = [['#'] * (W + 2)]
cnt = []
Checked = [[0 for _ in range(W+2)] for _ in range(H+2)]


for _ in range(H):
    S.append(['#'] + [i for i in input()] + ['#'])
S.append(['#']*(W + 2))

for start_h in range(1, H+1):
    for start_w in range(1, W+1):
        if S[start_h][start_w] == '#':
            continue
        q = deque([[start_h, start_w]])
        checked = deepcopy(Checked)
        c = 0
        tmp = []
        while q:
            h, w = q.popleft()
            if checked[h][w]:
                 continue
            checked[h][w] = 1
                    
            for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                next_h, next_w = h + dh, w + dw
                if S[next_h][next_w] == '#':
                    continue
                if [next_h, next_w] in tmp or checked[next_h][next_w]:
                    continue
                tmp.append([next_h, next_w])
            if not q:
                q.extend(tmp)
                tmp = []
                c += 1
        cnt.append(c-1)
            
print(max(cnt))

Submission status: Accepted

Solution code:
#頂点の数をN、変の数をMとするとO(N+M)
#queueは遅いからdequeを使う
from collections import deque
from copy import deepcopy

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

ans = [[0 for _ in range(w+2)]for _ in range(h+2)]
c_copy = deepcopy(c)
ans_copy = deepcopy(ans)
def bfs(x,y):
	global q
	global c
	q.append([x,y])
	num = 0

	while q:
		x,y = q.popleft()
		if c[y][x-1] == '.':
			q.append([x-1,y])
			ans[y][x-1] = ans[y][x] + 1
			num = ans[y][x-1]
			c[y][x-1] = '#'
		if c[y][x+1] == '.':
			q.append([x+1,y])
			ans[y][x+1] = ans[y][x] + 1
			num = ans[y][x+1]
			c[y][x+1] = '#'
		if c[y-1][x] == '.':
			q.append([x,y-1])
			ans[y-1][x] = ans[y][x] + 1
			num = ans[y-1][x]
			c[y-1][x] = '#'
		if c[y+1][x] == '.':
			q.append([x,y+1])
			ans[y+1][x] = ans[y][x] + 1
			num = ans[y+1][x]
			c[y+1][x] = '#'
	return num

tmp = 0
for i in range(1,h+1):
	for j in range(1,w+1):
		c = deepcopy(c_copy)
		ans = deepcopy(ans_copy)
		if c[i][j] == '.':
			c[i][j] = '#'
			tmp = max(tmp,bfs(j,i))

print(tmp)

Submission status: Accepted

Solution code:
from collections import deque

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

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

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]#上下左右どこかに1マス移動する

ans = 0
# スタート位置を変えながら全探索
for X in range(1, H + 1):
    for Y in range(1, W + 1):
        if S[X][Y] == '#':
            continue
#if ~ continue分はtrueなら下の操作を行うことなく次の番号に移るという意味
        check = [[-1] * (W + 2) for _ in range(H + 2)]
        check[X][Y] = 0
#cheakには壁には-1、道にはそこまでの距離、未探索地には0を入れる
        que = deque()
        que.append([X, Y])
        while que:
            tmp = que.popleft()
            x = tmp[0]
            y = tmp[1]
            flag = True
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if S[nx][ny] == '.' and check[nx][ny] == -1:#次の移動場所が"道"かつ"未探索"ならqueに突っ込む
                    que.append([nx, ny])
                    check[nx][ny] = check[x][y] + 1 #cheakにそこまでの距離を代入
                    flag = False
#flagの使い方が上手、真似したい
            if flag:#ある一点のスタート地点からの探索がすべて終わってから、その中の
                ans = max(ans, check[x][y])


print (ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans=[]
for i in range(H):
  for j in range(W):
    if S[i][j]=="#":
      continue
    queue=deque([[i,j]])
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    while queue:
      y,x=queue.popleft()
      for k,l in ([1,0], [-1,0], [0,1], [0,-1]):
        new_y,new_x=y+k,x+l
        if new_y<0 or new_x<0 or new_y>=H or new_x>=W:
          continue
        elif S[new_y][new_x]=="." and visited[new_y][new_x]==-1:
          visited[new_y][new_x]=visited[y][x]+1
          queue.append([new_y,new_x])
    L=0
    for m in range(H):
      val=max(visited[m])
      L=max(L,val)
    ans.append(L)
print(max(ans))