Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    from collections import deque
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    res = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':

                que = deque([[i,j]])
                footprint = [[-1 for _ in range(W)] for _ in range(H)]
                footprint[i][j] = 0

                while que:
                    a, b = que.popleft()
                    c = footprint[a][b]
                    if c > res:
                        res = c

                    if a != 0 and footprint[a-1][b] == -1 and grid[a-1][b] == '.':
                        que.append([a-1, b])
                        footprint[a-1][b] = c + 1
                    if a != H-1 and footprint[a+1][b] == -1 and grid[a+1][b] == '.':
                        que.append([a+1, b])
                        footprint[a+1][b] = c + 1
                    if b != 0 and footprint[a][b-1] == -1 and grid[a][b-1] == '.':
                        que.append([a, b-1])
                        footprint[a][b-1] = c + 1
                    if b != W-1 and footprint[a][b+1] == -1 and grid[a][b+1] == '.':
                        que.append([a, b+1])
                        footprint[a][b+1] = c + 1

    print(res)
        


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

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

g = [[0] * (H * W) for _ in range(H * W)]
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if y - 1 >= 0 and S[y - 1][x] != '#':
            g[y * W + x][(y - 1) * W + x] = 1
        if y + 1 < H and S[y + 1][x] != '#':
            g[y * W + x][(y + 1) * W + x] = 1
        if x - 1 >= 0 and S[y][x - 1] != '#':
            g[y * W + x][y * W + x - 1] = 1
        if x + 1 < W and S[y][x + 1] != '#':
            g[y * W + x][y * W + x + 1] = 1
g = floyd_warshall(csgraph_from_dense(g))

result = 0
for i in range(H * W):
    for j in range(H * W):
        if g[i][j] == float('inf'):
            continue
        result = max(result, g[i][j])
print(int(result))

Submission status: Accepted

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '#': continue
                visited[ny][nx] = True
                dist[ny][nx] = dist[y][x] + 1
                q.append((ny, nx))
                #dist[ny][nx] = dist[y][x] + 1
                #visited[ny][nx] = True

        
        for p in range(H):
            ans = max(ans, max(dist[p]))
        
        #ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Submission status: Accepted

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

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
from collections import deque
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#': continue
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[y][x] = 1
        q = deque([(x,y)])
        while q:
            x,y = q.popleft()
            for dx,dy in dxy:
                nx,ny = x+dx,y+dy
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '#': continue
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.append((nx,ny))


        for i in range(H):
            ans = max(ans, max(dist[i]))
        #ans = max(ans, max(max(row) for row in dist))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '#': continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True

        """
        for i in range(H):
            ans = max(ans, max(dist[i]))
        """
        ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Submission status: Accepted

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True


        ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Submission status: Accepted

Solution code:
from collections import deque



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

ans = 0
dyx = [(1,0), (0,1),(-1,0), (0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#": continue
        dist = [[0 for _ in range(W)] for _ in range(H)] 
        visited = [[False for _ in range(W)] for _ in range(H)]
        visited[i][j] = True
        q = deque()
        q.append((i,j))
        while q:
            y,x = q.popleft()
            for dy,dx in dyx:
                ny, nx = y+dy, x+dx
                if not 0 <= ny <= H-1 or not 0 <= nx <= W-1 or visited[ny][nx] == True or S[ny][nx] == "#":
                    continue
                q.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                visited[ny][nx] = True



        ans = max(ans, max(max(row) for row in dist))

            

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '#' and i < 1000000]
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def bfs(h, w, m, start):

    import queue
    d = [[0 for i in range(w)]for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    flg = False

    a = queue.Queue()
    a.put(start)
    #print(start)
    while not a.empty():
        hh, ww = map(int, a.get())
        for i in range(4):
            nx, ny = ww+dx[i], hh+dy[i]
            if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "#" and d[ny][nx] == 0 and [ny,nx]!=start:
                a.put([ny, nx])
                d[ny][nx] = d[hh][ww]+1
    #print(d)
    return d[hh][ww]



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

ans=[]
for i in range(h):
    for j in range(w):
        if m[i][j]!="#":
            start=[i,j]
            ans.append(bfs(h,w,m,start))
            #print(ans)

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
h , w = map(int,input().split())
ma = [["#" for i in range(w+2)]]
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    kar.append("#")
    ma.append(kar)
ma.append(["#" for i in range(w+2)])
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if ma[i][j] == "#":
            continue
        elif ma[i][j] ==".":
            p = [[-1 for g in range(w+2)] for f in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i,j])
            while q:
                y,x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1,x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1,x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y,x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y,x-1])
            for l in range(1,h+1):
                ans = max(ans,max(p[l]))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000)

import numpy as np

h,w = map(int,input().split())
s = []

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

from collections import deque

def bfs(i,j,dist):
    lis = [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]
    for place in lis:
        if place[0]<0 or place[0]>=h or place[1]<0 or place[1]>=w:
            continue
        if seen[place[0]][place[1]] != -1 or s[place[0]][place[1]]=="#":
            continue
        seen[place[0]][place[1]] = dist+1
        que.append([place[0],place[1],dist+1])
    if len(que):
        new = que.popleft()
        bfs(new[0],new[1],new[2])
    else:
        return


mx = 0
for i in range(h):
    for  j in range(w):
        if s[i][j]=="#":
            continue
        seen = [[-1 for _ in range(w)]for _ in range(h)]
        que = deque()
        seen[i][j] = 0
        bfs(i,j,0)
        ast = np.array(seen)
        tmp = np.amax(ast)
        mx = max(mx,tmp)
        #print(seen)
            #print(*seen,sep="\n")
print(mx)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000)

import numpy as np

h,w = map(int,input().split())
s = []

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

from collections import deque

def bfs(i,j,dist):
    seen[i][j] = dist
    lis = [[i-1,j],[i,j-1],[i+1,j],[i,j+1]]
    for place in lis:
        if place[0]<0 or place[0]>=h or place[1]<0 or place[1]>=w:
            continue
        if seen[place[0]][place[1]] != -1 or s[place[0]][place[1]]=="#":
            continue
        if [place[0],place[1],dist+1] in que:
            continue
        que.append([place[0],place[1],dist+1])
    if len(que):
        new = que.popleft()
        bfs(new[0],new[1],new[2])
    else:
        return


mx = 0
for i in range(h):
    for  j in range(w):
        if s[i][j]=="#":
            continue
        seen = [[-1 for _ in range(w)]for _ in range(h)]
        que = deque()
        bfs(i,j,0)
        ast = np.array(seen)
        tmp = np.amax(ast)
        mx = max(mx,tmp)
        #print(seen)
            #print(*seen,sep="\n")
print(mx)

Submission status: Accepted

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

res = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
	for j in range(w):
		if s[i][j] == "#":
			continue
		queue = deque([[i,j]])
		visited = [[-1 for ii in range(w)] for jj in range(h)]
		visited[i][j] = 0
		while queue:
			l,m = queue.popleft()
			for k in range(4):
				x = l + dx[k]
				y = m + dy[k]
				if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] != -1 or s[x][y] == "#":
					continue
				visited[x][y] = visited[l][m] + 1
				queue.append([x,y])
		for ii in range(h):
			for jj in range(w):
				res = max(res,visited[ii][jj])
print (res)

Submission status: Accepted

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

res = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
	for j in range(w):
		if s[i][j] == "#":
			continue
		queue = deque([[i,j]])
		visited = [[0 for ii in range(w)] for jj in range(h)]
		visited[i][j] = 1
		while queue:
			l,m = queue.popleft()
			for k in range(4):
				x = l + dx[k]
				y = m + dy[k]
				if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] != 0 or s[x][y] == "#":
					continue
				visited[x][y] = visited[l][m] + 1
				queue.append([x,y])
		for ii in range(h):
			for jj in range(w):
				res = max(res,visited[ii][jj])
print (res-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, y, x, h, w):
  queue = deque([[y, x]])
  visited = list([-1] * w for i in range(h))
  visited[y][x] = 0
  num = 0

  while queue:
    a, b = queue.popleft()
    for i, j in ([0, 1], [0, -1], [1, 0], [-1, 0]):
       new_y, new_x = a + i, b + j
       if(new_y >= 0 and new_x >= 0 and new_y < h and new_x < w):
        if(maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1):
          visited[new_y][new_x] = visited[a][b] + 1
          num = max(num, visited[new_y][new_x])
          queue.append([new_y, new_x])
  return num
  
if __name__ == '__main__':
  y, x = map(int, input().split())
  maze = list(input() for i in range(y))
  num = -1
  for i in range(y):
    for j in range(x):
      if(maze[i][j] == '.'):
        num = max(num, bfs(maze, i, j, y, x))

  print(num)

Submission status: Accepted

Solution code:
from collections import deque

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

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 1
        plan.appendleft((i, j, step))
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                visited[next_y][next_x] = True
                if step > largest_step:
                    largest_step = step
                plan.appendleft((next_y, next_x, step + 1))
        if largest_step > max_step:
            max_step = largest_step

print(max_step)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import deque

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

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            # if step > largest_step:
            #     largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        # if largest_step > max_step:
        #     max_step = largest_step
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)

Submission status: Accepted

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



def bfs(sh,sw,meiro):
	que=deque([[sh,sw]])
	dist=[[-1 for _ in range(w)] for _ in range(h)]
	dist[sh][sw]=0

	while True:
		if que == deque([]):
			tmpmax=0
			for di in dist:
				tmptmpmax=max(di)
				if tmptmpmax>tmpmax:
					tmpmax=tmptmpmax
			return tmpmax
		
		
		check=que.popleft()
		hnow=check[0]
		wnow=check[1]
		
		dnow=dist[hnow][wnow]
		
		hnext=hnow-1
		wnext=wnow
		if 0 < hnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow+1
		wnext=wnow
		if h-1 > hnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow
		wnext=wnow-1
		if 0 < wnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1
		
		hnext=hnow
		wnext=wnow+1
		if w-1 > wnow:
			if dist[hnext][wnext]==-1 and meiro[hnext][wnext] == ".":
				que.append([hnext,wnext])
				dist[hnext][wnext]=dnow+1

roadlist=[]
for i in range(h):
	for j in range(w):
		if meiro[i][j] == ".":
			roadlist.append([i,j])

amax=0
for start in roadlist:
	tmp=bfs(start[0],start[1],meiro)
	if tmp > amax:
		amax = tmp

print(amax)

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)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

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

  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx
      if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1 and S[ny][nx] == '.':
        dist[ny][nx] = dist[y][x] + 1
        q.append([ny, nx])

  return dist

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    from collections import deque

    dist = [0]*(H*W)
    for s in range(H*W):
        search_list = deque([s])
        visited_set = set([])
        d = [0] * (H*W)
        while search_list:
            now = search_list.popleft()
            visited_set.add(now)
            h = now // W
            w = now % W
            if S[h][w] == '#':
                continue
            for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                new_h = h+i
                new_w = w+j
                new_s = new_h * W + new_w
                if new_h in [-1, H] or new_w in [-1, W]:
                    continue
                elif new_s in search_list:
                    continue
                elif new_s in visited_set:
                    continue
                elif S[new_h][new_w] == '#':
                    continue
                else:
                    d[new_s] = d[now]+1
                    search_list.append(new_s)
        dist[s] = max(d)
    print(max(dist))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
cmd = [[-1,0],[1,0],[0,1],[0,-1]]
h,w = map(int,input().split())
Map = [["#"]*(w+2)]
for _ in range(h):
    s = ["#"]+list(input())[:-1]+["#"]
    Map.append(s)
Map.append(["#"]*(w+2))
MAX = 0
for sx in range(1,w+1):
    for sy in range(1,h+1):
        p = 0
        if Map[sy][sx] == "#":
            continue
        q = deque([[sx,sy]])
        visidat = [[0]*(w+2) for _ in range(h+2)]
        while len(q) != 0:
            x,y = q.popleft()
            for cx,cy in cmd:
                newx = x + cx
                newy = y + cy
                if Map[newy][newx] == "#" or(newx ==sx and newy == sy):
                    continue
                else: 
                    if visidat[newy][newx] == 0:
                        visidat[newy][newx] += visidat[y][x] + 1
                        if p < visidat[newy][newx]:
                            p = visidat[newy][newx]
                        q.append([newx,newy])
        MAX = max(MAX,p)
print(MAX)

Submission status: Accepted

Solution code:
from  collections import deque
H,W=list(map(int,input().split()))
S=[list(input()) for i in range(H)]
dxdy=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for w in range(W):
    for h in range(H):
        if S[h][w]!='#':
            temp=0
            stack=deque([[h,w]])
            visited=[[-1 for i in range(W)]for j in range(H)]
            visited[h][w]=0
            while stack:
                x,y=stack.popleft()
                for i in dxdy:
                    nx,ny=x+i[0],y+i[1]
                    if 0<=nx<H and 0<=ny<W and S[nx][ny]!='#'and visited[nx][ny]==-1:
                        stack.append([nx,ny])
                        visited[nx][ny]=visited[x][y]+1
            temp=max([j for i in visited for j in i])
            ans=max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def abc151_d():
    H, W = map(int, readline().strip().split())
    # 周辺埋め
    grid = [['#'] * (W+2)]
    for ln in read().split():
        grid.append(['#'] + [s for s in ln.decode('UTF-8')] + ['#'])
    else:
        grid.append(['#'] * (W+2))

    # 指定位置からBFSして距離最長を返す
    from collections import deque
    def bfs_max_dist(sx, sy):
        dist = [[-1] * (W+2) for _ in range(H+2)]
        dist[sx][sy] = 0
        que = deque([(sx, sy)])
        dmax = 0
        while que:
            r, c = que.popleft()
            for i, j in ((r-1, c), (r, c-1), (r, c+1), (r+1, c)):
                if grid[i][j] == '#': continue
                if dist[i][j] != -1: continue
                dist[i][j] = dist[r][c] + 1
                que.append((i, j))
                dmax = max(dist[r][c] + 1, ans)
        return dmax

    # スタート地点を全探索で試して、最長距離が最も大きいものを答えとする
    ans = 0
    for r in range(1, H+1):
        for c in range(1, W+1):
            if grid[r][c] == '#': continue
            ans = max(bfs_max_dist(r, c), ans)
    print(ans)

abc151_d()

Submission status: Accepted

Solution code:
import queue
h, w = map(int,input().split())
way = ["" for i in range(h+1)]
way[h] = "#"*(w+1)
for i in range(h):
    way[i] = str(input())+"#"
G = [[[] for j in range(w)] for i in range(h)]
road = []
for i in range(h):
    for j in range(w):
        if way[i][j] == "#":
            continue
        else:
            road.append([i,j])
        if way[i+1][j] == ".":
            G[i][j].append([i+1,j])
        if way[i-1][j] == ".":
            G[i][j].append([i-1,j])
        if way[i][j+1] == ".":
            G[i][j].append([i,j+1])
        if way[i][j-1] == ".":
            G[i][j].append([i,j-1])
M = 0

for i in road:
    q = queue.Queue()
    q.put(i)
    t = [[-1 for k in range(w+1)] for j in range(h+1)]
    t[i[0]][i[1]] = 0
    while not q.empty():
        j = q.get()
        for l in G[j[0]][j[1]]:
            if t[l[0]][l[1]] == -1:
                t[l[0]][l[1]] = t[j[0]][j[1]] + 1
                q.put(l)
    for k in t:
        if M < max(k):
            M = max(k)

print(M)

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    from collections import deque
    import copy
    h,w=L()
    grid=[S() for i in range(h)]
    dist=[[-1]*w for i in range(h)]
    start=deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j]=='.':
                start.append((i,j))
                #(h,w):tuple, immutable
                
                dist[i][j]=-2
                
    def bfs(start,dist):
        ans=0
        d=0
        search=deque()
        #c=0
        while start:
            #print("#####################")
            #c+=1
            #print(c,ans)
            sty,stx=start.popleft()
            search.append((sty,stx))
            new_dist=copy.deepcopy(dist)
            new_dist[sty][stx]=0
            while search:
                tmph,tmpw=search.popleft()
                #print("$$$",end="")
                #print(tmph,tmpw,end="")
                #print("$$$")
                d=new_dist[tmph][tmpw]
                
                for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
                    new_h=tmph+dy
                    new_w=tmpw+dx
                    if new_h<0 or h<=new_h or new_w<0 or w<=new_w: continue
                    if new_dist[new_h][new_w]==-2:
                        new_dist[new_h][new_w]=d+1
                        search.append((new_h,new_w))
                        ans=max(ans,d+1)
                
                #for i in range(h):
                #    print("".join([str(a) if a>=0 else '#' if a==-1 else '.' for a in new_dist[i]]))
                #print("###")
        return ans
                
    print(bfs(start,dist)) 
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy
import sys
sys.setrecursionlimit(1000)
a,b=map(int,input().split())
maze=[list(input()) for i in range(a)]
ans=0
for i in range(a):
  for j in range(b):
    l=copy.deepcopy(maze)
    if l[i][j]!="#":
      l[i][j]=0
      q=deque([[i,j]])
      while q:
        h,w=q.popleft()
        if 0<=h-1<a and 0<=w<b:
          if l[h-1][w]==".":
            l[h-1][w]=l[h][w]+1
            q.append([h-1,w])
        if 0<=h+1<a and 0<=w<b:
          if l[h+1][w]==".":
            l[h+1][w]=l[h][w]+1
            q.append([h+1,w])
        if 0<=h<a and 0<=w-1<b:
          if l[h][w-1]==".":
            l[h][w-1]=l[h][w]+1
            q.append([h,w-1])
        if 0<=h<a and 0<=w+1<b:
          if l[h][w+1]==".":
            l[h][w+1]=l[h][w]+1
            q.append([h,w+1])
      s=0
      for x in l:
        for y in x:
          if type(y)==int:
            if y>s:
              s=y
      if ans<s:
        ans=s
print(ans)

Submission status: Accepted

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

INF = 1001001001
di = [-1,0,1,0]
dj = [0,-1,0,1]
ans = 0

def update(i, j, x):
    if dist[i][j] != INF: return
    dist[i][j] = x
    que.put([i,j])

import queue

# スタートの座標全てのパターンについて距離を計算
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#': continue
        dist = [[INF]*w for i in range(h)]
        que = queue.Queue()
        update(si, sj, 0)
        while que.qsize():
            p = que.get()
            i = p[0]; j = p[1]
            for drc in range(4):
                ni = i+di[drc]; nj = j+dj[drc]
                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)