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
import queue

H, W = map(int, input().split())

maze = np.zeros((H, W))


for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '.':
            maze[i, j] = 1

max_run = 0


tan = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def max_route(h, w):
    g = (21, 21)
    q = queue.Queue()
    checker = maze.copy()
    q.put((h, w))
    q.put(g)

    run = 0

    while not q.empty():
        target = q.get()
        if target == g:
            if not q.empty():
                run += 1
                q.put(g)
        else:
            for t in tan:
                check = [target[0]+t[0], target[1]+t[1]]
                if 0 <= check[0] < H and 0 <= check[1] < W:
                    if checker[check[0], check[1]] == 1:
                        q.put((check[0], check[1]))
                        checker[check[0], check[1]] = 2

    return run


for h in range(H):
    for w in range(W):
        if maze[h, w] == 0:
            continue
        cur = max_route(h, w)
        if cur > max_run:
            max_run = cur

print(max_run)

Submission status: Wrong Answer

Solution code:
# ABC151 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx,gy,gx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        if [y,x]==[gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
h,w=nm()
path=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                if path[i][j]=='#' or path[k][l]=='#':
                    continue
                sy,sx=i,j
                gy,gx=k,l
                visited = [[-1]*w for i in range(h)]
                bfs(sy,sx,gx,gy)
                ans=max(visited[gy][gx],ans)
print(ans)



# for i in range(h):
#     for j in range(w):
#         for k in range(h):
#             for l in range(w):
#                 if i

Submission status: Wrong Answer

Solution code:
import sys
import collections
input=sys.stdin.readline


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


def f(sx, sy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(W)] for h in range(H)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    ma = 0
    for d in dist:
        for i in d:
            if i != float("inf"):
                ma = max(ma, i)
    return ma


def main():
    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, (f(y, x)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    BLACK = '#'
    WHITE = '.'
    H, W = MI()
    graph = [[0 for i in range(W)] for i in range(H)]
    ans = 0
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    for i in range(H):
        S = input()

        for j in range(W):
            graph[i][j] = S[j]

    # H = 2
    # W = 2
    # graph = [['.' for i in range(W)] for i in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            if graph[h][w] == BLACK:
                continue

            visited = [[False for i in range(W)] for i in range(H)]
            q = deque()
            q.append(((h, w), 0))
            arr = []
            while len(q) != 0:
                p, c = q.popleft()
                # print(ans, n)

                for d in options:
                    i = p[0] + d[0]
                    j = p[1] + d[1]

                    if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] == WHITE:
                        visited[i][j] = True
                        q.append(((i, j), c+1))
                        # print((i, j), c+1)
                    else:
                        arr.append(c)
            # print(h, w, arr, max(arr))
            ans = max(ans, max(arr))

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

H, W = map(int, input().split())
S = [input() for a in range(H)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

answer = 0

for s_y in range(H):
  for s_x in range(W):
    d = [[ 0 for b in range(W)] for a in range(H)]
    q = deque([[s_y, s_x]])
    d[s_y][s_x] = 0
    while len(q) > 0:
      y, x = q.popleft()
      for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and S[ny][nx] == '.' and d[ny][nx] == 0:
          q.append([ny, nx])
          d[ny][nx] = d[y][x]+1
    for i in range(H):
      answer = max(answer, max(d[i]))
print(answer)

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque
h,w=map(int,input().split())
p=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
b=copy.deepcopy(p)
ans=0
#print(p)
aa=[]
bb=[]
for i in range(1,h+1):
    for j in range(1,w+1):
        if p[i][j]=='.':
            aa.append(i)
            bb.append(j)
            aa.append(h-i+1)
            bb.append(w-j+1)
aa=list(set(aa))
bb=list(set(bb))
L=[min(aa),h-min(aa)+1]
R=[min(bb),w-min(bb)+1]
#print(L,R)
#s0,s1=map(lambda x:int(x)-1,input().split())
#g0,g1=map(lambda x:int(x)-1,input().split())
for i in L:
    for j in R:
        for k in range(1,h+1):
            for z in range(1,w+1):
                p=copy.deepcopy(b)
                if p[i][j]=='.' and p[k][z]=='.':
                    s0,s1=i,j
                    g0,g1=k,z
                    p[s0][s1]=0
                    d=[(1,0),(-1,0),(0,1),(0,-1)]
                    q=deque([[s0,s1]])
                    while q:
                        x,y=q.popleft()
                        for dx,dy in d:
                            if p[x+dx][y+dy]==".":
                                p[x+dx][y+dy]=p[x][y]+1
                                q.append([x+dx,y+dy])
                    if ans<=p[g0][g1]:
                        ans=p[g0][g1]
print(ans)

Submission status: Wrong Answer

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] == ".":
      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: Wrong Answer

Solution code:
import heapq
import itertools


def astar(init_pos, goal):
    passed_list = [init_pos]
    init_score = distance(passed_list) + heuristic(init_pos)
    checked = {init_pos: init_score}
    searching_heap = []
    heapq.heappush(searching_heap, (init_score, passed_list))
    while len(searching_heap) > 0:
        score, passed_list = heapq.heappop(searching_heap)
        last_passed_pos = passed_list[-1]
        if last_passed_pos == goal:
            return passed_list
        for pos in nexts(last_passed_pos):
            new_passed_list = passed_list + [pos]
            pos_score = distance(new_passed_list) + heuristic(pos)
            if pos in checked and checked[pos] <= pos_score:
                continue
            checked[pos] = pos_score
            heapq.heappush(searching_heap, (pos_score, new_passed_list))

    return []

if __name__ == "__main__":
    h, w = map(int, input().split())
    maze = [input() for j in range(h)]

    init = (0,0)
    goal = (h-1,w-1)

    def nexts(pos):
        ''' 探索中の座標から八方の座標を計算するジェネレーター'''
        wall = "#"

        # for a, b in itertools.product([' + 1', ' - 1', ''], repeat=2):
        for a, b in [["+1",""], ["-1", ""], ["", "+1"], ["", "-1"]]:
            if a or b:
                if 0 <= eval('pos[0]' + a) < h and 0 <= eval('pos[1]' + b) < w and maze[eval('pos[0]' + a)][eval('pos[1]' + b)] != wall:
                    yield (eval('pos[0]' + a), eval('pos[1]' + b))

    def heuristic(pos):
        ''' 探索中の座標からゴールまでの最短距離のスコア '''
        return ((pos[0] - goal[0]) ** 2 + (pos[1] - goal[1]) ** 2) ** 0.5

    def distance(path):
        ''' スタートから探索中の座標までの距離のスコア '''
        return len(path)

    def render_path(path):
        ''' 結果の出力 '''
        buf = [[ch for ch in l] for l in maze]

        for pos in path[1:-1]:
            buf[pos[0]][pos[1]] = "*"

        buf[path[0][0]][path[0][1]] = "s"
        buf[path[-1][0]][path[-1][1]] = "g"
        return ["".join(l) for l in buf]

    ma = 0
    for a in range(0,w):
        path = astar((0,a),(h-1,w-a-1))
        if len(path) > ma:
            ma = len(path)
        # if len(path) != 0:
        #     print("\n".join(render_path(path)))
        #     print()

    for a in range(0,h):
        path = astar((a,0), (h-a-1, w-1))
        if len(path) > ma:
            ma = len(path)
        # if len(path) != 0:
        #     print("\n".join(render_path(path)))
        #     print()

    print(ma-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
ddx = [0, 0, -1, 1]
ddy = [-1, 1, 0, 0]

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

res = 0
inf = 9999999
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        dist = [[inf]*w for _ in range(h)]
        dist[i][j] = 0
        que = deque([[i, j]])
        while len(que):
            y, x = que.popleft()
            for dx, dy in zip(ddx, ddy):
                if x+dx < 0 or x+dx >= w or y+dy < 0 or y+dy >= h or s[y+dy][x+dx] == '#' or dist[y+dy][x+dx] < inf:
                    continue
                que.append([y+dy, x+dx])
                dist[y+dy][x+dx] = dist[y][x] + 1
        ma = 0
        for i in range(h):
            for j in range(w):
                if dist[i][j] < inf:
                    ma = max(ma, dist[i][j])
        res = max(ma, res)
print(res)

Submission status: Wrong Answer

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

from collections import deque
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
d=0
for i in range(h):
    if d:
        break
    for j in range(w):
        if s[i][j]==".":
            p=[i,j]
            d=1
            break
q=[p]
t=[[1]*w for j in range(h)]
t[p[0]][p[1]]=1
while q:
    c=[]
    for i,j in q:
        a=[1,-1,0,0]
        b=[0,0,1,-1]
        for d in range(4):
            if 0<=i+a[d]<h and 0<=j+b[d]<w:
                if s[i+a[d]][j+b[d]]==".":
                    if t[i+a[d]][j+b[d]]:
                        t[i+a[d]][j+b[d]]=0
                        c.append([i+a[d],j+b[d]])
    if len(c)==0:
        break
    else:
        q=c[::]
e=0
for p in q:
    q=[p]
    t=[[1]*w for j in range(h)]
    t[p[0]][p[1]]=0
    g=0
    while q:
        c=[]
        for i,j in q:
            a=[1,-1,0,0]
            b=[0,0,1,-1]
            for d in range(4):
                if 0<=i+a[d]<h and 0<=j+b[d]<w:
                    if s[i+a[d]][j+b[d]]==".":
                        if t[i+a[d]][j+b[d]]:
                            t[i+a[d]][j+b[d]]=0
                            c.append([i+a[d],j+b[d]])
        if len(c)==0:
            break
        else:
            g+=1
            q=c[::]
    e=max(e,g)
print(g)

Submission status: Wrong Answer

Solution code:
import sys
import copy
input = sys.stdin.readline
from collections import deque
H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    S.append(list(input().rstrip()))
can = []
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            can.append([i, j])
ans = []
for u in can:
    S_ = copy.deepcopy(S)
    D = {}
    queue = deque([u])
    def bfs(u, S):
        S_2 = S[:]
        D[tuple(u)] = 0
        while queue:
            v = queue.popleft()
            x, y = v
            next_ = [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]
            for r in next_:
                if 0 <= r[0] < H and 0 <= r[1] < W:
                    if S_2[r[0]][r[1]] == ".":
                        S_2[r[0]][r[1]] = "#"
                        D[tuple(r)] = D[tuple(v)] + 1
                        queue.append(r)
        return max(D.values())
    ans.append(bfs(u, S_))
print(max(ans))

Submission status: Wrong Answer

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


def clear_maze(sx, sy, maze):

    # debug_print(maze)

    INF = -100

    field_x_length = len(maze[0])
    field_y_length = len(maze)
    distance = [[INF for i in range(field_x_length)]
                for j in range(field_y_length)]
    #    distance = [[None]*field_x_length]*field_y_length
    for i in range(field_y_length):
        for j in range(field_x_length):
            if maze[i][j] == '#':
                distance[i][j] = -100

    def bfs():
        queue = []

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

        distance[sy][sx] = 0

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

            # flag = False
            # for i in range(field_y_length):
            #     if INF in distance[i]:
            #         flag  = True
            #         break
            #     else:
            #         continue
            # if flag is False:
            #     break
                
    

            # if x == gx and y == gy:
            #     break

            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, (nx, ny))
                    distance[ny][nx] = distance[y][x] + 1
        
        return distance

    return bfs()


S = [list(input()) for _ in range(h)]
# print(S)

ans = 0


# def pick_max(maze):
#     field_x_length = len(maze[0])
#     field_y_length = len(maze)
#     ans = 0
#     for i in ra

for i in range(h):
    for j in range(w):
        start = S[i][j]
        if start == '#':
            continue

        # for k in range(h):
        #     for l in range(w):
            
        num = clear_maze(j, i, S)
        for i in range(h):
            ans = max(ans, max(num[i]))
        # print(an)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
import sys
sys.setrecursionlimit(410000)

INF = 10**6

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

def solve(sy,sx):
  d = [[INF]*w for _ in range(h)]
  que = deque()
  que.append([sx,sy])
  d[sy][sx]=0

  while len(que)>0:
    px,py = que.popleft()

    for dx,dy in ((-1,0),(0,1),(1,0),(0,-1)):
      nx = px + dx
      ny = py + dy

      if (0 <= nx and nx < w and 0<=ny and ny < h) \
          and maze[ny][nx] != '#' \
          and (d[ny][nx] == INF or d[ny][nx] > d[py][px] +1):              
        que.append((nx,ny))
        d[ny][nx] = d[py][px] +1

  return d


maze = copy.deepcopy(org_maze)
f = solve(0,0)

d79 = f[0][w-1]
d71 = f[h-1][0]
d73 = f[h-1][w-1]

maze = copy.deepcopy(org_maze)
f = solve(0,w-1)
d91 = f[h-1][0]
d93 = f[h-1][w-1]

maze = copy.deepcopy(org_maze)
f = solve(h-1,0)
d13 = f[h-1][w-1]

print(max(d79,d71,d73,d91,d93,d13))

Submission status: Wrong Answer

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

field = [[c for c in input().strip()] for _ in range(h)]

dir_x = [0, 1, 0, -1]
dir_y = [-1, 0, 1, 0]
ans = 0
# 全部のマスをスタートにしてチェックする
for i in range(h):
    for j in range(w):
        if field[i][j] == '#':
            continue

        field_flag = [[0 for _ in range(w)] for _ in range(h)]
        field_step = [[0 for _ in range(w)] for _ in range(h)]
        # スタート地点を入れる
        d = deque()
        d.append([i, j])
        while (d):
            y, x = d.popleft()
            for xx, yy in zip(dir_x, dir_y):
                if xx+x in range(w) and yy+y in range(h):
                    if field[yy+y][xx+x] == '.' and field_flag[yy+y][xx+x] == 0:
                        field_flag[yy+y][xx+x] = 1  # チェック済
                        # そこへたどり着く最小歩数
                        field_step[yy + y][xx + x] = field_step[y][x] + 1
                        ans = max(ans, field_step[yy + y][xx + x])  # 答えの更新
                        d.append([yy+y, xx+x])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = [int(x) for x in input().split()]
S = [input() for _ in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#': continue 
        maze = [[-1 for _ in range(W)] for _ in range(H)]
        maze[y][x] = 0
        d = deque([(x, y)])
        while len(d):
            x, y = d.pop()
            now = maze[y][x]
            for i in range(4):
                nx, ny = [x + dx[i], y + dy[i]]
                if nx < 0 or nx > W-1 or ny < 0 or ny > H-1: continue
                if S[ny][nx] == '#': continue
                if maze[ny][nx] == -1 or maze[ny][nx] > now+1:
                    maze[ny][nx] = now+1
                    d.append((nx, ny))
        for m in maze:
            ans = max(ans, max(m))
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
grid=[None]*H
# 仮のスタート
sx,sy=-1,-1
found=False
for i in range(H):
  grid[i]=input()
  if not found:
    for j in range(len(grid[i])):
      if grid[i][j]==".":
        sy=i
        sx=j
        found=True
        
from collections import deque
stack=deque()
# y,x,そこまでの距離
stack.append([sy,sx,0])
INF=10**9
seen=[[INF for j in range(W)] for i in range(H)]

longest=0
longestY=-1
longestX=-1
while stack:
  node=stack.popleft()
  y=node[0]
  x=node[1]
  dist=node[2]
  if grid[y][x]=="#":
    continue
  if seen[y][x]<=dist:
    continue
  if dist>longest:
    longest=dist
    longestY=y
    longestX=x
  seen[y][x]=dist
  if y-1>=0:
    stack.append([y-1,x,dist+1])
  if y+1<H:
    stack.append([y+1,x,dist+1])
  if x-1>=0:
    stack.append([y,x-1,dist+1])
  if x+1<W:
    stack.append([y,x+1,dist+1])
    
# ここから後半
q=deque()
q.append([longestY,longestX,0])
visited=[[INF for j in range(W)] for i in range(H)]
ans=0
while q:
  node=q.popleft()
  y=node[0]
  x=node[1]
  dist=node[2]
  if grid[y][x]=="#":
    continue
  if visited[y][x]<=dist:
    continue
  if dist>ans:
    ans=dist
  visited[y][x]=dist
  if y-1>=0:
    q.append([y-1,x,dist+1])
  if y+1<H:
    q.append([y+1,x,dist+1])
  if x-1>=0:
    q.append([y,x-1,dist+1])
  if x+1<W:
    q.append([y,x+1,dist+1])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]

dist = [[float('inf') for i in range(W)] for j in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == float('inf'):
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]


ans = []
for i in range(H):
    for j in range(W):
        sx, sy = i, j
        for k in range(H):
            for l in range(W):
                gx, gy = k, l
                ans.append(bfs())

# print(ans)
ans = [i for i in ans if i != float('inf')]
print(max(ans))

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque
h,w=map(int,input().split())
p=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
b=copy.deepcopy(p)
ans=0
#print(p)
aa=[]
bb=[]
for i in range(1,h+1):
    for j in range(1,w+1):
        if p[i][j]=='.':
            aa.append(i)
            bb.append(j)
            aa.append(h-i+1)
            bb.append(w-j+1)
aa=list(set(aa))
bb=list(set(bb))
L=[min(aa),h-min(aa)+1]
R=[min(bb),w-min(bb)+1]
#print(L,R)
#s0,s1=map(lambda x:int(x)-1,input().split())
#g0,g1=map(lambda x:int(x)-1,input().split())
for i in L:
    for j in R:
        for k in L:
            for z in R:
                p=copy.deepcopy(b)
                if p[i][j]=='.' and p[k][z]=='.':
                    s0,s1=i,j
                    g0,g1=k,z
                    p[s0][s1]=0
                    d=[(1,0),(-1,0),(0,1),(0,-1)]
                    q=deque([[s0,s1]])
                    while q:
                        x,y=q.popleft()
                        for dx,dy in d:
                            if p[x+dx][y+dy]==".":
                                p[x+dx][y+dy]=p[x][y]+1
                                q.append([x+dx,y+dy])
                    if ans<=p[g0][g1]:
                        ans=p[g0][g1]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(si, sj):
    q = deque()
    q.append([si, sj, 0])
    used = set([si,sj])
    ans = MAX_VALUE
    while len(q) > 0:
        prvi, prvj, d = q.popleft()
        for i, j in [[prvi-1, prvj], [prvi+1, prvj], [prvi, prvj-1], [prvi, prvj+1]]:
            if (i,j) in used:
                continue
            if grid[j][i] == '#':
                ans = min(ans, d)
                continue
            else:
                q.append([i,j,d+1])
                used.add((i,j))
    return d

H, W = map(int, input().split())
MAX_VALUE = (H+2) * (W+2) + 1
grid = ['#'*(W+2)] + [ '#' + input() + '#' for _ in range(H)] + ['#'*(W+2)]

ans = 1
for j in range(1, H + 1):
    for i in range(1, W + 1):
        if grid[j][i] == '#':
            continue
        res = bfs(i, j)
        if res != MAX_VALUE:
            ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S    = [None] * H # S[h][w]
for h in range(H):
    S[h] = list(input())

# find temporary start
is_break = False
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            is_break = True
            break
    if is_break:
        break

h_init, w_init = h, w

# find goal
STEPs                 = [[-1 for w in range(W)] for h in range(H)] # STEPs[x][y]
STEPs[h_init][w_init] = 0
max_STEP              = 0

Q = [(h_init, w_init)]

while len(Q) > 0:
    Q_new = []
    for q in Q:
        step     = STEPs[q[0]][q[1]]
        max_STEP = max(max_STEP, step)
        for h, w in [(q[0]-1, q[1]), (q[0], q[1]-1), (q[0], q[1]+1), (q[0]+1, q[1])]:
            if (h < 0 or w < 0) or (h >= H or w >= W) or (STEPs[h][w] != -1) or S[h][w] != '.':
                continue
            else:
                STEPs[h][w] = step+1
                Q_new.append((h, w))
    Q = Q_new

is_break = False
for h in range(H):
    for w in range(W):
        if STEPs[h][w] == max_STEP:
            is_break = True
            break
    if is_break:
        break

h_goal, w_goal = h, w

# print(STEPs)
# print(max_STEP, h_goal, w_goal)

# find start
STEPs                 = [[-1 for w in range(W)] for h in range(H)] # STEPs[x][y]
STEPs[h_goal][w_goal] = 0
max_STEP              = 0

Q = [(h_goal, w_goal)]

while len(Q) > 0:
    Q_new = []
    for q in Q:
        step     = STEPs[q[0]][q[1]]
        max_STEP = max(max_STEP, step)
        for h, w in [(q[0]-1, q[1]), (q[0], q[1]-1), (q[0], q[1]+1), (q[0]+1, q[1])]:
            if (h < 0 or w < 0) or (h >= H or w >= W) or (STEPs[h][w] != -1) or S[h][w] != '.':
                continue
            else:
                STEPs[h][w] = step+1
                Q_new.append((h, w))
    Q = Q_new

print(max_STEP)

# is_break = False
# for h in range(H):
#     for w in range(W):
#         if STEPs[h][w] == max_STEP:
#             is_break = True
#             break
#     if is_break:
#         break

# print(STEPs)
# print(max_STEP, h, w)

Submission status: Wrong Answer

Solution code:
import math
import sys
sys.setrecursionlimit(10**9)
H,W = map(int,input().split())

S = []
for h in range(H):
    s = input()
    t = []
    for ss in s:
        if ss==".":
            t.append(True)
        else:
            t.append(False)
    S.append(t)

# print(S)

V = H*W

d = [[float("inf") for i in range(V)] for j in range(V)]

for h in range(H):
    for w in range(W):
        i = h*W+w
        if S[h][w]:
            if 0<=h<=H-2 and S[h+1][w]:
                j = (h+1)*W+w
                d[i][j], d[j][i] = 1,1
            if 1<=h<=H-1 and S[h-1][w]:
                j = (h-1)*W+w
                d[i][j], d[j][i] = 1,1
            if 0<=w<=W-2 and S[h][w+1]:
                j = h*W+(w+1)
                d[i][j], d[j][i] = 1,1
            if 1<=w<=W-1 and S[h][w-1]:
                j = h*W+(w-1)
                d[i][j], d[j][i] = 1,1

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

    return d #d[i][j]に頂点i, j間の最短距離を格納

# 例一個作ってみる．
dd = warshall_floyd(d, V)

# print(dd)
mx = 0
for ddd in dd:
    for n in ddd:
        if math.isfinite(n):
            mx = max(mx, n)

print(mx)

# 6 4
# #...
# #.#.
# #...
# #.#.
# #.#.
# #.#.

Submission status: Wrong Answer

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

#四方向の移動用
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


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

    while que:
        p = que.popleft()

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

            if (0 <= nx < w) and (0 <= ny < h) and (l[ny][nx] != "#") and (d[ny][nx] == -1):
                que.append((nx, ny))
                d[ny][nx] = d[p[1]][p[0]] + 1

    return max(sum(d, []))


ans = 0
for sy in range(h):
    for sx in range(w):
        temp = bfs(sx, sy)
        if ans < temp:
            ans = temp
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())

S = [list(input()) for _ in range(H)]

check = [[False]*W for _ in range(H)]

res = 0


for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        if check[i][j]:
            continue

        mc = [[-1]*W for _ in range(H)]
        mc[i][j] = 0

        q = [(i, j)]
        while q:
            y, x = q.pop(0)
            for a, b in [(-1,0), (0,-1), (0,1), (1,0)]:
                if y+a < 0 or y+a >= H or x+b < 0 or x+b >= W:
                    continue

                if S[y+a][x+b] == "#":
                    continue


                if mc[y+a][x+b] == -1 or mc[y+a][x+b] > mc[y][x]+1:
                    mc[y+a][x+b] = mc[y][x]+1

                    res = max(res, mc[y+a][x+b])
                    q.append([y+a, x+b])

                    check[y][x] = True



print(res)