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
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    start = []
    for h in range(H):
        for w in range(W):
            if S[h][w] != "#":
                start.append([h, w])

    res = 0
    for sh, sw in start:
        maze = [[f_inf] * W for _ in range(H)]
        maze[sh][sw] = 0
        que = deque([[sh, sw]])
        while que:
            h, w = que.popleft()
            for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                elif S[next_h][next_w] == "#":
                    continue
                else:
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
        ma = 0
        for h in range(H):
            for w in range(W):
                if S[h][w] != "#":
                    ma = max(ma, maze[h][w])
        res = max(res, ma)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import numpy as np
import queue
H,W=map(int,input().split())
S=list()
for i in range(H):
  S.append(input())
ans=0
  
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      L=[[-1]*W for i in range(H)]
      L[i][j]=0
      q=queue.Queue()
      q.put([i,j])
      while not q.empty():
        r=q.get()
        for k,l in [[1,0],[0,-1],[0,1],[-1,0]]:
          if r[0]+k>=0 and r[0]+k<H and r[1]+l>=0 and r[1]+l<W and S[r[0]+k][r[1]+l]=="." and L[r[0]+k][r[1]+l]==-1:
            L[r[0]+k][r[1]+l]=L[r[0]][r[1]]+1
            q.put([r[0]+k,r[1]+l])
      ans=max(ans,max(list(map(lambda x:max(x),L))))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import _pickle as cPickle
import cProfile
H, W =map(int,input().split())
grid = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            dist[h][w] = 0
            cells.append((h,w))

distG = cPickle.loads(cPickle.dumps(dist, -1))
pcells = deque()
def bfs(h,w):
    pcells.append((h,w))
    d = 1
    distG[h][w] = 1
    while pcells:
        oh,ow = pcells.popleft()
        d = distG[oh][ow]
        for dx, dy in ((0,1),(0,-1),(1,0),(-1,0)):
            nw = ow + dx
            nh = oh + dy
            if nw < 0 or W <= nw or nh <0 or H <= nh:
                continue
            if distG[nh][nw] == 0:
                distG[nh][nw] = d+1
                pcells.append((nh,nw))

    return d-1

a = 0
for i in range(len(cells)):
    distG = cPickle.loads(cPickle.dumps(dist, -1))
    h,w = cells.popleft()
    a = max(a,bfs(h,w))
print(a)

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*s=open(i:=0)
M=999
*g,=eval('[0]*M,'*M)
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+20]=u>'#'<(s+['#'*M])[i][j];j+=1;g[k][k+1]=u>'#'<t[j]
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Submission status: Accepted

Solution code:
from collections import deque
import itertools
def main():
    H, W = list(map(int, input().split()))
    A = [['#'] * (W + 2)] + [['#', ] + list(input()) + ['#', ] for _ in range(H)] + [['#'] * (W + 2)]
    DXY = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = 0
    INF = 10000
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if A[h][w] == '#':
                continue
            count = [[-1 if i == '#' else INF for i in a] for a in A]
            count[h][w] = 0
            stack = deque([[h, w], ])
            visited = [[0] * W for _ in range(H)]
            while stack:
                x, y = stack.popleft()
                if visited[x - 1][y - 1] == 1:
                    continue
                else:
                    visited[x - 1][y - 1] = 1
                for (dx, dy) in DXY:
                    X = x + dx
                    Y = y + dy
                    if A[X][Y] == '.':
                        if visited[X - 1][Y - 1] == 0:
                            stack.append([X, Y])
                        count[X][Y] = min(count[X][Y], count[x][y] + 1)
            count = list(itertools.chain.from_iterable(count))
            ans = max(ans, max(count))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
G = []
for i in range(H+2):
    if i == 0 or i == H+1:
        G.append('#'*(W+2))
    else:
        G.append('#' + input() + '#')

ans = 0
for sx in range(W+2):
    for sy in range(H+2):
        if G[sy][sx] == '.':
            dist = [[-float('inf') for i in range(W+2)] for i in range(H+2)]
            visited = [[-1 for i in range(W+2)] for i in range(H+2)]
            q = deque([])
            q.append((sx, sy))
            dist[sy][sx] = 0
            visited[sy][sx] = 1
            while q:
                x, y = q.popleft()

                if G[y][x+1] == '.' and visited[y][x+1] == -1:
                    q.append((x+1, y))
                    dist[y][x+1] = dist[y][x] + 1
                    visited[y][x+1] = 1

                if G[y][x-1] == '.' and visited[y][x-1] == -1:
                    q.append((x-1, y))
                    dist[y][x-1] = dist[y][x] + 1
                    visited[y][x-1] = 1

                if G[y+1][x] == '.' and visited[y+1][x] == -1:
                    q.append((x, y+1))
                    dist[y+1][x] = dist[y][x] + 1
                    visited[y+1][x] = 1

                if G[y-1][x] == '.' and visited[y-1][x] == -1:
                    q.append((x, y-1))
                    dist[y-1][x] = dist[y][x] + 1
                    visited[y-1][x] = 1
            for i in range(W+2):
                for j in range(H+2):
                    ans = max(ans, dist[j][i])
print(ans)

Submission status: Accepted

Solution code:
import pprint
H,W=map(int,input().split())
import copy
lastraw=["#"]*(W+2)
field=[["#"]*(W+2)]
for i in range(H):
  field.append(["#"]+list(input())+["#"])
 
field.append(lastraw)
maxmoves=0
#print(field)
saved_field=copy.deepcopy(field)
 
for i in range(H):
  for j in range(W):
    field=copy.deepcopy(saved_field)
    goal_point=(0,0)
    [sy,sx]=[j+1,i+1]
    [gy,gx]=[0,0]
 
    queue=[[sy,sx]]
    tests = ((-1,0),(0, 1),(1, 0),(0, -1))
    moves=0
 
    if field[sx][sy]=='#':
      queue=[]
    else:
      field[sx][sy]=0
 
    while True:
      if len(queue)==0:
        maxmoves=max(maxmoves,moves-1)
        break
      queue_next = []
      moves += 1
      #pprint.pprint(field)
      for y, x in queue:
        for ny, nx in tests:
          ty, tx = y + ny, x + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
      queue = queue_next
      if goal_point in queue:
        break
        #pprint.pprint(field)
        maxmoves=max(maxmoves,moves)
print(maxmoves)

Submission status: Accepted

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

f = []
for i in range(h):
    s = list(map(lambda x:0 if x== "." else 1,list(input())))
    f.append(s)

from collections import deque
def dfs_field(field,st,go):
    """
    :param field: #が1,.が0になったfield
    st: [i,j]
    go: [i,j]
    :return: 色々今は回数returnしている。
    """
    h = len(field)
    w = len(field[0])
    around = [[-1,0],[1,0],[0,1],[0,-1]]
    que = deque()
    visited = set()
    visited.add(str(st[0])+","+str(st[1]))
    que.append([st[0],st[1],0])
    max_cos = 0
    while True:
        if len(que) == 0:
            return  max_cos
        top = que.popleft()
        nowi = top[0]
        nowj = top[1]
        cost = top[2]
        for a in around:
            ni = nowi+a[0]
            nj = nowj+a[1]
            if ni < 0 or ni > h-1 or nj < 0 or nj > w-1:
                continue
            if field[ni][nj] == 1:
                continue
            if ni == go[0] and nj == go[1]:
                return cost+1
            else:
                key = str(ni)+","+str(nj)
                if key not in visited:
                    que.append([ni,nj,cost+1])
                    visited.add(key)
                    if cost+1 > max_cos:
                        max_cos = cost+1
        # print(que)



ans = 0
for i in range(h):
    for j in range(w):
        if f[i][j] == 0:
            ct = dfs_field(f,[i,j],[-2,-2])
            if ans < ct:
                ans = ct

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
S = [input()[:-1] for _ in [0]*H]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(h, w, H, W):
    visited = [False]*(W*H)
    q = deque()
    q.append((0, h, w))
    while q:
        d, h, w = q.popleft()
        if visited[h*W+w]:
            continue
        visited[h*W+w] = True

        for dh, dw in dirs:
            nh, nw = h+dh, w+dw
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh*W+nw] or  S[nh][nw] == '#':
                    continue
                q.append((d+1, nh, nw))
    return d, h, w

ans = 0
for h, _S in enumerate(S):
    for w, s in enumerate(_S):
        if s == '.':
            d, _, _ = bfs(h, w, H, W)
            if d > ans:
                ans = d

print(ans)

Submission status: Accepted

Solution code:
# ABC151 D-Maze Master
import queue
H,W = map(int,input().split())
maze = [input() for _ in range(H)]
dydx = ((0,1),(0,-1),(1,0),(-1,0))

def reach(sy,sx):
    visited = [[0]*W for _ in range(H)]
    visited[sy][sx] = 1
    q = queue.Queue()
    q.put((sy,sx,0))
    while True:
        y,x,d = q.get()
        for dy,dx in dydx:
            if (0<=y+dy<H)&(0<=x+dx<W):
                if (maze[y+dy][x+dx] == '#') or (visited[y+dy][x+dx] == 1):
                    continue
                visited[y+dy][x+dx] = 1
                q.put((y+dy,x+dx,d+1))
        if q.empty():
            ans = d
            break
    return ans

d = -1
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        d = max(d,reach(sy,sx))
                
print(d)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc151/tasks/abc151_d

from collections import deque

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


def bfs(sx, sy):
    result = 0
    count = [[-1] * w for i in range(h)]
    count[sx][sy] = 0
    d = deque()
    d.append((sx, sy))
    while d:
        x, y = d.popleft()
        result = count[x][y]
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            if (
                not (0 <= tx < h)
                or not (0 <= ty < w)
                or maze[tx][ty] == "#"
                or count[tx][ty] != -1
            ):
                continue
            else:
                count[tx][ty] = count[x][y] + 1
                d.append((tx, ty))
    return result


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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc151/tasks/abc151_d

from collections import deque

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


def bfs(sx, sy):
    result = 0
    count = [[-1] * w for i in range(h)]
    count[sx][sy] = 0
    d = deque([[sx, sy]])
    while d:
        x, y = d.popleft()
        result = count[x][y]
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            if (
                not (0 <= tx < h)
                or not (0 <= ty < w)
                or maze[tx][ty] == "#"
                or count[tx][ty] != -1
            ):
                continue
            else:
                count[tx][ty] = count[x][y] + 1
                d.append([tx, ty])
    return result


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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())
    
dij=[-1,0,1,0,-1]
def update(i,j,x,d,q):
    if(d[i][j]!=-1):return
    d[i][j]=x
    q.append((i,j))

m=-1
for i in range(h):
    for j in range(w):
        if(s[i][j]=="#"):continue
        d=[[-1 for ii in range(w)] for jj in range(h)]
        q=[]
        update(i,j,0,d,q)
        while q:
            xy=q.pop(0)
            xx=xy[0]
            yy=xy[1]
            for k in range(4):
                ni=xx+dij[k]
                nj=yy+dij[k+1]
                if(ni<0 or ni>=h or nj<0 or nj>=w):continue
                if(s[ni][nj]=="#"):continue
                update(ni,nj,d[xx][yy]+1,d,q)
        for ii in range(h):
            for jj in range(w):
                m=max(d[ii][jj],m)
print(m)

Submission status: Accepted

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

def f(i, j):
    t = [[-1]*w for j in range(h)]
    t[i][j] = 0
    q = [(i,j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and s[y-1][x] != "#" and t[y-1][x] == -1:
            t[y-1][x] = t[y][x] + 1
            q.append((y-1,x))
        if y + 1 < h and s[y+1][x] != "#" and t[y+1][x] == -1:
            t[y+1][x] = t[y][x]+1
            q.append((y+1,x))
        if x - 1 >= 0 and s[y][x-1] != "#" and t[y][x-1] == -1:
            t[y][x-1] = t[y][x] + 1
            q.append((y,x-1))
        if x + 1 < w and s[y][x+1] != "#" and t[y][x+1] == -1:
            t[y][x+1] = t[y][x] + 1
            q.append((y,x+1))
    return max(max(tt) for tt in t)
result = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            result = max(result,f(i,j))
print(result)

Submission status: Accepted

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

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


d = [[float("inf")]*(H*W) for i in range(H*W)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(H-1):
    for j in range(W-1):
        if S[i][j] == ".":
            if S[i+1][j] == ".":
                d[i*W+j][(i+1)*W+j] = 1
                d[(i+1)*W+j][i*W+j] = 1
            if S[i][j+1] == ".":
                d[i*W+j][i*W+(j+1)] = 1
                d[i*W+(j+1)][i*W+j] = 1
for i in range(W-1):
    if S[H-1][i] == "." and S[H-1][i+1] == ".":
        d[(H-1)*W+i][(H-1)*W+(i+1)] = 1
        d[(H-1)*W+(i+1)][(H-1)*W+i] = 1
for i in range(H-1):
    if S[i][W-1] == "." and S[i+1][W-1] == ".":
        d[i*W+(W-1)][(i+1)*W+(W-1)] = 1
        d[(i+1)*W+(W-1)][i*W+(W-1)] = 1

for i in range(H*W):
    d[i][i] = 0 #自身のところに行くコストは０

ans = 0
data = warshall_floyd(d)
for items in data:
    for item in items:
        if item != float("inf"):
            ans = max(ans, item)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc151/tasks/abc151_d

from collections import deque

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


def bfs(sx, sy):
    count = [[0] * w for i in range(h)]
    check = [[0] * w for i in range(h)]
    check[sx][sy] = 1
    d = deque([[sx, sy]])
    while d:
        x, y = d.popleft()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            if (
                not (0 <= tx < h)
                or not (0 <= ty < w)
                or maze[tx][ty] == "#"
                or check[tx][ty] == 1
            ):
                continue
            else:
                count[tx][ty] = count[x][y] + 1
                check[tx][ty] = 1
                d.append([tx, ty])

    result = 0
    for k in count:
        for l in k:
            result = max(result, l)
    return result


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

Submission status: Accepted

Solution code:
import math
import itertools
from collections import deque
import bisect
import heapq

def IN(): return int(input())
def sIN(): return input()
def lIN(): return list(input())
def MAP(): return map(int,input().split())
def LMAP(): return list(map(int,input().split()))
def TATE(n): return [input() for i in range(n)]
ans = 0

def bfs(sx,sy):
    d = [[-1] * w for i in range(h)]
    MAX = 0

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

    que = deque([])
    que.append((sx, sy))#スタート座標の記録
    d[sx][sy] = 0#スタートからスタートへの最短距離は0

    while que:#中身がなくなるまで
        p = que.popleft()
       
        for m in range(4):#現在地から4方向の移動を考える
            nx = p[0] + dx[m]
            ny = p[1] + dy[m]

            if 0 <= nx < h and 0 <= ny < w:
              if maze[nx][ny] != "#" and d[nx][ny] == -1:
                que.append((nx, ny))#↑格子点からでない＆壁でない＆まだ通ってない
                d[nx][ny] = d[p[0]][p[1]] + 1

    for k in range(h):
      MAX = max(max(d[k]),MAX)
      
    return MAX

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

for i in range(h):#sx座標指定0~h-1
  for j in range(w):#sy座標指定0~w-1
    if maze[i][j] == '.':
      ans = max(bfs(i,j),ans)
      
print(ans)

Submission status: Accepted

Solution code:
import sys
h, w = map(int, input().split())
C = [list(input()) for i in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        visited = [[0 for i in range(w)] for i in range(h)]
        data = []
        if C[i][j] == '.':
            data.append([i, j])
            visited[i][j] = 1
            
            dy_dx = [[1,0], [0,1], [-1,0], [0,-1]]
            
            while len(data) > 0:
                now = data.pop(0)
                for k in range(4):
                    y = now[0] + dy_dx[k][0]
                    x = now[1] + dy_dx[k][1]
                    
                    if 0 <= y and y < h and 0 <= x and x < w:
                        if C[y][x] != '#' and visited[y][x] == 0:
                            #移動回数カウント
                            visited[y][x] = visited[now[0]][now[1]] + 1
                            data.append([y, x])
        for l in range(h):
            for m in range(w):
                ans = max(ans, visited[l][m])

print(ans - 1)

Submission status: Accepted

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


def dfs(a,b):
    d = deque([])
    d.append([a,b])
    n = [1,0,-1,0]
    m = [0,1,0,-1]
    l = [[-1]*w for _ in range(h)]
    l[a][b]=0
    while len(d)!=0:
        #print(l)
        s = d.popleft()
        s1,s2 = s[0],s[1]
        for i in range(4):
            if 0<=s1+m[i] and s1+m[i]<=h-1 and 0<=s2+n[i] and s2+n[i]<=w-1:
                if sss[s1+m[i]][s2+n[i]]=="." and l[s1+m[i]][s2+n[i]]==-1:
                    d.append([s1+m[i],s2+n[i]])
                    l[s1+m[i]][s2+n[i]] = l[s1][s2]+1
    t = 0
    for j in l:
      for m in j:
        t = max(t,m)
    return t
t = 0
for i in range(w):
    for j in range(h):
      if sss[j][i]==".":
        t = max(t,dfs(j,i))
print(t)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
field = ['#' * (W+2)] * (H+2)
for i in range(1, H+1):
    field[i] = '#' + input() + '#'
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
ans = 0
q = deque()

for si in range(1, H+1):
    for sj in range(1, W+1):
        if field[si][sj] == '#':
            continue
        q.clear()
        q.append([si, sj])
        dist = [[-1 for _ in range(W+2)] for _ in range(H+2)]
        dist[si][sj] = 0
        dist_max = 0
        while len(q) != 0:
            current = q.popleft()
            ci = current[0]
            cj = current[1]

            for d in range(4):
                next_i = ci + di[d]
                next_j = cj + dj[d]

                if field[next_i][next_j] == '#':
                    continue

                if dist[next_i][next_j] != -1:
                    continue

                q.append([next_i, next_j])
                dist[next_i][next_j] = dist[ci][cj] + 1
                dist_max = max(dist_max, dist[next_i][next_j])
        ans = max(ans, dist_max)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(S,s,H,W):
    dx=[1,0,0,-1]
    dy=[0,1,-1,0]
    d=deque([s])
    visited=[[-1 for _ in range(W)] for _ in range(H)]
    visited[s[0]][s[1]]=0
    max_time_=0
    while d:
        root=d.popleft()
        prev=visited[root[0]][root[1]]
        for n in range(len(dx)):
            n_x=root[0]+dx[n]
            n_y=root[1]+dy[n]
            if (0<=n_x<=H-1) and (0<=n_y<=W-1):
                if S[n_x][n_y]=="." and visited[n_x][n_y]==-1:
                    d.append((n_x,n_y))
                    visited[n_x][n_y]=prev+1
                    max_time_=max(max_time_,prev+1)
    return max_time_

def main():
    #スタート地点を固定し、全てのマスへの移動回数を全探索し、最大移動回数を求める。
    #スタート地点を全探索し、最大移動回数内の最大値を答えとして出力する。
    #input
    H,W=map(int,input().strip().split())
    S=[list(input()) for _ in range(H)]
    
    #スタート地点を固定し、sg_listに格納。
    #スタート地点〜全ての"."を探索し、最も遠い点をsg_listに格納する。
    #最も遠い点までの移動回数をturns_listに格納する。
    sg_list=[]
    max_time=0
    for w in range(W):
        for h in range(H):
            if S[h][w]=="." and (h,w) not in sg_list:
                start=(h,w)
                sg_list.append((h,w))
                max_time=max(max_time,bfs(S,start,H,W))
    return max_time

if __name__=="__main__":
    print(main())

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    from collections import deque
    import copy
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [[0] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    a = deque([])
    for i in range(1, h + 1):
        s = input()
        for j in range(1, w + 2):
            if s[j - 1] == ".":
                cm[i][j] = -1
                a.append([i, j])
    ans = 0
    for y, x in a:
        dm = copy.deepcopy(cm)
        que.append([y, x, 0])
        dm[y][x] = 0
        while len(que) > 0:
            y, x, r = que.popleft()
            if ans < r + 1:
                ans = r + 1
            if dm[y + 1][x] == -1:
                dm[y + 1][x] = r + 1
                que.append([y + 1, x, r + 1])
            if dm[y - 1][x] == -1:
                dm[y - 1][x] = r + 1
                que.append([y - 1, x, r + 1])
            if dm[y][x + 1] == -1:
                dm[y][x + 1] = r + 1
                que.append([y, x + 1, r + 1])
            if dm[y][x - 1] == -1:
                dm[y][x - 1] = r + 1
                que.append([y, x - 1, r + 1])
    print(ans - 1)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np

def main():
    H, W = list(map(int, input().split()))
    N = H * W
    S = [[line for line in range(W)] for row in range(H)]
    for i in range(H):
        row = input()
        for j, line in enumerate(row):
            S[i][j] = line

    data = np.zeros([N, N])
    for i in range(H):
        for j in range(W):
            n = W * i + j
            if j<W-1 and S[i][j]=='.' and S[i][j+1]=='.':
                data[n][n+1] = data[n+1][n] = 1
            if i<H-1 and S[i][j]=='.' and S[i+1][j]=='.':
                data[n][n+W] = data[n+W][n] = 1

    G = csgraph_from_dense(data)
    answer = 0
    for n in range(N):
        result = dijkstra(G, indices=n)
        result = [x for x in result if x!=np.inf]
        answer = max(answer, max(result))
    print(int(answer))
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    from collections import deque
    import copy
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [[0] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    a = deque([])
    for i in range(1, h + 1):
        s = input()
        for j in range(1, w + 2):
            if s[j - 1] == ".":
                cm[i][j] = -1
                a.append([i, j])
    ans = 0
    for b in a:
        dm = copy.deepcopy(cm)
        que.append(b[0])
        que.append(b[1])
        que.append(0)
        dm[b[0]][b[1]] = 0
        while len(que) > 0:
            y = que.popleft()
            x = que.popleft()
            r = que.popleft()
            if ans < r + 1:
                ans = r + 1
            if dm[y + 1][x] == -1:
                dm[y + 1][x] = r + 1
                que.append(y + 1)
                que.append(x)
                que.append(r + 1)
            if dm[y - 1][x] == -1:
                dm[y - 1][x] = r + 1
                que.append(y - 1)
                que.append(x)
                que.append(r + 1)
            if dm[y][x + 1] == -1:
                dm[y][x + 1] = r + 1
                que.append(y)
                que.append(x + 1)
                que.append(r + 1)
            if dm[y][x - 1] == -1:
                dm[y][x - 1] = r + 1
                que.append(y)
                que.append(x - 1)
                que.append(r + 1)
    print(ans - 1)
main()

Submission status: Accepted

Solution code:
from collections import deque
import copy
H, W = map(int, input().split())
 
start = set()
for y in range(H):
  for x, w in enumerate(input()):
    if w == '.':
      start.add((x,y))

score = 0
ssize = [(-1,0),(0,-1),(1,0),(0,1)]
for xy in start:
  d = deque()
  d.append((xy+(0,)))
  step = 0
  can = copy.deepcopy(start)
  can.remove(xy)
  while len(d) > 0:
    now = d.popleft()
    step = now[2]
    for xs, ys in ssize:
      nxt = (now[0]+xs, now[1]+ys)
      if nxt in can:
        d.append(nxt+(step+1,))
        can.remove(nxt)
  score = max(step, score)
  
print(score)

Submission status: Accepted

Solution code:
from collections import deque
import copy
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = set()
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '.':
      start.add((x, y))

score = -1
ssize = [(-1,0),(0,-1),(1,0),(0,1)]
for xy in start:
  d = deque()
  d.append((xy+(0,)))
  step = 0
  can = copy.deepcopy(start)
  can.remove(xy)
  while len(d) > 0:
    now = d.popleft()
    step = now[2]
    for xs, ys in ssize:
      nxt = (now[0]+xs, now[1]+ys)
      if nxt in can:
        d.append(nxt+(step+1,))
        can.remove(nxt)
  score = max(step, score)
  
print(score)

Submission status: Accepted

Solution code:
import copy
h, w = map(int, input().split())
grid = []
scoresInit = [[500 for i in range(w)] for j in range(h)]

for i in range(h):
  grid.append(list(input()))
  for j in range(w):
    if grid[i][j] == "#":
      scoresInit[i][j] = -1

ans = 0
for i in range(h):
  for j in range(w):
    scores = copy.deepcopy(scoresInit)
    if grid[i][j] == "#":
      continue
    scores[i][j] = 0
    queue = [(i,j)]
    while queue != []:
      (x, y) = queue.pop(0)
      if x-1 >= 0 and grid[x-1][y] != "#" and scores[x-1][y] > scores[x][y]+1:
        scores[x-1][y] = scores[x][y]+1
        queue.append((x-1, y))
      if x+1 < h and grid[x+1][y] != "#" and scores[x+1][y] > scores[x][y]+1:
        scores[x+1][y] = scores[x][y]+1
        queue.append((x+1, y))
      if y-1 >= 0 and grid[x][y-1] != "#" and scores[x][y-1] > scores[x][y]+1:
        scores[x][y-1] = scores[x][y]+1
        queue.append((x, y-1))
      if y+1 < w and grid[x][y+1] != "#" and scores[x][y+1] > scores[x][y]+1:
        scores[x][y+1] = scores[x][y]+1
        queue.append((x, y+1))
    ansTmp = 0
    for k in range(len(scores)):
      ansTmp = max(ansTmp, max(scores[k]))
    ans = max(ans, ansTmp)
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))#入力を全行数分取得
#配列を生成する。np.zeros()は全てを0に初期化する関数
#第１引数は H*W,H*Wの２次元配列、第２引数はbool型を意味する
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)#divmod()は商と余りを求める関数。（r:商　c:余り）

    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
        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:
from collections import deque

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

def bfs(sx, sy):
    que = deque([])
    que.append((sx, sy))
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = [[-1] * w for i in range(h)]
    d[sy][sx] = 0
    while que:
        s = que.popleft()
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and d[ny][nx] == -1:
                que.append((nx, ny))
                d[ny][nx] = d[s[1]][s[0]] + 1
    
    tmp = 0
    for i in range(h):
        for j in range(w):
            tmp = max(tmp, d[i][j])
    
    return tmp

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

print(ans)