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

h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = -1

def bfs(sx, sy):
    que = deque([[sy, sx]])
    d = [[0] * w for _ in range(h)]
    count = 0
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            nx, ny = x+i, y+j
            if 0 <= nx and nx < w and 0 <= ny and ny < h and d[ny][nx] == 0 and c[ny][nx] != "#":
                nx_, ny_ = nx-i, ny-j
                d[ny][nx] = d[ny_][nx_] + 1
                que.append([ny, nx])
    return max(max(d))

for i_ in range(h):
    for j_ in range(w):
        if c[i_][j_] == "#":
            continue
        ans = max(ans, bfs( j_, i_))

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


HEIGHT, WIDTH = map(int, input().split())
S = [input() for _ in range(HEIGHT)]
M = np.array([[0 if char == "." else -1 for char in row] for row in S], dtype=np.int64)


def bfs(i, j):
    for v in np.array([[1, 0], [0, 1]]):
        for flag in [1, -1]:
            di, dj = v * flag
            new_i, new_j = i + di, j + dj
            if (
                0 <= new_i < HEIGHT
                and 0 <= new_j < WIDTH
                and (new_i, new_j) != START
                and MM[new_i, new_j] == 0
            ):
                MM[new_i, new_j] = MM[i, j] + 1
                STACK.append((new_i, new_j))


ANS = 0
for i in range(HEIGHT):
    for j in range(WIDTH):
        if M[i, j] == 0:
            MM = M.ravel().copy().reshape(HEIGHT, WIDTH)
            START = (i, j)
            STACK = [START]
            while STACK:
                i, j = STACK.pop(0)
                bfs(i, j)
            ANS = max(ANS, MM.max())
            print(MM)
            print()
print(ANS)

Submission status: Wrong Answer

Solution code:

def get_neighbors(S, i):
    n = []
    if S[i]:
        if i >= W: #First row
            if S[i-W]:
                n += [i-W]
        if i < (H-1)*W:
            if S[i+W]:
                n += [i+W]
        if i % W > 0:
            if S[i-1]:
                n += [i-1]
        if i % W < W-1:
            if S[i+1]:
                n += [i+1]
    return n

import numpy as np
H, W = map(int, raw_input().split())
S = np.empty(H*W, bool)

for i in xrange(H):
    S[i*W:(i+1)*W] = map(lambda x: x==".", raw_input())
    
NR = sum(S) # Number of road cube
NE = [] # The neighbors
for i in xrange(H*W):
    NE += [get_neighbors(S, i)]

M = np.zeros([H*W, H*W], int)
# init
for i,n in enumerate(NE):
    for j in n:
        M[i,j] = 1
        
# find road
I = np.sum(M != 0)
Count = 2

while I < NR *NR:
    a = []
    for i,n in enumerate(NE):
        for j in n:
            a = np.logical_and(M[i] == 0, M[j] == Count-1)
            M[i][a] = Count
    I = np.sum(M != 0)
    Count += 1

print(Count - 1)

Submission status: Wrong Answer

Solution code:
import sys
import socket
import numpy
from itertools import product

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    h, w = read_int_list()
    a = [read_str() for _ in range(h)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    inf = 10 ** 3
    d = numpy.full(shape=(h, w, h, w), fill_value=inf)
    for i, j in product(range(h), range(w)):
        d[i][j][i][j] = 0

    for i, j in product(range(h), range(w)):
        if a[i][j] == '#':
            continue
        for di, dj in zip(dx, dy):
            k = i + di
            l = j + dj
            if not (0 <= k < h and 0 <= l < w):
                continue
            if a[k][l] == '#':
                continue
            d[i][j][k][l] = 1

    for k, kk in product(range(h), range(w)):
        for i, ii in product(range(h), range(w)):
            for j, jj in product(range(h), range(w)):
                if d[i][ii][j][jj] > d[i][ii][k][kk] + d[k][kk][j][jj]:
                    d[i][ii][j][jj] = d[i][ii][k][kk] + d[k][kk][j][jj]


    res = 0
    for i, ii in product(range(h), range(w)):
        for j, jj in product(range(h), range(w)):
            if d[i][ii][j][jj] == inf:
                continue
            if res < d[i][ii][j][jj]:
                res = d[i][ii][j][jj]
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import socket
import numpy
from itertools import product

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    h, w = read_int_list()
    a = [read_str() for _ in range(h)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    inf = 10 ** 3
    d = numpy.full(shape=(h, w, h, w), fill_value=inf)
    for i, j in product(range(h), range(w)):
        d[i][j][i][j] = 0

    for i, j in product(range(h), range(w)):
        if a[i][j] == '#':
            continue
        for di, dj in zip(dx, dy):
            k = i + di
            l = j + dj
            if not (0 <= k < h and 0 <= l < w):
                continue
            if a[k][l] == '#':
                continue
            d[i][j][k][l] = 1

    for i, ii in product(range(h), range(w)):
        for j, jj in product(range(h), range(w)):
            for k, kk in product(range(h), range(w)):
                if d[i][ii][j][jj] > d[i][ii][k][kk] + d[k][kk][j][jj]:
                    d[i][ii][j][jj] = d[i][ii][k][kk] + d[k][kk][j][jj]


    res = 0
    for i, ii in product(range(h), range(w)):
        for j, jj in product(range(h), range(w)):
            if d[i][ii][j][jj] == inf:
                continue
            if res < d[i][ii][j][jj]:
                res = d[i][ii][j][jj]
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = 998244353
INF = int(1e15)


def bfs(S, H, W, s):
    q = []
    q.append(s)
    M = [[-1 for _ in range(W)]for _ in range(H)]
    M[s[1]][s[0]] = 0
    while q != []:
        p = q.pop(0)
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for i in range(4):
            n = (p[0] + DIR[i][0], p[1] + DIR[i][1])
            if not (0 <= n[0] < W and 0 <= n[1] < H):
                continue
            if S[n[1]][n[0]] == "#":
                continue
            if M[n[1]][n[0]] != -1:
                continue
            M[n[1]][n[0]] = M[p[1]][p[0]] + 1
            q.append(n)
    res = 0
    for h in range(H):
        res = max(res, max(M[h]))
    return res


def main():
    # sys.stdin = open("sample.txt")
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, bfs(S, H, W, (w, h)))
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = 998244353
INF = int(1e15)


def bfs(S, H, W, s):
    q = []
    q.append(s)
    M = [[0 for _ in range(W)]for _ in range(H)]
    while q != []:
        p = q.pop(0)
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for i in range(4):
            n = (p[0] + DIR[i][0], p[1] + DIR[i][1])
            if not (0 <= n[0] < W and 0 <= n[1] < H):
                continue
            if S[n[1]][n[0]] == "#" or n == s:
                continue
            if M[n[1]][n[0]] != 0:
                continue
            M[n[1]][n[0]] = M[p[1]][p[0]] + 1
            q.append(n)
    res = 0
    for h in range(H):
        res = max(res, max(M[h]))
    return res


def main():
    # sys.stdin = open("sample.txt")
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, bfs(S, H, W, (w, h)))
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy

def dd(P,l,M):
    def nexts(y,x,M):
        n = []
        if y > 0 and M[y-1][x] == ".":
            n += [(y-1,x)] # up
        if y < H - 1 and M[y+1][x] == ".":
            n += [(y+1,x)] # down
        if x > 0 and M[y][x-1] == ".":
            n += [(y,x-1)] # left
        if x < W - 1 and M[y][x+1] == ".":
            n += [(y,x+1)]  # right
        return n

    n = []
    for y,x in P:
        #print("dd",l,y,x)
        n += nexts(y,x,M)
    n = list(set(n))

    for y,x in n:
        M[y][x] = "#"

    if n == []:
        return [(l,P[0])]
    else:
        return dd(n,l+1,M)

H,W = [int(i) for i in input().rstrip().split(' ')]
S = [list(input()) for _ in range(H)]
S1 = copy.deepcopy(S)
mr = 0
for y in range(H):
    b = False
    for x in range(W):
        if S[y][x] == ".":
            S1 = copy.deepcopy(S)
            far = sorted(dd([(y,x)], 0, S1), reverse=True)[0]
            #print(y,x,far)
            if mr < far[0]:
                mr = far[0]
print(mr)

Submission status: Wrong Answer

Solution code:
import copy

H,W = [int(i) for i in input().rstrip().split(' ')]
S = [list(input()) for _ in range(H)]
S1 = copy.deepcopy(S)
start = []
for y in range(H):
    b = False
    for x in range(W):
        if S[y][x] == ".":
            start = (y,x)
            #print(start)
            b = True
            break
    if b:
        break

def dd(P,l,M):
    def nexts(y,x,M):
        n = []
        if y > 0 and M[y-1][x] == ".":
            n += [(y-1,x)] # up
        if y < H - 1 and M[y+1][x] == ".":
            n += [(y+1,x)] # down
        if x > 0 and M[y][x-1] == ".":
            n += [(y,x-1)] # left
        if x < W - 1 and M[y][x+1] == ".":
            n += [(y,x+1)]  # right
        return n

    n = []
    for y,x in P:
        #print("dd",l,y,x)
        n += nexts(y,x,M)
    n = list(set(n))

    for y,x in n:
        M[y][x] = "#"

    if n == []:
        return [(l,P[0])]
    else:
        return dd(n,l+1,M)

far = sorted(dd([start], 0, S1),reverse=True)[0]
far2 = sorted(dd([far[1]], 0, S),reverse=True)[0]
print(far2[0])

Submission status: Wrong Answer

Solution code:
import queue

h, w = list(map(int, input().split()))
s = [input() for _ in range(h)]
le = []
for i in range(h*w):
    q = queue.Queue()
    q.put(i)
    kyori = [0] * (h*w)
    kyori[i] = 1
    while not q.empty():
        p = q.get()
        kyo = kyori[p]
        x = p%w
        y = p//w
        if x >= 1 and s[y][x-1] == '.' and kyori[p-1] == 0:
            q.put(p-1)
            kyori[p-1] = kyo+1
        if x < w-1 and s[y][x+1] == '.' and kyori[p+1] == 0:
            q.put(p+1)
            kyori[p+1] = kyo+1
        if y >= 1 and s[y-1][x] == '.' and kyori[p-w] == 0:
            q.put(p-w)
            kyori[p-w] = kyo+1
        if y < h-1 and s[y+1][x] == '.' and kyori[p+w] == 0:
            q.put(p+w)
            kyori[p+w] = kyo+1
    le.append(max(kyori))
print(max(le)-1)

Submission status: Wrong Answer

Solution code:
import queue

h, w = list(map(int, input().split()))
s = [input() for _ in range(h)]
q = queue.Queue()
q.put(0)
kyori = [0] * (h*w)
kyori[0] = 1
for i in range(2):
    while not q.empty():
        p = q.get()
        kyo = kyori[p]
        x = p%w
        y = p//w
        if x >= 1 and s[y][x-1] == '.' and kyori[p-1] == 0:
            q.put(p-1)
            kyori[p-1] = kyo+1
        if x < w-1 and s[y][x+1] == '.' and kyori[p+1] == 0:
            q.put(p+1)
            kyori[p+1] = kyo+1
        if y >= 1 and s[y-1][x] == '.' and kyori[p-w] == 0:
            q.put(p-w)
            kyori[p-w] = kyo+1
        if y < h-1 and s[y+1][x] == '.' and kyori[p+w] == 0:
            q.put(p+w)
            kyori[p+w] = kyo+1
    if i == 0:
        start = kyori.index(max(kyori))
        q = queue.Queue()
        q.put(start)
        kyori = [0] * (h*w)
        kyori[start] = 1
print(max(kyori)-1)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

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

for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            x, y = i, j


from heapq import heappop, heappush

def dfs(sx, sy):
    dist = [[float("inf")]*w for i in range(h)]
    heap = [(0, sx, sy)]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == "." and dist[nx][ny] > c+1:
                heappush(heap, (c+1, nx, ny))
    
    tmp = 0
    rx, ry = 0, 0
    for i in range(h):
        for j in range(w):
            if dist[i][j] != float("Inf") and tmp < dist[i][j]:
                tmp = dist[i][j]
                rx,ry = i,j
    return tmp, rx, ry

ans = 0


for i in range(10):
    r, x,y = dfs(x, y)
print(r)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

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

for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            sx, sy = i, j


from heapq import heappop, heappush

def dfs(sx, sy):
    dist = [[float("inf")]*w for i in range(h)]
    heap = [(0, sx, sy)]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == "." and dist[nx][ny] > c+1:
                heappush(heap, (c+1, nx, ny))
    
    tmp = 0
    rx, ry = 0, 0
    for i in range(h):
        for j in range(w):
            if dist[i][j] != float("Inf") and tmp < dist[i][j]:
                tmp = dist[i][j]
                rx,ry = i,j
    return tmp, rx, ry

ans = 0

r1, x,y = dfs(sx, sy)
r2, x,y = dfs(x, y)
print(r2)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

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

road = []

for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            cnt = 0
            for dx,dy in dxdy:
                nx = i + dx
                ny = j + dy
                if 0<=nx<h and 0<=ny<w and board[i][j] == ".":
                    cnt += 1
            if cnt == 1:
                road.append([i,j])


from heapq import heappop, heappush

def dfs(start, end):
    dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
    dist = [[float("inf")]*w for i in range(h)]
    #heap = [(0, *start)]
    heap = [(0, start[0], start[1])]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == "." and dist[nx][ny] > c+1:
                heappush(heap, (c+1, nx, ny))
    return dist[end[0]][end[1]]


from itertools import combinations

ans = 0
for start, end in combinations(road, 2):
    #print(start, end)
    tmp = dfs(start, end)
    if tmp != float("inf"):
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	H,W = MI()
	maze = [[0 for _ in range(W)] for _ in range(H)]
	for i in range(H):
		S = IS()
		for j,s in enumerate(S):
			if s == '#':
				maze[i][j] = -1
	
	def bfs(sx,sy):
		from collections import deque
		que = deque()
		dist_map = copy.deepcopy(maze)
		que.append((sx,sy, dist_map[sy][sx]))
		while len(que) > 0:
			x,y,d=que.popleft()
			dist_map[y][x] = d
			for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
				nx = x+dx
				ny = y+dy
				if(0<=nx<W and 0<=ny<H):
					if(dist_map[ny][nx]==0):
						que.append((nx,ny,d+1))
		return d

	ans = -1
	for i in range(H):
		for j in range(W):
			if(maze[i][j]==0):
				dist = bfs(j,i)
				if(dist > ans):
					ans = dist
	print(ans)

main()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
n = h * w
raw = []
for i in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(1)
  raw += add
wf = [[100 for _ in range(n)] for _ in range(n)]
for i in range(n):
  if raw[i] == 0:
    wf[i][i] = 0
    d = []
    if i-w >= 0:
      d.append(i-w)
    if i+w < n:
      d.append(i+w)
    if i%w != 0:
      d.append(i-1)
    if (i+1)%w != 0:
      d.append(i+1)
    for e in d:
      try:
        if raw[e] == 0:
          wf[i][e] = 1
      except:
        print(e)
#for x in wf:
  #print(x)
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][k] + wf[k][j] < wf[i][j]:
        wf[i][j] = wf[i][k] + wf[k][j]
ans = 0
for i in range(n):
  for j in range(n):
    if ans < wf[i][j] % 100:
      ans = wf[i][j]
print(ans)
#for x in wf:
  #print(x)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int,input().split())
l = []
for i in range(h):
    s = list(input())
    l.append(s)
q = deque()
s = [[1,0],[0,1],[-1,0],[0,-1]]
def aaa(i,j,h,w):
    if i >= 0 and i <= h-1 and j >= 0 and j <= w-1:
        return True
    else:
        return False
ans = []
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            rl = [[-1 for i in range(w)] for j in range(h)]
            rl[i][j] = 0
            q.append([i,j])
            while len(q) > 0:
                a,b = deque.popleft(q)
                for x in s:
                    if aaa(a+x[0],b+x[1],h,w):
                        if l[a+x[0]][b+x[1]] == ".":
                            if rl[a+x[0]][b+x[1]] > 0:
                                rl[a+x[0]][b+x[1]] = min(rl[a+x[0]][b+x[1]],rl[a][b]+1)
                            else:
                                rl[a+x[0]][b+x[1]] = rl[a][b]+1
                                q.append([a+x[0],b+x[1]])
            for y in range(h):
                ans.append(max(rl[y]))
print(max(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from itertools import product
from collections import deque


def bfs(maze, s):
  dq = deque()
  count = 0
  dq.append((s[0], s[1], count))
  visited = numpy.zeros(maze.shape, dtype=numpy.int)
  while dq:
    x, y, count = dq.popleft()
    for id in range(4):
      dx, dy = map(lambda x:int(x.real), [(0+1j)**(id), (0+1j)**(id+1)])
      if x+dx < 0 or y+dy < 0 or maze.shape[0] <= x+dx or maze.shape[1] <= y+dy:
        continue
      if maze[x+dx, y+dy]==1 and visited[x+dx, y+dy]!=1:
        dq.append((x+dx, y+dy, count+1))
        visited[(x+dx, y+dy)] = 1
  return count


def main():
  h, w = map(int, input().strip().split())
  maze = numpy.zeros((h, w), dtype=numpy.int)
  scores = numpy.full((h, w), -1, dtype=numpy.int)
  for ih in range(h):
    maze[ih] = [(0 if c=='#' else 1)for c in input().strip('')]
  for sx, sy in product(range(h), range(w)):
    if maze[sx, sy] == 0:
      continue
    scores[sx, sy] = bfs(maze, (sx, sy))
  print(numpy.max(scores))


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

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

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [float('inf') for w in range(W)] for h in range(H)]
        que.append([h, w])
        history[h][w] = 0
        while len(que) != 0:
            [x, y] = que.popleft()
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx and newx < H and 0 <= newy and newy < W and S[newx][newy] != "#" and history[newx][newy] == float('inf'):
                    history[newx][newy] = history[x][y] + 1
                    que.append([newx, newy])
        for h in range(H):
            for w in range(W):
                if history[h][w] == float('inf'):
                    history[h][w] = 0
        current_max_cost = max(list(itertools.chain.from_iterable(history)))
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

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

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [float('inf') for w in range(W)] for h in range(H)]
        que.append([h, w, 0])
        while len(que) != 0:
            [x, y, cost] = que.popleft()
            history[x][y] = cost
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx < H and 0 <= newy < W and history[newx][newy] != "#" and history[newx][newy] > cost + 1:
                    que.append([newx, newy, cost + 1])
        for h in range(H):
            for w in range(W):
                if history[h][w] == float('inf'):
                    history[h][w] = 0
        current_max_cost = max(list(itertools.chain.from_iterable(history)))
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

max_cost = 0


for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [float('inf') for w in range(W)] for h in range(H)]
        que.append([h, w, 0])
        while len(que) != 0:
            [x, y, cost] = que.popleft()
            history[x][y] = cost
            if x + 1 < H and S[x+1][y] != "#" and history[x+1][y] > cost + 1:
                que.append([x + 1, y, cost + 1])
            if y + 1 < W and S[x][y+1] != "#" and history[x][y+1] > cost + 1:
                que.append([x, y + 1, cost + 1])
            if y -1 >= 0 and S[x][y-1] != "#" and history[x][y-1] > cost + 1:
                que.append([x, y - 1, cost + 1])
            if x - 1 >= 0 and S[x-1][y] != "#" and history[x-1][y] > cost + 1:
                que.append([x-1, y, cost + 1])
        for h in range(H):
            for w in range(W):
                if history[h][w] == float('inf'):
                    history[h][w] = 0
        current_max_cost = max(list(itertools.chain.from_iterable(history)))
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

max_cost = 0


for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [float('inf') for w in range(W)] for h in range(H)]
        que.append([h, w, 0])
        while len(que) != 0:
            [x, y, cost] = que.pop()
            history[x][y] = cost
            if x + 1 < H and S[x+1][y] != "#" and history[x+1][y] > cost + 1:
                que.append([x + 1, y, cost + 1])
            if y + 1 < W and S[x][y+1] != "#" and history[x][y+1] > cost + 1:
                que.append([x, y + 1, cost + 1])
            if y -1 >= 0 and S[x][y-1] != "#" and history[x][y-1] > cost + 1:
                que.append([x, y - 1, cost + 1])
            if x - 1 >= 0 and S[x-1][y] != "#" and history[x-1][y] > cost + 1:
                que.append([x-1, y, cost + 1])
        for h in range(H):
            for w in range(W):
                if history[h][w] == float('inf'):
                    history[h][w] = 0
        current_max_cost = max(list(itertools.chain.from_iterable(history)))
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)