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:
INF = 1001001001
from collections import deque
h,w = map(int,input().split())
s = [input() for _ in range(h)]
di = (-1, 0, 1, 0)
dj = ( 0,-1, 0, 1)

ans = 0
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#': continue
        dist = [[INF] * w for _ in range(h)]
        dist[si][sj] = 0
        q = deque([(si,sj)])
        while len(q) > 0:
            i,j = 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
                if dist[ni][nj] != INF: continue
                q.append((ni,nj))
                dist[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



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

step=[[1,0],[-1,0],[0,1],[0,-1]]

mx=0
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":continue
        chk=[[False]*W for i in range(H)]
        q=deque([[h,w,0]])
        chk[h][w]=True
        while q:
            y,x,c=q.popleft()
            for dh,dw in step:
                if not (0<=y+dh<H and 0<=x+dw<W):continue
                if S[y+dh][x+dw]=="#":continue
                if chk[y+dh][x+dw]==False:
                    chk[y+dh][x+dw]=True
                    q.append([y+dh,x+dw,c+1])
                else:
                    mx=max(mx,c)

print(mx)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
ans = 0
si, sj = 0, 0

for i in range(h):
    s.append(input())

for x in range(h):
    for y in range(w):
        # print('x, y:', x, y)
        if s[x][y] == '#':
            continue
        q = deque()
        q.append((0, (x, y)))
        done = set()
        done.add(str(x) + ':' + str(y))
        temp = 0

        while q:
            dis, tup = q.popleft()
            i, j = tup[0], tup[1]
            temp = max(temp, dis)

            # Right
            if j < w - 1 and s[i][j + 1] == '.':
                if str(i) + ':' + str(j + 1) not in done:
                    done.add(str(i) + ':' + str(j + 1))
                    q.append((dis + 1, (i, j + 1)))

            # Left
            if j > 0 and s[i][j - 1] == '.':
                if str(i) + ':' + str(j - 1) not in done:
                    done.add(str(i) + ':' + str(j - 1))
                    q.append((dis + 1, (i, j - 1)))

            # Up
            if i > 0 and s[i - 1][j] == '.':
                if str(i - 1) + ':' + str(j) not in done:
                    done.add(str(i - 1) + ':' + str(j))
                    q.append((dis + 1, (i - 1, j)))

            # Down
            if i < h - 1 and s[i + 1][j] == '.':
                if str(i + 1) + ':' + str(j) not in done:
                    done.add(str(i + 1) + ':' + str(j))
                    q.append((dis + 1, (i + 1, j)))

        if temp > ans:
            # print('\nUpdate:', x, y)
            # print('temp, ans:', temp, ans)
            ans = temp
            si, sj = x, y

        # ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze,dist,sy,sx):
    #キューオブジェクトの生成
    queue = deque([[sy,sx]])
    #スタート地点のdistを0にする
    dist[sy][sx] = 0
    #mdを初期化
    md = 0
    while queue:
        #先頭から要素を一つ削除する
        y,x = queue.popleft()
        for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            #迷路内に収まっているか確かめる
            if 0 <= new_y < H and 0 <= new_x < W:
                #new_y,new_xが道かどうか確かめる
                #またnew_y,new_xが初めて通る道かを確かめる
                if maze[new_y][new_x] == "." and dist[new_y][new_x] == -1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md = max(dist[new_y][new_x],md)
    return md
H, W = map(int,input().split())
maze = [input() for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for k in range(H)]
        #i,jをスタートの位置としているから壁じゃないか確認
        if maze[i][j] != "#":
            a = bfs(maze,dist,i,j)
            ans = max(a,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(H):
    S.append(list(input()))

step=[[1,0],[-1,0],[0,1],[0,-1]]


mx=0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw]=="#":continue
        visited = [[False] * W for i in range(H)]
        q=deque([[sh,sw,0]])
        visited[sh][sw]=True

        while q:
            h,w,c=q.popleft()
            for dh,dw in step:
                if not (0<=h+dh<H and 0<=w+dw<W):continue
                if S[h+dh][w+dw]=="#":continue
                if visited[h+dh][w+dw]==False:
                    q.append([h+dh,w+dw,c+1])
                    visited[h+dh][w+dw]=True
                else:
                    mx=max(mx,c)
print(mx)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze,dist,sy,sx):
    #キューオブジェクトの生成
    queue = deque([[sy,sx]])
    dist[sy][sx] = 0
    md = 0
    l = []
    while queue:
        #先頭から要素を一つ削除する
        y,x = queue.popleft()
        for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            #迷路内に収まっているか確かめる
            if 0 <= new_y < H and 0 <= new_x < W:
                #道かどうか確かめる
                if maze[new_y][new_x] == "." and dist[new_y][new_x] == -1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md = max(dist[new_y][new_x],md)
    return md
H, W = map(int,input().split())
maze = [input() for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for k in range(H)]
        if maze[i][j] != "#":
            a = bfs(maze,dist,i,j)
            ans = max(a,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze,dist,sy,sx):
    #キューオブジェクトの生成
    queue = deque([[sy,sx]])
    dist[sy][sx] = 0
    md = 0
    l = []
    while queue:
        #先頭から要素を一つ削除する
        y,x = queue.popleft()
        for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y, new_x = y+j, x+k
            #迷路内に収まっているか確かめる
            if 0 <= new_y < H and 0 <= new_x < W:
                #道かどうか確かめる
                if maze[new_y][new_x] == "." and dist[new_y][new_x] == -1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md = max(dist[new_y][new_x],md)
    return md
H, W = map(int,input().split())
maze = [input() for i in range(H)]

ans = 0
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for j in range(H)]
        if maze[i][j] != "#":
            a = bfs(maze,dist,i,j)
            ans = max(a,ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    grid = ["#"*(w+2)]+["#"+input()+"#" for _ in [0]*h]+["#"*(w+2)]
    grid = [[i == "." for i in j] for j in grid]
    ans_list = []
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j]:
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*(w+2) for _ in [0]*(h+2)]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    if dist[x+dx][y+dy] == -1:
                        if grid[x+dx][y+dy]:
                            dist[x+dx][y+dy] = cnt
                            qq.append((x+dx, y+dy))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Submission status: Accepted

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

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        i, j = x // W, x % W
        for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if X[ni][nj] == 0:
                    y = ni * W + nj
                    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][j] == 0:
            ma = max(ma, max(BFS(i*W+j)))
print(ma)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, H, W, sx, sy):
    que = deque()
    que.append([sx, sy])
    visited[sx][sy] = 0
    ml = 0
    
    while que:
        x, y = que.popleft()
        
        for px, py in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx, ny = x+px, y+py
            if (0<=nx<H)and(0<=ny<W):
                if (maze[nx][ny] == '.')and(visited[nx][ny]==-1):
                    que.append([nx, ny])
                    dist = visited[x][y] + 1
                    visited[nx][ny] = dist
                    ml = max(ml, dist)
    return ml
                    

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        else:
            visited = [[-1]*W for _ in range(H)]
            ans = max(ans, bfs(maze, visited, H, W, i, j))
print(ans)

Submission status: Accepted

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

import copy
dp=[[1000 for i in range(w)]for i in range(h)]
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j=="#":
            dp[y][x]=9999

dydx=[[-1,0],[1,0],[0,-1],[0,1]]
#print(dp)
maxi=0
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j==".":
            ndp=copy.deepcopy(dp)
            ndp[y][x]=0
            cnt=0
            queue=[]
            queue.append([y,x])
            while queue:
                ny,nx=queue.pop(0)
                for dy,dx in dydx:
                    nny,nnx=ny+dy,nx+dx
                    if 0<=nny<=h-1 and 0<=nnx<=w-1 and field[nny][nnx]!="#" and ndp[nny][nnx]==1000:
                        ndp[nny][nnx]=ndp[ny][nx]+1
                        queue.append([nny,nnx])
                        if ndp[nny][nnx]>maxi:
                            maxi=ndp[nny][nnx]
            #print(ndp)
print(maxi)

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    grid = ["#"*(w+2)]+["#"+input()+"#" for _ in [0]*h]+["#"*(w+2)]
    grid = [[i == "." for i in j] for j in grid]
    ans_list = []
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j]:
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*(w+2) for _ in [0]*(h+2)]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                if dist[x-1][y] == -1:
                    if grid[x-1][y]:
                        dist[x-1][y] = cnt
                        qq.append((x-1, y))
                if dist[x+1][y] == -1:
                    if grid[x+1][y]:
                        dist[x+1][y] = cnt
                        qq.append((x+1, y))
                if dist[x][y-1] == -1:
                    if grid[x][y-1]:
                        dist[x][y-1] = cnt
                        qq.append((x, y-1))
                if dist[x][y+1] == -1:
                    if grid[x][y+1]:
                        dist[x][y+1] = cnt
                        qq.append((x, y+1))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Submission status: Accepted

Solution code:
# BFS, queue
from collections import deque

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

# print(s)

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

def update(i, j, x):
    if dist[i][j] != inf:
        return
    dist[i][j] = x
    q.append([i, j])

ans = 0

for si in range(h):
    for sj in range(w):
        if s[si][sj] == "#":
            continue
        dist = [[inf] * w for _ in range(h)]
        q = deque()



        update(si, sj, 0)
        while q:
            i, j = 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:
def main():
    h, w = map(int, input().split())
    grid = ["#"*(w+2)]+["#"+input()+"#" for _ in [0]*h]+["#"*(w+2)]
    #grid = [[i == "." for i in j] for j in grid]
    ans_list = []
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j] == ".":
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*(w+2) for _ in [0]*(h+2)]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                if dist[x-1][y] == -1:
                    if grid[x-1][y] == ".":
                        dist[x-1][y] = cnt
                        qq.append((x-1, y))
                if dist[x+1][y] == -1:
                    if grid[x+1][y] == ".":
                        dist[x+1][y] = cnt
                        qq.append((x+1, y))
                if dist[x][y-1] == -1:
                    if grid[x][y-1] == ".":
                        dist[x][y-1] = cnt
                        qq.append((x, y-1))
                if dist[x][y+1] == -1:
                    if grid[x][y+1] == ".":
                        dist[x][y+1] = cnt
                        qq.append((x, y+1))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Submission status: Accepted

Solution code:
# BFS, queue
from collections import deque

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

# print(s)

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


ans = 0

for si in range(h):
    for sj in range(w):
        if s[si][sj] == "#":
            continue
        dist = [[inf] * w for _ 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 q:
            i, j = 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

def bfs(table, visited, sy, sx):
    queue=deque([[sy, sx]])
    visited[sy][sx]=0
    md=0
    while queue:
        y, x=queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < R and 0 <= new_x < C:
              if table[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])
                md=max(visited[new_y][new_x],md)
    return md

R, C=map(int, input().split())
table = [input() for i in range(R)]
ans=0
for yi in range(R):
  for xi in range(C):
    visited=[[-1]*C for j in range(R)]
    if table[yi][xi]!='#':
      a=bfs(table,visited,yi,xi)
      ans=max(a,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, dist, sy, sx):
    queue = deque([[sy, sx]])
    dist[sy][sx] = 0
    md = 0
    l = []
    while queue:
        y,x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x]=="." and dist[new_y][new_x]==-1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md=max(dist[new_y][new_x],md)
    return md

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

ans=0
for i in range(H):
  for j in range(W):
    dist=[[-1]*W for j in range(H)]
    if maze[i][j]!='#':
      a=bfs(maze,dist,i,j)
      ans=max(a,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def solve(S, s):
    if S[s[0]][s[1]] != ".":
        return -1
    queue = deque([s])
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[s[0]][s[1]] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if new_x in range(W) and new_y in range(H) and 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])
#    for v in visited:
#        print(v)
    return max(map(max,visited))


H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        ans = max(ans, solve(S, [i, l]))
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
EMP = -1            # 未チェック
BLOCK = -2          # 壁

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

# 迷路情報
maze_map = [[EMP for i in range(w)] for j in range(h)]

# 座標リスト(上、左、右、下)
pos_list = [[-1,0], [0,-1], [0,1], [1,0]]

# 迷路取得
for i in range(h):
    input_data = input()
    char_data = list(input_data)

    for j in range(len(char_data)):
        # 壁は-2
        if(char_data[j] == "#"):
            maze_map[i][j] = BLOCK

# 最大値取得
max_mass = 0

# 探索
for i in range(h):
    for j in range(w):

        # 迷路、キューを初期化
        tmp_maze_map = deepcopy(maze_map)
        queue_list = []

        # 自身の位置を開始位置とする(壁の時は見ない)
        if(tmp_maze_map[i][j] == BLOCK):
            continue
        tmp_maze_map[i][j] = 0

        # キューに自身を入れる
        queue_list.append([i,j])

        while(len(queue_list) > 0):
            get_x = queue_list[0][0]
            get_y = queue_list[0][1]

            # 隣のチェック
            for k in pos_list:
                rin_x = get_x + k[0]
                rin_y = get_y + k[1]
            
                # 自身が壁
                if(tmp_maze_map[get_x][get_y] == BLOCK):
                    continue
                # 隣が範囲を超える
                if((rin_x < 0) or (rin_x >= h) or (rin_y < 0) or (rin_y >= w)):
                    continue
                # 隣が空でない
                if(tmp_maze_map[rin_x][rin_y] != EMP):
                    continue
                # 距離計算
                tmp_maze_map[rin_x][rin_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([rin_x,rin_y])            

            # チェックしたマスを取り除く
            queue_list.pop(0)

        # 最大値を取得
        for k in tmp_maze_map:
            t_sum_list = deepcopy(k)
            t_sum_list += [max_mass]
            max_mass = max(t_sum_list)
            t_sum_list.clear()
        
        # 迷路リセット
        tmp_maze_map.clear()

print(max_mass)

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    grid = [input() for _ in [0]*h]
    ans_list = []
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*w for _ in [0]*h]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                if x > 0:
                    if dist[x-1][y] == -1:
                        if grid[x-1][y] == ".":
                            dist[x-1][y] = cnt
                            qq.append((x-1, y))
                if x < h-1:
                    if dist[x+1][y] == -1:
                        if grid[x+1][y] == ".":
                            dist[x+1][y] = cnt
                            qq.append((x+1, y))
                if y > 0:
                    if dist[x][y-1] == -1:
                        if grid[x][y-1] == ".":
                            dist[x][y-1] = cnt
                            qq.append((x, y-1))
                if y < w-1:
                    if dist[x][y+1] == -1:
                        if grid[x][y+1] == ".":
                            dist[x][y+1] = cnt
                            qq.append((x, y+1))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '))
table = [[c for c in input()] for _ in range(H)]

def dfs(i, j):
    dists = [[-1 for _ in range(W)] for _ in range(H)]
    nexts = ((-1,0), (1,0), (0,-1), (0,1))

    buf = [(i, j)]
    dists[i][j] = 0
    while buf:
        i, j = buf.pop(0)

        for x, y in nexts:
            next_i = i + x
            next_j = j + y
            if 0 <= next_i < H and 0 <= next_j < W:
                if table[next_i][next_j] == '.' and dists[next_i][next_j] == -1:
                    dists[next_i][next_j] = dists[i][j] + 1
                    buf.append((next_i, next_j))


    ret = 0
    for i in range(H):
        for j in range(W):
            ret = max(ret, dists[i][j])

    return ret

# print(table)

ans = 0
for i in range(H):
    for j in range(W):
        if table[i][j] == '.':
            n = dfs(i, j)
            ans = max(ans, n)


print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
EMP = -1 
BLOCK = -2

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

# 迷路情報
maze_map = [[EMP for i in range(w)] for j in range(h)]

# 迷路取得
for i in range(h):
    input_data = input()
    char_data = list(input_data)

    for j in range(len(char_data)):
        # 壁は-1
        if(char_data[j] == "#"):
            maze_map[i][j] = BLOCK

# 最大値取得
max_mass = 0

# 探索
for i in range(h):
    for j in range(w):

        # 迷路、キューを初期化
        tmp_maze_map = deepcopy(maze_map)
        queue_list = []

        # 自身の位置を開始位置とする(壁の時は見ない)
        if(tmp_maze_map[i][j] == BLOCK):
            continue
        tmp_maze_map[i][j] = 0

        # キューに自身を入れる
        queue_list.append([i,j])

        while(len(queue_list) > 0):
            get_x = queue_list[0][0]
            get_y = queue_list[0][1]

            # チェック(上) 範囲を超える、自身が壁、上が空でないのときは処理しない
            if(not ((get_x == 0) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x-1][get_y] != EMP))):
                tmp_maze_map[get_x-1][get_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x-1,get_y])

            # チェック(左, 右)
            if(not ((get_y == 0) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x][get_y-1] != EMP))):
                tmp_maze_map[get_x][get_y-1] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x, get_y-1])

            # チェック(右)
            if(not ((get_y == w-1) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x][get_y+1] != EMP))):
                tmp_maze_map[get_x][get_y+1] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x, get_y+1])
            # チェック(下)
            if(not ((get_x == h-1) or (tmp_maze_map[get_x][get_y] == BLOCK) or (tmp_maze_map[get_x+1][get_y] != EMP))):
                tmp_maze_map[get_x+1][get_y] = tmp_maze_map[get_x][get_y] + 1
                queue_list.append([get_x+1,get_y])

            # チェックしたマスを取り除く
            queue_list.pop(0)

        # 最大値を取得
        for k in tmp_maze_map:
            t_sum_list = deepcopy(k)
            t_sum_list += [max_mass]
            max_mass = max(t_sum_list)
            t_sum_list.clear()
        
        # 迷路リセット
        tmp_maze_map.clear()

print(max_mass)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx):
    queue=deque([[sy, sx]])
    visited[sy][sx]=0
    md=0
    l=[]
    while queue:
        y, x=queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x=y+j, x+k
            if 0<=new_y<R and 0<=new_x<C:
              if maze[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])
                md=max(visited[new_y][new_x],md)
    return md


R, C=map(int, input().split())

maze=[input() for i in range(R)]
ans=0
for i in range(R):
  for j in range(C):
    visited=[[-1]*C for j in range(R)]
    if maze[i][j]!='#':
      a=bfs(maze,visited,i,j)
      ans=max(a,ans)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
meiro=[input() for _ in range(h)]
n=w*h
e=[[0]*n for _ in range(n)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
  for j in range(w):
    if meiro[i][j]==".":
      for x,y in d:
        ni,nj=i+x,j+y
        if 0<=ni<h and 0<=nj<w and meiro[ni][nj]==".":
          e[w*i+j][w*ni+nj]=1

ans=floyd_warshall(e)
INF=float("inf")
print(int(max(max(a if a != INF else 0 for a in a) for a in ans)))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0

INF=10**9
ans=0
for i in range(H):
  for j in range(W):
    dist=[[INF for j in range(W)] for i in range(H)]
    q=deque()
    q.append([i,j,0])
    while q:
      node=q.popleft()
      y=node[0]
      x=node[1]
      d=node[2]
      if grid[y][x]=="#":
        continue
      if dist[y][x]<=d:
        continue
      if ans<d:
        ans=d
      dist[y][x]=d
      cases=((0,1),(0,-1),(1,0),(-1,0))
      for c in cases:
        if 0<=y+c[0]<H and 0<=x+c[1]<W:
          q.append([y+c[0],x+c[1],d+1])
      
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.readline

H, W = map(int, input().split())
S = [list('#' * (W + 2))] + [['#'] + list(read().rstrip()) + ['#'] for _ in range(H)] + [list('#' * (W + 2))]


def bfs(grid, start):
    distance = [[-1] * (W + 2) for _ in range(H + 2)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                distance[new_x][new_y] = distance[x][y] + 1
                queue.append((new_x, new_y))
        if not queue:
            return distance[x][y]


answer = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = dy + j, dx + i
            if S[new_x][new_y] == '.':
                cnt += 1

        if cnt > 2:
            continue

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Accepted

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

ans = 0
for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            continue
        cells = [[None] * W for _ in range(H)]
        cells[i][j] = 0
        q = deque([(i, j)])
        while q:
            y, x = q.popleft()
            for dy, dx in d:
                if 0 <= y+dy < H and 0 <= x+dx < W and l[y+dy][x+dx] == '.' and (cells[y+dy][x+dx] is None or cells[y+dy][x+dx] > cells[y][x]+1):
                    n = cells[y][x] + 1
                    cells[y+dy][x+dx] = n
                    q.append((y+dy, x+dx))
                    if ans < n:
                        ans = n

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, dot_num):
    q = deque([[sy, sx]])
    visited[sy][sx] = 0
    cnt = 1
    while q:
        y, x = q.popleft()
        # 全てのマスを探索したら終了
        if dot_num == cnt:
            visited_1dim = [0] * H*W
            for i in range(H):
                for j in range(W):
                    visited_1dim[i*W + j] = visited[i][j]
            return max(visited_1dim)
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    q.append([new_y, new_x])
                    cnt += 1
                    
H, W = map(int, input().split())
maze = [input() for i in range(H)]

# 道の数
maze_1dim = [0] * H*W
for y in range(H):
    for x in range(W):
        maze_1dim[y*W + x] = maze[y][x]
dot_num = maze_1dim.count(".")

# スタート地点を全て探索
ans = 0
for y in range(H):
    for x in range(W):
        visited = [[-1]*W for j in range(H)]
        if maze[y][x] == ".":
            ans = max(ans, bfs(maze, visited, y, x, dot_num))
print(ans)