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: Wrong Answer

Solution code:
import numpy as np
from collections import deque

def resolve():
    H, W = map(int, input().split())

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

    def dfs(st):

        INF = -1
        d = np.full((H, W), INF)

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

        que = deque()
        que.append(st)
        d[st[1]][st[0]] = 0

        while len(que):
            p = que.popleft()
            # print(p)

            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                if nx >= 0 and nx < W and ny >= 0 and ny < H and maze[ny][nx] != "#" and d[ny][nx] == INF:
                    # print("next is ", nx, ny)
                    que.append([nx, ny])
                    d[ny][nx] = d[p[1]][p[0]] + 1
                    # print(d)
                    # print(que)

        cost = np.max(d)
        idx = np.unravel_index(np.argmax(d), d.shape)
        # print(idx)
        # print(cost)
        return idx, cost

    max_cost = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == '.':
                st = [x, y]
                idx, cost = dfs(st)
                if cost > max_cost:
                    max_cost = cost 
        break
    
    # idx, cost = dfs(st)
    # idx, cost = dfs((idx[1], idx[0]))
    print(int(max_cost))

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import queue
INF = 100000000

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

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

def bfs(sx, sy):
    d = [[-1 for i in range(W)] for j in range(H)]
    d[sx][sy] = 0
    max_d = 0

    q = queue.Queue()
    q.put([sx, sy])

    while not q.empty():
        p = q.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx) & (nx < H) & (0 <= ny) & (ny < W):
                if (S[nx][ny] != "#") & (d[nx][ny] == -1):
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    q.put([nx, ny])
                    max_d = max(max_d, d[nx][ny])
                    if max_d == 39:
                        print(sx, sy, nx, ny, d[p[0]][p[1]], p[0], p[1])

    return max_d

res = 0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy] == ".":
            res = max(res, bfs(sx, sy))

print(res)

Submission status: Wrong Answer

Solution code:
import queue
INF = 100000000

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

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

def bfs(sx, sy):
    d = [[0 for i in range(W)] for j in range(H)]
    d[sx][sy] = 0
    max_d = 0

    q = queue.Queue()
    q.put([sx, sy])

    while not q.empty():
        p = q.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx) & (nx < H) & (0 <= ny) & (ny < W):
                if (S[nx][ny] != "#") & (d[nx][ny] == 0):
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    q.put([nx, ny])
                    max_d = max(max_d, d[nx][ny])

    return max_d

res = 0
for sx in range(H):
    for sy in range(W):
        res = max(res, bfs(sx, sy))

print(res)

Submission status: Wrong Answer

Solution code:
import queue
INF = 100000000

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

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

def bfs(sx, sy):
    d = [[-1 for i in range(W)] for j in range(H)]
    d[sx][sy] = 0
    max_d = 0

    q = queue.Queue()
    q.put([sx, sy])

    while not q.empty():
        p = q.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx) & (nx < H) & (0 <= ny) & (ny < W):
                if (S[nx][ny] != "#") & (d[nx][ny] == -1):
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    q.put([nx, ny])
                    max_d = max(max_d, d[nx][ny])

    return max_d

res = 0
for sx in range(H):
    for sy in range(W):
        res = max(res, bfs(sx, sy))

print(res)

Submission status: Wrong Answer

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF = 10 ** 2 
(H, W) = list(map(int,input().split()))
# print(H,W)

S = []
N = H * W
c = [[INF for j in range(N)] for u in range(N)]
d = [[INF for j in range(H*W)] for u in range(H*W)]

for k in range(N):
    c[k][k] = 0
    d[k][k] = 0

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

#print(S)

def vindex(i,j):
    global W
    return W * (i-1) + j -1

# print(vindex(H,W))
for i in range(1,H+1):
    for j in range(1,W+1):
        index = vindex(i,j)
        s = S[i-1][j-1]
        # print(index,s)
        if i != 1:
            index_t = vindex(i-1,j)
            sup = S[i-2][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
                
        if i != H:
            index_t = vindex(i+1,j)
            sup = S[i][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != 1:
            index_t = vindex(i,j-1)
            sup = S[i-1][j-2]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != W:
            index_t = vindex(i,j+1)
            sup = S[i-1][j]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1

#print("D",d)


for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j] , d[i][k]+d[k][j])
    #print(k,d)

ans = 0 
for i in range(N):
    for j in range(N):

        if (d[i][j] != INF and d[i][j] > ans):
            ans = d[i][j]

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[None for i in range(w)] for j in range(h)]
	for y in range(h):
		line = input()
		for x, z in enumerate(line):
			street[y][x] = True if z=="." else False
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				r = bfs(x, y, [i[::] for i in street])
				# print(f"x: {x} and y: {y} and r: {r} and max: {maximum}")
				# print(street)
				maximum = max(maximum, r)
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



main()

Submission status: Wrong Answer

Solution code:
def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[None for i in range(w)] for j in range(h)]
	for y in range(h):
		line = input()
		for x, z in enumerate(line):
			street[y][x] = True if z=="." else False
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				maximum = max(maximum, bfs(x, y, street.copy()))
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze, h, w, si, sj):
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])
    return max(map(max, score))
  
h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si  in range(h):
    for sj in range(w):
        if maze[si][sj] == "#":
            continue
        scores.append(bfs(maze, h, w, si, sj))
print(max(scores))

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze, h, w, si, sj):
    q = deque([[si, sj]])
    score = [[0] * w for i in range(h)]

    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and not score[ni][nj]:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])
    return max(sum(score, []))
  
h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si  in range(h):
    for sj in range(w):
        if maze[si][sj] == "#":
            continue
        scores.append(bfs(maze, h, w, si, sj))
print(max(scores))

Submission status: Wrong Answer

Solution code:
def warshall_floyd(n, d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])


INF = float('inf')

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

N = H * W
d = [[INF] * N for _ in range(N)]
for k in range(N):
    d[k][k] = 0

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

warshall_floyd(N, d)

result = 0 
for i in range(N):
    for j in range(N):
        if d[i][j] != INF and d[i][j] > result:
            result = d[i][j]

print(result)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))
res = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] != '.':
            continue
        visited = [[False for _ in range(w)] for _ in range(h)]
        visited[h - 1][w - 1] = True
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)
#             visited.append((c_i, c_j))
            for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
                if 0 <= n_i < h and 0 <= n_j < w and grid[n_i][n_j] == '.' and visited[n_i][n_j] == False:
                    queue.append((n_i, n_j, level + 1))
                    visited[n_i][n_j] = True
        res = max(res, level)
print(res)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))
res = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] != '.':
            continue
        visited = [[False for _ in range(w)] for _ in range(h)]
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)
#             visited.append((c_i, c_j))
            for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
                if 0 <= n_i < h and 0 <= n_j < w and grid[n_i][n_j] == '.' and visited[n_i][n_j] == False:
                    queue.append((n_i, n_j, level + 1))
                    visited[n_i][n_j] = True
        res = max(res, level)
print(res)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))
res = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] != '.':
            continue
        visited = [[-1] * w for _ in range(h)]
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)
#             visited.append((c_i, c_j))
            for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
                if 0 <= n_i < h and 0 <= n_j < w and grid[n_i][n_j] == '.' and visited[n_i][n_j] == -1:
                    queue.append((n_i, n_j, level + 1))
                    visited[n_i][n_j] = 1
        res = max(res, level)
print(res)

Submission status: Wrong Answer

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

def bfs(x,y):
  dis_map = [[None if s[i][j] == '.' else -1 for j in range(w)] for i in range(h)]
  q = deque()
  dis_map[y][x] = 0
  q.append((x,y))
  while q:
    i,j = q.popleft()
    for dx,dy in dir:
      ni = i+dx
      nj = j+dy
      if 0 <= ni <= w-1 and 0 <= nj <= h-1:
        if dis_map[nj][ni] == None:
          dis_map[nj][ni] = dis_map[j][i] + 1
          q.append((ni,nj))
  ans =  max(max(dis) for dis in dis_map)
  print(dis_map,ans)
  return ans
  


for i in range (h):
  for j in range (w): #スタートの選択
    if s[i][j]=='#':continue
    dis = bfs(j,i)
    if ans < dis:
      ans = dis
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

q = deque()

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

for h in range(H):
  for w in range(W):
    if m[h][w] == ".":
      q.append((h, w))

d = {}
for h in range(H):
  for w in range(W):
    d[(h, w)] = {}

while q:
  h, w = q.pop()
  if 0 <= h-1 and m[h-1][w] == ".":
    q.append((h-1, w))
    d[(h, w)][(h-1, w)] = 1
    d[(h-1, w)][(h, w)] = 1
  if h+1 < H  and m[h+1][w] == ".":
    q.append((h+1, w))
    d[(h, w)][(h+1, w)] = 1
    d[(h+1, w)][(h, w)] = 1
  if 0 <= w-1 and m[h][w-1] == ".":
    q.append((h, w-1))
    d[(h, w)][(h, w-1)] = 1
    d[(h, w-1)][(h, w)] = 1
  if w+1 < W  and m[h][w+1] == ".":
    q.append((h, w+1))
    d[(h, w)][(h, w+1)] = 1
    d[(h, w+1)][(h, w)] = 1
  
  m[h][w] = "#"

for it in range(H*W):
  for jt in range(H*W):
    for kt in range(H*W):
      i = divmod(it, W)
      j = divmod(jt, W)
      k = divmod(kt, W)
      d[j][k] = min(d[j].get(k, float("inf")), d[j].get(i, float("inf")) + d[k].get(i, float("inf")))

maxd = 0
for s in d.values():
  for g in s.values():
    if g <= H*W:
      maxd = max(g, maxd)
print(maxd)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
def main():
    hw = list(map(int, input().split()))
    s = np.zeros((hw[0],hw[1]), dtype=int)
    validpoints = []
    for i in range(hw[0]):
        tmp = input()
        tm = [None]*hw[1]
        for j in range(hw[1]):
            if tmp[j] == '.':
                tm[j] = 0
                validpoints.append((i,j))
            elif tmp[j] == '#':
                tm[j] = 1
        s[i] = np.array(tm)

    ma = 0
    # for i in validpoints:
    #     for j in validpoints:
    #         vis = np.array(s)
    #         cost = breadth(s,i,j,vis)
    #         if cost > ma:
    #             ma = cost
    for i in validpoints:
        vis = np.array(s)
        cost = breadth_max(s,i,vis)
        if cost > ma:
            ma = cost
    print(ma)

    # print(breadth(s,(2,0),(0,4)))
    # print(breadth(s,(0,0),(1,0)))
    
def breadth_max(ss, start, visited):
    newvis = np.array(visited)
    newvis[start] = 1

    down = (start[0]+1,start[1])
    up = (start[0]-1,start[1])
    right = (start[0],start[1]+1)
    left = (start[0],start[1]-1)
    child = [down,up,right,left]
    child = list(filter(lambda i: 0 <= i[0] < len(ss) and 0 <= i[1] < len(ss[0]) and visited[i[0],i[1]] == 0, child))

    if len(child) > 0:
        for i in child:
            newvis[i] = 1
        mi = 99999
        for i in child:
            co = breadth_max(ss,i,newvis)
            if mi > co:
                mi = co
        return 1+mi
    else:
        return 0


def breadth(ss, start, goal, visited):
    newvis = np.array(visited)
    newvis[start] = 1
    if start == goal:
        return 0
    down = (start[0]+1,start[1])
    up = (start[0]-1,start[1])
    right = (start[0],start[1]+1)
    left = (start[0],start[1]-1)
    child = [down,up,right,left]
    child = list(filter(lambda i: 0 <= i[0] < len(ss) and 0 <= i[1] < len(ss[0]) and visited[i[0],i[1]] == 0, child))
    if len(child) > 0:
        mi = 99999
        for i in child:
            co = breadth(ss,i,goal,newvis)
            if mi > co:
                mi = co
        return 1+mi
    else:
        return 1
    

# def breadth(ss, start, goal):
#     q = deque()
#     visited = np.array(ss)
#     visited[start] = 1
#     q.append(start)
#     c = 0
#     while not len(q) == 0:
#         v = q.pop()
#         if v == goal:
#             break
#         down = (v[0]+1,v[1])
#         up = (v[0]-1,v[1])
#         right = (v[0],v[1]+1)
#         left = (v[0],v[1]-1)
#         child = [down,up,right,left]
#         child = list(filter(lambda i: 0 <= i[0] < len(ss) and 0 <= i[1] < len(ss[0]) and visited[i[0],i[1]] == 0, child))

#         if len(child) > 0:
#             for i in child:
#                 visited[i] = 1
#                 q.append(i)
#             c += 1
        
#     return c

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans=0
dxy=[(0,1),(1,0),(0,-1),(-1,0)]
for x in range(w):
  for y in range(h):
    if S[y][x]=='#': continue
    q=deque([(x,y)])
    dist=[[0]*w for _ in range(h)]
    visited=[[0]*w for _ in range(h)]
    visited[y][x]=1
    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))
    ans = max(ans, max(max(row) for row in dist))
print(ans)

Submission status: Wrong Answer

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

ans=0
dxy=[(0,1),(1,0),(0,-1),(-1,0)]
for x in range(w):
  for y in range(h):
    if S[y][x]=='#': continue
    q=deque([(x,y)])
    memo=[[-1]*w for _ in range(h)]
    memo[y][x]=0
    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 S[ny][nx]=='#':continue
        if memo[ny][nx]<0:
          memo[ny][nx]=memo[y][x]+1
          q.append([nx,ny])
    ans=max(ans,max(max(row) for row in memo))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import numpy as np
import copy
from collections import deque

n, m = map(int, input().split())

# マス目と距離保存のための箱を作成
d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)


def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する．最後Nan判定
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = int(np.nanmax(np.array(local_d)))
    return d_max


dis = 0
for i in range(n):
    for j in range(m):
        if d[i][j] != "#":
            dis_i = tansaku(i, j, d)
            if dis_i > dis:
                dis = copy.copy(dis_i)

print(dis)

Submission status: Wrong Answer

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

ans=0
dxy=[(0,1),(1,0),(0,-1),(-1,0)]
for x in range(w):
  for y in range(h):
    if S[y][x]=='#': continue
    q=deque([(x,y,0)])
    memo=[[-1]*w for _ in range(h)]
    memo[y][x]=0
    while q:
      x,y,cnt=q.popleft()
      cnt+=1
      for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if S[ny][nx]=='#':continue
        if memo[ny][nx]<0:
          memo[ny][nx]=cnt
          q.append([nx,ny,cnt])
    ans=max(ans,max(max(row) for row in memo))
print(ans)

Submission status: Wrong Answer

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

ans=0
dxy=[(0,1),(1,0),(0,-1),(-1,0)]
for x in range(w):
  for y in range(h):
    if S[y][x]=='#': continue
    q=deque([(x,y,0)])
    memo=[[-1]*w for _ in range(h)]
    memo[y][x]=0
    while q:
      x,y,cnt=q.popleft()
      cnt+=1
      for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if S[ny][nx]=='#':continue
        if memo[ny][nx]<0:
          memo[ny][nx]=cnt
          q.append([nx,ny,cnt])
    ans=max(ans,max(max(memo)))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import numpy as np
import copy
from collections import deque

n, m = map(int, input().split())

# マス目と距離保存のための箱を作成
d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)


def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する．最後Nan判定
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = int(np.nanmax(np.array(local_d)))
    return d_max


dis = 0
for i in range(n):
    for j in range(m):
        dis_i = tansaku(i, j, d)
        if dis_i > dis:
            dis = copy.copy(dis_i)

print(dis)

Submission status: Wrong Answer

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()

    M = [input() for i in range(H)]

    def search(y, x):
        q = []
        m = [[0]*W for i in range(H)]

        m[y][x] = 0
        q = deque([(y,x, 0)])
        ans = 0
        while q:
            y, x, k = q.popleft()
            ans = max(ans, k)
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                yy = y + i
                xx = x + j

                if 0 <= xx < W and 0 <= yy < H:
                    if M[yy][xx] == "." and m[yy][xx] == 0:
                        m[yy][xx] = 1
                        q.append((yy, xx, k+1))

        return ans

    ans = 0
    for y in range(H):
        for x in range(W):
            if M[y][x] == ".":
                ans = max(ans, search(y, x))
    print(ans)
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
import copy
from collections import deque
 
n, m = map(int, input().split())
 
# マス目と距離保存のための箱を作成
d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)
 
 
def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する．最後Nan判定
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = max(list([max(local_d[0]), max(local_d[n - 1])]))
    for i in range(n):
        d_max = max([local_d[i][0], local_d[i][m - 1], d_max])
    return d_max
 
 
dis = 0
for i in range(n):
    dis_i = tansaku(i, 0, d)
    if dis_i > dis:
        dis = copy.deepcopy(dis_i)
    dis_i = tansaku(i, m - 1, d)
    if dis_i > dis:
        dis = copy.deepcopy(dis_i)
 
 
for i in range(m):
    dis_i = tansaku(0, i, d)
    if dis_i > dis:
        dis = copy.deepcopy(dis_i)
 
    dis_i = tansaku(n - 1, i, d)
    if dis_i > dis:
        dis = copy.deepcopy(dis_i)
 
 
print(dis)

Submission status: Wrong Answer

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()

    M = [input() for i in range(H)]

    def search(y, x):
        q = []
        m = [[0]*W for i in range(H)]

        m[y][x] = 0
        q = deque([(y,x, 0)])
        ans = 0
        while q:
            y, x, k = q.popleft()
            ans = max(ans, k)
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                yy = y + i
                xx = x + j

                if 0 <= xx < W and 0 <= yy < H:
                    if M[yy][xx] != "#" and m[yy][xx] == 0:
                        m[yy][xx] = 1
                        q.append((yy, xx, k+1))

        return ans

    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, search(y, x))
    print(ans)
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import copy
import heapq
import math
import fractions

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


h,w = ips()
pre  = '#'*(w+2)
board = [pre]
road = h*w
for i in range(h):
    a = input()
    road-=a.count('#')
    a = ''.join(['#',a,'#'])
    board.append(a)
board.append(pre)
maxsteps = 0
bh = h+2
bw = w+2
notfar = set()
for by in range(1,h+1):
    for bx in range(1,w+1):
        que = []
        checked = []
        if board[by][bx] == '.' and bw*by+bx not in notfar:
            #print("start",by,bx,by*bw+bx)
            que = []
            checked = [bw*by+bx]
            steps = 0
            if board[by][bx - 1] == '.':que.append([by,bx-1])
            if board[by][bx + 1] == '.':que.append([by,bx+1])
            if board[by - 1][bx] == '.':que.append([by-1,bx])
            if board[by + 1][bx] == '.':que.append([by+1,bx])
            while len(que):
                next = len(que)
                oldque = copy.copy(que)
                que = copy.copy([])
                for i in range(len(oldque)):
                    y,x = oldque[i] #need to change here
                    checked.append(y*bw+x)
                    if board[y][x - 1] == '.' and bw*y+x-1 not in checked: que.append([y, x - 1])
                    if board[y][x + 1] == '.' and bw*y+x+1 not in checked: que.append([y, x + 1])
                    if board[y - 1][x] == '.' and bw*(y-1)+x not in checked: que.append([y - 1, x])
                    if board[y + 1][x] == '.' and bw*(y+1)+x not in checked: que.append([y + 1, x])
                steps+=1
                if len(que):
                    for i in range(len(oldque)):
                        y, x = oldque[i]
                        notfar.add(bw*y+x)
                #print("che",checked)
                #print("que",que)
            maxsteps = max(steps,maxsteps)
print(maxsteps)

Submission status: Wrong Answer

Solution code:
import collections
h, w = map(int, input().split())
s = [[""]*(w+2)]
starts = []
for i in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
    for j, __s in enumerate(_s):
        if __s == ".":
            starts.append([i+1, j])
s.append([""]*(w+2))

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

ans = 0
for _start in starts:
    dist = [[-1]*(w+2) for _ in range(h+2)]
    dist[_start[0]][_start[1]] = 0
    q = collections.deque([_start])

    # BFS
    while 0 < len(q):
        c = q.pop()
        for _dx, _dy in zip(dx, dy):
            x = c[0] + _dx
            y = c[1] + _dy
            if s[x][y] == "." and dist[x][y] == -1:
                dist[x][y] = dist[c[0]][c[1]] + 1
                q.appendleft([x, y])

    ans = max(ans, max(max(dist)))

print(ans)