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

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

Submission status: Accepted

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

	max_step = 0	 
	for i in range(H * W):
		#yはWで割り切れる位置、xはWのあまりの位置になる
		sy, sx = i // W, i % W
		#壁なら以降全部飛ばす
		if S[sy][sx] == "#":
			continue
		
		#-1で未訪問を表す
		steps = [[-1] * W for _ in range(H)]

		#sx,syを0で初期訪問位置とする
		steps[sy][sx] = 0
		#queueで発見済みだが未訪問の頂点を格納
		queue = [(sy, sx)]
		#発見済み+未訪問の点がなくなるまで続ける
		while len(queue) >= 1:
			#初手は初期位置がpopする
            #発見済み+未訪問の地点をcy,cxに格納してqueueからはpopする
			cy, cx = queue.pop(0)
			#上下左右の点をdy,dxに代入
			for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
				ny, nx = cy + dy, cx + dx
				#迷路の範囲外でないか確認
				if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
					continue
				#壁か訪問済みでないか確認
				if S[ny][nx] == "#" or steps[ny][nx] >= 0:
					continue
				#ここまで来たら移動可能であることがわかるので発見済み+未訪問にny,nxを追加
				queue.append((ny, nx))
				#移動前(cy,cx)から距離+1であることを記録
				steps[ny][nx] = steps[cy][cx] + 1
		# print("steps = {} after while".format(steps))
	 
		#i = H*Wの時のmaxを算出
		ms = max(max(r) for r in steps)
		#これまでのmaxと比較
		max_step = max(ms, max_step)
	print(max_step)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
from collections import deque


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

def calc_max_dist(start_x, start_y):
    dist = [[-1] * W for _ in range(H)]
    que = deque()

    dist[start_x][start_y] = 0
    que.append((start_x, start_y))

    while len(que):
        current_x, current_y = que.popleft()
        for i in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            near_x, near_y = current_x + i[0], current_y + i[1]

            if not (0 <= near_x < H and 0 <= near_y < W):
                continue

            if S[near_x][near_y] == '.' and dist[near_x][near_y] == -1:
                dist[near_x][near_y] = dist[current_x][current_y] + 1
                que.append((near_x, near_y))

    return max([max(_) for _ in dist])


print(max([calc_max_dist(x, y) for x in range(H) for y in range(W) if S[x][y] == '.']))

Submission status: Accepted

Solution code:
from collections import deque

def bfs(sx, sy):
    dist = [[-1]*W for _ in range(H)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])
    res = 0
    
    while q:
        cx, cy = q.popleft()
        
        for nx, ny in [(cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)]:
            if not (0<=nx<H and 0<=ny<W):
                continue
            
            if S[nx][ny]=='.' and dist[nx][ny]==-1:
                dist[nx][ny] = dist[cx][cy]+1
                q.append((nx, ny))
                res = max(res, dist[nx][ny])
    
    return res

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

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

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
inf = 10**8
dist = [[inf for i in range(h*w)] for j in range(h*w)]

G = [input() for _ in range(h)]

for i in range(h):
    for j in range(w):
        if G[i][j] == '.':
            dist[i * w + j][i * w + j] = 0
            for dx,dy in [[-1,0],[1,0],[0,1],[0,-1]]:
                if 0<=i+dx<h and 0<=j+dy<w and G[i+dx][j+dy] == '.':
                    dist[i * w + j][(i + dx) * w + j + dy] = 1
                    dist[(i + dx) * w + j + dy][i * w + j] = 1

for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k])

ans = 0
for i in range(h*w):
    for j in range(h*w):
        if dist[i][j] < inf:
            ans = max(ans,dist[i][j])

print(ans)

Submission status: Accepted

Solution code:
import copy

MOVEMENT = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    for point in points:
        # print(point)
        map = copy.deepcopy(MAP)
        step = search(map, point)
        max_step = max(step, max_step)
    print(max_step)


def search(map, point):
    map[point[0]][point[1]] = "0"

    currents = [point]
    new_points = []
    cost = 1
    while True:
        if len(currents) == 0:
            if len(new_points) == 0:
                # print_map(map)
                return get_max_cost(map)
            currents = new_points
            new_points = []
            cost += 1
        point = currents.pop(0)

        for m in MOVEMENT:
            next_point = (point[0] + m[0], point[1] + m[1])
            if is_valid(map, next_point):
                map[next_point[0]][next_point[1]] = str(cost)
                new_points.append(next_point)


def print_map(map):
    for row in map:
        print("".join(row))


def is_valid(map, point):
    if point[0] < 0 or point[1] < 0:
        return False
    if point[0] >= len(map) or point[1] >= len(map[0]):
        return False
    if map[point[0]][point[1]] == ".":
        return True
    return False


def get_max_cost(map):
    max_cost = 0
    for row in map:
        for col in row:
            if col == '.':
                return None
            elif col == '#':
                continue
            max_cost = max(max_cost, int(col))
    return max_cost


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W = map(int,input().split())
    S = [list(str(input())) for _ in range(H)]
    INF = float('inf')
    
    def maiz(x,y):
        if S[x][y] == "#":
            return -1
        else:
            length = [[INF for _ in range(W)] for _ in range(H)]
            length[x][y] = 0
            dx,dy = [1,0,-1,0],[0,1,0,-1]
            queue = deque()
            queue.append((x,y))
            while queue:
                x,y = queue.popleft()
                for i in range(4):
                    nx,ny = x+dx[i],y+dy[i]
                    if (0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] == "." and length[nx][ny] == INF):
                        queue.append((nx,ny))
                        length[nx][ny] = min(length[nx][ny],length[x][y] + 1)
            num = 0
            for i in range(H):
                for j in range(W):
                    if length[i][j] != INF:
                        num = max(num,length[i][j])
            return num
    
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans,maiz(i,j))
            
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
S_=[[] for i in range(H)]
for i in range(H):
  for j in range(W):
    S_[i].append(S[i][j])
def chkS(i,j,H,W):
  if 0<=i<H and 0<=j<W:
    return True
  else:
    return False
import copy
  
def tansaku(i,j,__):
  global H,W,S
  X=[]
  #ue
  ni=i
  nj=j-1
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='#':
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass
    
  #sita
  ni=i
  nj=j+1
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='#':
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass
    
  #migi
  ni=i+1
  nj=j
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='#':
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass
    
    
  #hidari
  ni=i-1
  nj=j
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='#':
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass

  if len(X)==0:
    return X,S[i][j]
  else:
    return X,__+1

  
ans=0
for i in range(H):
  for j in range(W):
    if S_[i][j] =='.':
      _=[[i,j]]
      S=copy.deepcopy(S_)
      S[i][j]=0
      __=0
      while len(_)>0:
        _X=[]
        for NEXT in _:
          X,__=tansaku(NEXT[0],NEXT[1],__)
          _X.extend(X)
        _=_X
      if __>ans:
        ans=__
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for si in range(H):
    for sj in range(W):
      if S[si][sj] == '#':
        continue

      dist = [[-1 for _ in range(W)] for _ in range(H)]
      q = deque()

      start = (si, sj)
      if dist[si][sj] == -1:
        dist[si][sj] = 0
        q.append(start)

      while q:
        qi, qj = q.popleft()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          if dist[ni][nj] == -1:
            dist[ni][nj] = dist[qi][qj]+1
            q.append((ni, nj))
            ans = max(ans, dist[ni][nj])
  return ans


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

Submission status: Accepted

Solution code:
from collections import deque

INF = -1

sizeI, sizeJ = map(int, input().split())
a = [input().rstrip() for _ in range(sizeI)]

def bfs(startI, startJ):
    dist = [[INF for _ in range(sizeJ)] for _ in range(sizeI)]
    dist[startI][startJ] = 0
    q = deque([(startI, startJ)])
    while q:
        i, j = q.pop()
        curDist = dist[i][j]
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < sizeI and 0 <= nj < sizeJ and dist[ni][nj] == INF and a[ni][nj] == '.':
                dist[ni][nj] = 1 + curDist
                q.appendleft((ni, nj))
    return max([max(row) for row in dist])

ret = -float('inf')
for i in range(sizeI):
    for j in range(sizeJ):
        if a[i][j] == '.':
            ret = max(ret, bfs(i, j))
print(ret)

Submission status: Accepted

Solution code:
from collections import deque
import copy

def cha(maze,h,w):
    maze = copy.deepcopy(maze)
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                maze[i][j] = 10**10
            if maze[i][j] == "#":
                maze[i][j] = -1
    return maze

def bfs(maze,sy,sx):
    maze = copy.deepcopy(maze)
    maze[sy][sx] = 0
    que = deque([[sy,sx]])
    while que:
        y,x = que.popleft()
        for next_y,next_x in [(y+1,x),(y-1,x),(y,x+1),(y,x-1)]:
            if maze[next_y][next_x] == -1:
                continue
            dist = maze[next_y][next_x]
            if dist > maze[y][x] + 1:
                maze[next_y][next_x] = maze[y][x] + 1
                que.append([next_y,next_x])
    return maze

def search(maze):
    c = 0
    for i in maze:
        i.append(c)
        c = max(i)
    return c

def _main():
    h,w = map(int,input().split())
    maze = [["#"]*w]
    for _ in range(h):
        maze.append(list(input()))
    maze.append(["#"]*w)
    for i in range(h+2):
        maze[i].insert(0,"#")
        maze[i].insert(w+1,"#")
    C = 0
    for sy in range(h+2):
        for sx in range(w+2):
            if maze[sy][sx] == ".":
                C = max((search(bfs(cha(maze,h+2,w+2),sy,sx)),C))
    print(C)

if __name__=="__main__":
    _main()

Submission status: Accepted

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

maze=[]
INF=10**6
dx=[1,0,-1,0]
dy=[0,1,0,-1]

#マップ入力
for i in range(h):
    row=list(input())
    maze.append(row)


ans=0
for i in range(h):
    for j in range(w):
        queue=deque()
        d=[]
        used=[]
        for p in range(h):
            used.append([False for k in range(w)])
            d.append([INF for k in range(w)])
            
        if maze[i][j]==".":
            d[i][j]=0
            used[i][j]=True
            queue.append([i,j])

            while len(queue)>0:
                y,x=queue.popleft()
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=ny<h and 0<=nx<w:
                        if d[ny][nx]>d[y][x]+1 and maze[ny][nx]=="." and 0==used[ny][nx]:
                            d[ny][nx]=d[y][x]+1
                            ans=max(ans,d[ny][nx])
                            queue.append([ny,nx])
                            used[ny][nx]=True
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


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

INF = 10 ** 6
m = [[10 ** 6] * W for _ in range(H)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


def bfs(y, x):
    q = deque()
    q.append((y, x))

    while len(q):
        y, x = q.popleft()

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

            if (0 <= ny < H and 0 <= nx < W and
                m[ny][nx] == INF and S[ny][nx] != '#'):

                q.append((ny, nx))
                m[ny][nx] = m[y][x] + 1

ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] != "#":
            m = [[10 ** 6] * W for _ in range(H)]
            m[y][x] = 0
            bfs(y, x)
            for i in range(H):
                for j in range(W):
                    if m[i][j] != INF:
                        ans = max(ans, m[i][j])

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque
H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque([[sx, sy]])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(len(dx)):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == -1\
                and maze[nx][ny] == ".":
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
                    q.append([nx, ny])
    dist = -1
    for i in range(H):
        dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x,y))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
#-------------------------------------------------------------------
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
H,W = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

S=[ "" for _ in range(H+2) ]
#p(S)

S[0]="#"*(W+2)
S[H+1]="#"*(W+2)
for h in range(1,H+1):
	s = input()
	S[h] = "#" + s + "#"

#p(S)

XY=[[1,0],[-1,0],[0,1],[0,-1]]

INF=float("inf") # 正の無限大
ans=0

from collections import deque

for h in range(1,H+1):
	for w in range(1,W+1):

		if S[h][w]=="#": continue

		M=[[ INF for w in range(W+2) ] for h in range(H+2)]
		M[h][w]=0

		Q = deque()
		Q.append([h,w])
		mmax=0

		#p("Q=",Q)
		
		while Q:
			h,w=Q.popleft()
			
			if S[h][w]=="#": continue
			
			m = M[h][w]
			mmax=max(mmax,m)
			for x,y in XY:
				if S[h+y][w+x]=="#": continue
				
				if M[h+y][w+x] > (m+1):
					M[h+y][w+x] = m+1
					Q.append([h+y,w+x])
					mmax=max(mmax,m+1)

			#p("h,w,Q,m=",h,w,Q,m)

		for MH in M:
			for m in MH:
				if m==INF: continue
				ans=max(ans,m)


#for m in M:
#	print(m)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
s = [input() for i in range(h)]
# print(s)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
res = -INF
for y in range(h):
    for x in range(w):
        if s[y][x] == '#':
            continue
        ans = 0
        dist = [[-1]*w for i in range(h)]
        dist[y][x] = 0
        q = deque([[x,y]])
        while q:
            v = q.popleft()
            # print(v)
            vx,vy = v[0],v[1]
            for dir in range(4):
                ny = vy + dy[dir]
                nx = vx + dx[dir]
                if ny<0 or ny>h-1 or nx<0 or nx>w-1:
                    continue
                if s[ny][nx] == '#' or dist[ny][nx] != -1:
                    continue
                dist[ny][nx] = dist[vy][vx] + 1
                ans = max(ans, dist[ny][nx])
                q.append([nx,ny])
        # if y == 0 and x == 0:
            # pprint.pprint(dist)
        res = max(res, ans)
print(res)

Submission status: Accepted

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

def calc_distance(maze):
    global maxd
    global sx, sy
    global nextx, nexty
    INF = 100000000

    field_x_length = len(maze[0])
    field_y_length = len(maze)

    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)

    queue = []

    queue.insert(0, (sy, sx))

    distance[sy][sx] = 0

    while True:
        y, x = queue.pop()

        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]


            if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
                if maxd < distance[y][x] + 1:
                    maxd = distance[y][x] + 1
                    nexty = ny
                    nextx = nx
        if len(queue) == 0: break

maxd = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            sx, sy = j, i
        else: continue
        distance = calc_distance(maze)
print(maxd)

Submission status: Accepted

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


def calc(sh, sw):
    dist = [[float('inf')] * W for i in range(H)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dist[sh][sw] = 0
    que = deque([[sh, sw]])

    while que:
        sh, sw = que.pop()
        for dh, dw in directions:
            if not ((0 <= sh + dh < H) and (0 <= sw + dw < W)):
                continue

            if G[sh + dh][sw + dw] == '#':
                continue

            if dist[sh + dh][sw + dw] != float('inf'):
                continue

            dist[sh + dh][sw + dw] = dist[sh][sw] + 1
            que.appendleft([sh + dh, sw + dw])

    ret = 0
    for d in dist:
        for w in range(W):
            if d[w] == float('inf'):
                continue
            ret = max(ret, d[w])

    return ret


ans = 0
for sh in range(H):
    for sw in range(W):
        if G[sh][sw] == '#':
            continue
        ans = max(ans, calc(sh, sw))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = ((1, 0), (0, 1), (-1, 0), (0, -1))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited = [[False] * w for _ in range(h)]
        visited[i][j] = True
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z + 1
                        visited[nx][ny] = True
print(ans)

Submission status: Accepted

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

def validPoint(i,j):
	if i < 0 or i >= H:
		return False
	if j < 0 or j >= W:
		return False
	return True

def wfs(start):
	search = deque([(start, 0)])
	dist = [[-1 for j in range(W)] for i in range(H)]
	#searched = [[False for j in range(W)] for i in range(H)]
	#searched[start[0]][start[1]] = True
	v = [(0,-1), (0,1), (-1,0), (1,0)]
	dist[start[0]][start[1]] = 0
	while len(search) > 0:
		s = search.popleft()
		i,j = s[0][0], s[0][1]
		d = s[1]
		if dist[i][j] < d:
			continue
		for (x,y) in v:
			if validPoint(i+x, j+y):
				if m[i+x][j+y] == "#":
					continue
				if dist[i+x][j+y] == -1 or dist[i+x][j+y] > d+1:
					dist[i+x][j+y] = d+1
					search.append(((i+x,j+y),d+1))
	return max([max(dist[i]) for i in range(H)])

ans = 0
for i in range(H):
	for j in range(W):
		if m[i][j] == "#":
			continue
		ans = max(ans, wfs((i,j)))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append([i, j, 0])
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        visited[i][j] = True
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        mx = 0
        while len(q) != 0:
            x, y, z = q[0]
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
                        visited[nx][ny] = True
                        ans = max(ans, z + 1)
            q.popleft()
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
h,w=map(int,input().split())
meiro = [list(input()) for i in range(h)]
#meiro[y][x]
def bfs(a,b):#a縦b横
    maxdist=0
    da=[1,-1,0,0]
    db=[0,0,1,-1]
    dist=[[-1]*w for i in range(h)]
    dist[a][b]=0
    stack=deque([(a,b)])
    while stack:
        y,x=stack.popleft()
        D=dist[y][x]
        for dy,dx in zip(da,db):
            X=x+dx
            Y=y+dy
            if 0<=Y and Y<=h-1 and X<=w-1 and 0<=X:
                if meiro[Y][X]=='.':
                    if dist[Y][X]==-1:
                        dist[Y][X]=D+1
                        stack.append((Y,X))
                    elif dist[Y][X]>0:
                        dist[Y][X]=min(dist[Y][X],D+1)
                else:
                    dist[Y][X]==-(10**6)
    return dist
saidai=0
for i in range(h):
    for j in range(w):
        if meiro[i][j]=='.':
            saidai=max(saidai,np.array(bfs(i,j)).max())
print(saidai)

Submission status: Accepted

Solution code:
import collections


def search(data, w, h, start):
    maps = [[-1] * w for i in range(h)]
    move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    que = collections.deque([(start[1], start[0])])
    maps[start[1]][start[0]] = 0
    result = 0
    while que:
        y, x = que.popleft()
        num = maps[y][x]
        for m in move:
            if 0 <= y+m[0] < h and 0 <= x+m[1] < w:
                if maps[y+m[0]][x+m[1]] != -1:
                    continue
                if data[y+m[0]][x+m[1]] == '#':
                    continue
                elif data[y+m[0]][x+m[1]] == '.':
                    maps[y+m[0]][x+m[1]] = num+1
                    result = max(result, maps[y+m[0]][x+m[1]])
                    que.append((y+m[0], x+m[1]))
    return result


def main():
    h, w = map(int, input().split())
    data = []
    for i in range(h):
        tmp = input()
        data.append([j for j in tmp])

    ans = 0
    for i in range(h*w-1):
        if data[i//w][i % w] == '.':
            ans = max(search(data, w, h, (i % w, i//w)), ans)
    print(ans)


main()

Submission status: Accepted

Solution code:
#First In First Outのキュー
from collections import deque #dequeを用いる

import copy #参照渡し

#入力
h,w= map(int,input().split())

maze = [list(input()) for _ in range(h)] #訪問先を変更するために、listにする

ans=0

def bfs(sx,sy,c):
  maxlen=0
  que = deque() #キューに要素を追加するときはque.append([i,j])、取り出すときはque.popleft()
  que.append([sx,sy,0]) #初期値
  c[sy][sx] = '@'
  dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]] # ↓、→、←、↑

  #bfs キューから取り出し、移動先をキューに追加、キューから取り出し、移動先をキューに追加...を繰り返す
  while que: #ゴールに着くまでにキューの要素がなくなったらゴール不可

    x,y,tmp = que.popleft() #キューから要素を取り出す（座標を取り出す）

    for dx,dy in dxy: #(x,y)→(next_x,next_y)の1マス分の移動を考える（上下左右で4パターン存在）

      if 0 <= x+dx < w and 0 <= y+dy < h and c[y+dy][x+dx]=='.': #(移動先は行列内) かつ (空きマスの場合)
        que.append([x+dx,y+dy,tmp+1]) #キューに移動先を追加して、移動先の手数を+1する
        c[y+dy][x+dx] = '@' #訪問済みは@に置換する
        maxlen=max(maxlen,tmp+1)# maxlenを更新
  return maxlen

for Sy in range(h):
  for Sx in range(w):
    Maze=copy.deepcopy(maze)
    if Maze[Sy][Sx]=='.':
      #print(Sy,Sx,Gy,Gx,Maze)
      Tmp=bfs(Sx,Sy,Maze)
      #print(Sy,Sx,Gy,Gx,Maze)
      ans=max(ans,Tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
h += 2; w += 2
maze = "#" * w
for _ in range(h-2):
    maze += "#" + input() + "#"
maze += "#" * w

def bfs(start):
    INF = h*w+1
    dist = [INF] * (h*w)
    dist[start] = 0
    q = deque([start])
    while q:
        cur_loc = q.popleft()
        cur_val = dist[cur_loc]
        for move in (-1,1,w,-w):
            next_loc = cur_loc + move
            if maze[next_loc] == "#":
                continue
            next_val = cur_val + 1
            if next_val >= dist[next_loc]:
                continue
            dist[next_loc] = next_val
            q.append(next_loc)
    return max(x for x in dist if x < INF)

ans = max(bfs(start) for start in range(h*w) if maze[start] != "#")
print(ans)

Submission status: Accepted

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

Glaph = [[float("inf") for i in range(H*W)] for j in range( H*W )]
for i in range(H):
  for j in range(W):
    
    if S[i][j] == ".":
 
      Glaph[i*W+j][i*W+j] = 0
      if i-1 != -1 and S[i-1][j] == ".":
        Glaph[i*W+j][(i-1)*W+j] = 1
      if i+1 != H and S[i+1][j] == ".":
        Glaph[i*W+j][(i+1)*W+j] = 1
      if j-1 != -1 and S[i][j-1] == ".":
        Glaph[i*W+j][i*W+(j-1)] = 1
      if j+1 != W and S[i][j+1] == ".":
        Glaph[i*W+j][i*W+(j+1)] = 1
        
def warshall_floyd(n) : # nは頂点数
  for i in range(n):      # 経由する頂点
    for j in range(n):    # 開始頂点
      for k in range(n):  # 終端
        Glaph[j][k] = min(Glaph[j][k], Glaph[j][i] + Glaph[i][k])
        
warshall_floyd(H*W)

ans = 0
for i in range(H*W):
  for j in range(H*W):
    if Glaph[i][j]!=float("inf"):
      ans=max(ans,Glaph[i][j])

print(ans)

Submission status: Accepted

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

max_step = 0
for i in range(H * W):
    sy, sx = i // W, i % W
    if S[sy][sx] == "#":
        continue

    steps = [[-1] * W for _ in range(H)]
    steps[sy][sx] = 0
    queue = [(sy, sx)]
    while len(queue) >= 1:
        cy, cx = queue.pop(0)
        for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
                continue
            if S[ny][nx] == "#" or steps[ny][nx] >= 0:
                continue
            queue.append((ny, nx))
            steps[ny][nx] = steps[cy][cx] + 1

    ms = max(max(r) for r in steps)
    max_step = max(ms, max_step)

print(max_step)

Submission status: Accepted

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

max_step = 0
for i in range(H * W):
    sy, sx = i // W, i % W
    if S[sy][sx] == "#":
        continue

    steps = [[-1] * W for _ in range(H)]
    steps[sy][sx] = 0
    queue = [(sy, sx)]
    while len(queue) >= 1:
        cy, cx = queue.pop(0)
        for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
                continue
            if S[ny][nx] == "#" or steps[ny][nx] >= 0:
                continue
            queue.append((ny, nx))
            steps[ny][nx] = steps[cy][cx] + 1

    ms = max(max(r) for r in steps)
    max_step = max(ms, max_step)

print(max_step)