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, defaultdict

inf = 10**15
h, w = map(int, input().split())
#隣接リスト
#G = defaultdict(lambda:[])
G = [[inf]*(h*w) for _ in range(h*w)]
#################################

def warshall_floyd(d):
    #d[i][j]:iからjに行く最短経路
    for k in range(h*w):
        for i in range(h*w):
            for j in range(h*w):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
  
li = []
for j in range(h):
    g = list(input())
    temp = []
    for i in g:
      if i=='.':
        temp.append(0)
      else:
        temp.append(1)
    li.append(temp)
for i in range(h):
    for j in range(w-1):
        if li[i][j]==0 and li[i][j+1]==0:
            G[i*w+j][i*w+j+1] = 1
            G[i*w+j+1][i*w+j] = 1
for i in range(h-1):
    for j in range(w):
        if li[i][j] ==0 and li[i+1][j]==0:
            G[i*w+j][i*w+w+j] = 1
            G[i*w+j+w][i*w+j] = 1
    
#################################
d = warshall_floyd(G)
max_ = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] < inf:
      max_ = max(max_, d[i][j])
print(max_)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict

inf = 10**15
h, w = map(int, input().split())
#隣接リスト
#G = defaultdict(lambda:[])
G = [[inf]*(h*w) for _ in range(h*w)]
#################################

def warshall_floyd(d):
    #d[i][j]:iからjに行く最短経路
    for k in range(h*w):
        for i in range(h*w):
            for j in range(h*w):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
  
li = []
for j in range(h):
    g = list(input())
    temp = []
    for i in g:
      if i=='.':
        temp.append(0)
      else:
        temp.append(1)
    li.append(temp)
for i in range(h):
    for j in range(w-1):
        if li[i][j]==0 and li[i][j+1]==0:
            G[i*w+j][i*w+j+1] = 1
            G[i*w+j+1][i*w+j] = 1
for i in range(h-1):
    for j in range(w):
        if li[i][j] ==0 and li[i+1][j]==0:
            G[i*w+j][i*w+w+j] = 1
            G[i*w+j+w][i*w+j] = 1
    
#################################
d = warshall_floyd(G)
max_ = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] != inf:
      max_ = max(max_, d[i][j])
print(max_)

Submission status: Wrong Answer

Solution code:

from collections import deque, defaultdict

def warshall_floyd(d):
    #d[i][j]:iからjに行く最短経路
    for k in range(h*w):
        for i in range(h*w):
            for j in range(h*w):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
inf = 10**15
h, w = map(int, input().split())
#隣接リスト
#G = defaultdict(lambda:[])
G = [[inf]*(h*w) for _ in range(h*w)]
#################################

def warshall_floyd(d):
    #d[i][j]:iからjに行く最短経路
    for k in range(h*w):
        for i in range(h*w):
            for j in range(h*w):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
  
li = []
for j in range(h):
    g = list(input())
    li.append(g)
for i in range(h):
    for j in range(w-1):
        if li[i][j]=='.' and li[i][j+1]=='.':
            G[i*w+j][i*w+j+1] = 1
            G[i*w+j+1][i*w+j] = 1
for i in range(h-1):
    for j in range(w):
        if li[i][j] == '.' and li[i+1][j]=='.':
            G[i*w+j][i*w+w+j] = 1
            G[i*w+j+w][i*w+j] = 1
    
#################################
d = warshall_floyd(G)
max_ = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] != inf:
      max_ = max(max_, d[i][j])
print(max_)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[x][y] = 0
    d = deque()
    d.append((x, y))
    while(len(d) != 0):
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1:  # 上
                if c[h-1][w] == '.':
                    dist[h-1][w] = dist[h][w]+1
                    d.append((h-1, w))

            if h != H-1 and dist[h+1][w] == -1:  # 下
                if c[h+1][w] == '.':
                    dist[h+1][w] = dist[h][w]+1
                    d.append((h+1, w))

            if w != 0 and dist[h][w-1] == -1:  # 左
                if c[h][w-1] == '.':
                    dist[h][w-1] = dist[h][w]+1
                    d.append((h, w-1))

            if w != W-1 and dist[h][w+1] == -1:  # 右
                if c[h][w+1] == '.':
                    dist[h][w+1] = dist[h][w]+1
                    d.append((h, w+1))

    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[x][y] = 0
    d = deque()
    d.append((x, y))
    while(len(d) != 0):
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1 and c[h-1][w] == '.':  # 上
                dist[h-1][w] = dist[h][w]+1
                d.append((h-1, w))
            if h != H-1 and dist[h+1][w] == -1 and c[h+1][w] == '.':  # 下
                dist[h+1][w] = dist[h][w]+1
                d.append((h+1, w))
            if w != 0 and dist[h][w-1] == -1 and c[h][w-1] == '.':  # 左
                dist[h][w-1] = dist[h][w]+1
                d.append((h, w-1))
            if w != W-1 and dist[h][w+1] == -1 and c[h][w+1] == '.':  # 右
                dist[h][w+1] = dist[h][w]+1
                d.append((h, w+1))
    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[x][y] = 0
    d = deque()
    d.append((x, y))
    while(len(d) != 0):
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and c[h-1][w] == '.' and dist[h-1][w] == -1:  # 上
                dist[h-1][w] = dist[h][w]+1
                d.append((h-1, w))
            if h != H-1 and c[h+1][w] == '.' and dist[h+1][w] == -1:  # 下
                dist[h+1][w] = dist[h][w]+1
                d.append((h+1, w))
            if w != 0 and c[h][w-1] == '.' and dist[h][w-1] == -1:  # 左
                dist[h][w-1] = dist[h][w]+1
                d.append((h, w-1))
            if w != W-1 and c[h][w+1] == '.' and dist[h][w+1] == -1:  # 右
                dist[h][w+1] = dist[h][w]+1
                d.append((h, w+1))
    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[x][y] = 0
    d = deque()
    d.append((x, y))
    while(len(d) != 0):
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1:  # 上
                dist[h-1][w] = dist[h][w]+1
                d.append((h-1, w))
            if h != H-1 and dist[h+1][w] == -1:  # 下
                dist[h+1][w] = dist[h][w]+1
                d.append((h+1, w))
            if w != 0 and dist[h][w-1] == -1:  # 左
                dist[h][w-1] = dist[h][w]+1
                d.append((h, w-1))
            if w != W-1 and dist[h][w+1] == -1:  # 右
                dist[h][w+1] = dist[h][w]+1
                d.append((h, w+1))
    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(i, j):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[i][j] = 0
    d = deque()
    d.append((i, j))
    while(len(d) != 0):
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1:  # 上
                dist[h-1][w] = dist[h][w]+1
                d.append((h-1, w))
            if h != H-1 and dist[h+1][w] == -1:  # 下
                dist[h+1][w] = dist[h][w]+1
                d.append((h+1, w))
            if w != 0 and dist[h][w-1] == -1:  # 左
                dist[h][w-1] = dist[h][w]+1
                d.append((h, w-1))
            if w != W-1 and dist[h][w+1] == -1:  # 右
                dist[h][w+1] = dist[h][w]+1
                d.append((h, w+1))
    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
print(c)


def BFS(i, j):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[i][j] = 0
    d = deque()
    d.append((i, j))
    while(len(d) != 0):
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1:  # 上
                dist[h-1][w] = dist[h][w]+1
                d.append((h-1, w))
            if h != H-1 and dist[h+1][w] == -1:  # 下
                dist[h+1][w] = dist[h][w]+1
                d.append((h+1, w))
            if w != 0 and dist[h][w-1] == -1:  # 左
                dist[h][w-1] = dist[h][w]+1
                d.append((h, w-1))
            if w != W-1 and dist[h][w+1] == -1:  # 右
                dist[h][w+1] = dist[h][w]+1
                d.append((h, w+1))
    print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(i, j):
    #print(i, j)
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    #print('ok', dist)
    #print('i', i)
    dist[i][j] = 0
    #print(i, j, dist[i][j])
    d = deque()
    d.append((i, j))
    # print(d)
    #print('koko', dist)
    while(len(d) != 0):
        #print('d', dist)
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1:  # 上
                dist[h-1][w] = dist[h][w]+1
                d.append((h-1, w))
            if h != H-1 and dist[h+1][w] == -1:  # 下
                dist[h+1][w] = dist[h][w]+1
                d.append((h+1, w))
            if w != 0 and dist[h][w-1] == -1:  # 左
                dist[h][w-1] = dist[h][w]+1
                d.append((h, w-1))
            if w != W-1 and dist[h][w+1] == -1:  # 右
                dist[h][w+1] = dist[h][w]+1
                d.append((h, w+1))
    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(i, j):
    dist = [-1]*H
    for i in range(H):
        dist[i] = [-1]*W
    dist[i][j] = 0
    d = deque()
    d.append((i, j))
    # print(d)
    while(len(d) != 0):
        h, w = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1:  # 上
                dist[h-1][w] = dist[h][w]+1
                d.append((h-1, w))
            if h != H-1 and dist[h+1][w] == -1:  # 下
                dist[h+1][w] = dist[h][w]+1
                d.append((h+1, w))
            if w != 0 and dist[h][w-1] == -1:  # 左
                dist[h][w-1] = dist[h][w]+1
                d.append((h, w-1))
            if w != W-1 and dist[h][w+1] == -1:  # 右
                dist[h][w+1] = dist[h][w]+1
                d.append((h, w+1))
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def bfs(x0, y0, maze, dis):
    from collections import deque
    max_x = len(maze[0])
    max_y = len(maze)

    dis[y0][x0] = 0
    dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    q = deque()
    q.append([x0, y0, dis[y0][x0]])

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

        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy

            if 0 > nx or max_x <= nx or 0 > ny or max_y <= ny:
                continue
            if maze[ny][nx] == "#":
                continue
            if dis[ny][nx] != -1:
                continue

            dis[ny][nx] = d + 1
            q.append([nx, ny, dis[ny][nx]])

    return


h, w = map(int, input().split())

s = [[] for _ in range(h)]

for i in range(h):
    s[i] = input()

ans = 0
for i in range(h):
    for j in range(w):
        dis = [[-1] * w for _ in range(h)]

        if s[i][j] == ".":
            bfs(j, i, s, dis)

        d = 0

        for i in range(h):
            for j in range(w):
                d = max(d, dis[i][j])

        ans = max(ans, d)

print(ans)

Submission status: Wrong Answer

Solution code:
def bfs(x0, y0, maze, dis):
    from collections import deque
    max_x = len(maze[0])
    max_y = len(maze)

    dis[y0][x0] = 0
    dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    q = deque()
    q.append([x0, y0, dis[y0][x0]])

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

        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy

            if 0 > nx or max_x <= nx or 0 > ny or max_y <= ny:
                continue
            if maze[ny][nx] == "#":
                continue
            if dis[ny][nx] != -1:
                continue

            dis[ny][nx] = d + 1
            q.append([nx, ny, dis[ny][nx]])

    return


h, w = map(int, input().split())

s = [[] for _ in range(h)]

for i in range(h):
    s[i] = input()

ans = 0
for i in range(h):
    for j in range(w):
        dis = [[-1] * w for _ in range(h)]

        bfs(j, i, s, dis)

        d = 0

        for i in range(h):
            for j in range(w):
                d = max(d, dis[i][j])

        ans = max(ans, d)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

h,w=list(map(int,input().split()))
graph=[input() for _ in range(h)]#graph初期化

def f(x,y):#start地点(x,y)
  x-=1;y-=1
  dist=[[-1 for j in range(w)] for i in range(h)]#distance設定
  dist[x][y]=0#スタート地点は初期値0
  que = deque([(x,y,0)])#スタート地点とdist初期値を入力 

  while que:
    r,s,t = que.popleft()
    for i,j in [(-1,0),(0,-1),(1,0),(0,1)]:#これでi,jとれるの
      if not (0<=r+i<h and 0<=s+j<w):#座標がh,w内でなければ探索しない
        continue
      if dist[r+i][s+j]>0:#すでに訪れていたら探索しない
        continue
      if graph[r+i][s+j]=="#":#壁なら探索しない
        continue
      dist[r+i][s+j]=t+1#距離を前回の＋1
      que.append([r+i,s+j,t+1])#訪れてないのでqueに今の地点を追加する
  return np.amax(dist)#maxのmaxを返す

ans=0
for i in range(1,h+1):#全探索（indexのため1~h+1まで）
  for j in range(1,w+1):
    if graph[i-1][j-1]=="#":#壁なら探索しない
      continue
    ans=max(ans,f(i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

h,w=list(map(int,input().split()))
graph=[input() for _ in range(h)]#graph初期化

def f(x,y):#start地点(x,y)
  x-=1;y-=1
  dist=[[-1 for j in range(w)] for i in range(h)]#distance設定
  dist[x][y]=0#スタート地点は初期値0
  que = deque([(x,y,0)])#スタート地点とdist初期値を入力 

  while que:
    r,s,t = que.popleft()
    for i,j in [(-1,0),(0,-1),(1,0),(0,1)]:#これでi,jとれるの
      if not (0<=r+i<h and 0<=s+j<w):#座標がh,w内でなければ探索しない
        continue
      if dist[r+i][s+j]>0:#すでに訪れていたら探索しない
        continue
      if graph[r+i][s+j]=="#":#壁なら探索しない
        continue
      dist[r+i][s+j]=t+1#距離を前回の＋1
      que.append([r+i,s+j,t+1])#訪れてないのでqueに今の地点を追加する
  return np.amax(dist)#maxのmaxを返す

ans=0
for i in range(1,h+1):#全探索（indexのため1~h+1まで）
  for j in range(1,w+1):
    ans=max(ans,f(i,j))
print(ans)

Submission status: Wrong Answer

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

def f(x,y):#start地点(x,y)
  x-=1;y-=1
  dist=[[-1 for j in range(w)] for i in range(h)]#distance設定
  dist[x][y]=0#スタート地点は初期値0
  que = deque([(x,y,0)])#スタート地点とdist初期値を入力 

  while que:
    r,s,t = que.popleft()
    for i,j in [(-1,0),(0,-1),(1,0),(0,1)]:#これでi,jとれるの
      if not (0<=r+i<h and 0<=s+j<w):#座標がh,w内でなければ探索しない
        continue
      if dist[r+i][s+j]>0:#すでに訪れていたら探索しない
        continue
      if graph[r+i][s+j]=="#":#壁なら探索しない
        continue
      dist[r+i][s+j]=t+1#距離を前回の＋1
      que.append([r+i,s+j,t+1])#訪れてないのでqueに今の地点を追加する
  return max(max(dist))#maxのmaxを返す

ans=0
for i in range(1,h+1):#全探索（indexのため1~h+1まで）
  for j in range(1,w+1):
    ans=max(ans,f(i,j))
print(ans)

Submission status: Wrong Answer

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

#スタートする座標をa,bとしておく
def bfs(a,b):
  maze=copy.deepcopy(maze1)
  dp=[[0 for i in range(w)] for j in range(h)]
  q=deque([[a,b]])
  #まず自分がいるところを＃に変えておく
  maze[a][b]="#"
  while len(q)>0:
    i,j=q.popleft()
    if 0<=i+1<=h-1 and 0<=j<=w-1 and maze[i+1][j]==".":
      maze[i+1][j]="#" 
      dp[i+1][j]=dp[i][j]+1
      q.append([i+1,j])
    if 0<=i-1<=h-1 and 0<=j<=w-1 and maze[i-1][j]==".":
      maze[i-1][j]="#"
      dp[i-1][j]=dp[i][j]+1
      q.append([i-1,j])
    if 0<=i<=h-1 and 0<=j-1<=w-1 and maze[i][j-1]==".":
      maze[i][j-1]="#"
      dp[i][j-1]=dp[i][j]+1
      q.append([i,j-1])
    if 0<=i<=h-1 and 0<=j+1<=w-1 and maze[i][j+1]==".":
      maze[i][j+1]="#"
      dp[i][j+1]=dp[i][j]+1
      q.append([i,j+1])
  sum=0
  for i in range(h):
    sum=max(max(dp[i]),sum)
  return sum
  
  
ans=0
for k in range(int(h/2)+1):
  for l in range(w):
    if maze1[k][l]==".":
      ans=max(bfs(k,l),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))#壁
for i in range(h):
    l.append('#'+input()+'#')
l.append('#'*(w+2))#壁
p=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='#':
            continue
        s=[[-1 for a in b] for b in l]
        q=deque([[i,j]])
        s[i][j]=0
        while len(q)>0:
            a,b=q.popleft()
            for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
                if l[a+i][b+j]=='#' or s[a+i][b+j]>-1:
                    continue
                q.append([a+i,b+j])
                s[a+i][b+j]=s[a][b]+1
        r=0
        for a in s:
            for b in a:
                r=max(r,b)
        p=max(r,p)
print(p)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))#壁
for i in range(h):
    l.append('#'+input()+'#')
l.append('#'*(w+2))#壁
p=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='#':
            continue
        s=[[-1 for a in b] for b in l]
        q=deque([[i,j]])
        s[i][j]=0
        while len(q)>0:
            a,b=q.popleft()
            for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
                if l[a+i][b+j]=='#' or s[a+i][b+j]>-1:
                    continue
                q.append([a+i,b+j])
                s[a+i][b+j]=s[a][b]+1
        p=max(s[a][b],p)
print(p)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
L = [str(input()) for _ in range(H)]
ans = 0
for h in range(H):
    for w in range(W):
        if L[h][w] == '#':
            break
        else:
            flag = [[-1] * W for _ in range(H)]
            depth = [[0] * W for _ in range(H)]
            flag[h][w] = 0
            q = deque([(h, w)])
            while q:
                i, j = q.popleft()
                d = depth[i][j]
                if i != H - 1:
                    if L[i+1][j] == '.' and flag[i+1][j] < 0:
                        flag[i+1][j] = 0
                        depth[i+1][j] = d + 1
                        q.append((i+1, j))
                if i != 0:
                    if L[i-1][j] == '.' and flag[i-1][j] < 0:
                        flag[i-1][j] = 0
                        depth[i-1][j] = d + 1
                        q.append((i-1, j))
                if j != W - 1:
                    if L[i][j+1] == '.' and flag[i][j+1] < 0:
                        flag[i][j+1] = 0
                        depth[i][j+1] = d + 1
                        q.append((i, j+1))
                if j != 0:
                    if L[i][j-1] == '.' and flag[i][j-1] < 0:
                        flag[i][j-1] = 0
                        depth[i][j-1] = d + 1
                        q.append((i, j-1))
                ans = max(ans, d)
print(ans)

Submission status: Wrong Answer

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

for i in range(h):
  for j in range(w):
    if A[i][j]=='.':
      if i-1>=0:
          if A[i-1][j]=='.':
            g[i][j].append((i-1,j))
      if i+1<h:
          if A[i+1][j]=='.':
            g[i][j].append((i+1,j))          
      if j+1<w:
          if A[i][j+1]=='.':
            g[i][j].append((i,j+1))          
      if j-1>0:
          if A[i][j-1]=='.':
            g[i][j].append((i,j-1))  
        
from collections import deque
def bfs(a,b):
  time=[[-1]*w for _ in range(h)]
  time[a][b]=0
  stack=deque([])
  stack.append((a,b))
  n=1
  while stack:
    d=stack.popleft()
    for v in g[d[0]][d[1]]:
      if time[v[0]][v[1]]==-1:
        time[v[0]][v[1]]=time[d[0]][d[1]]+1
        stack.append(v)
        
      else:
        continue
      
  timem=0
  for i in range(h):
    for j in range(w):
      timem=max(timem,time[i][j])
  return timem
ans=0
for i in range(h):
  for j in range(w):
    bfsm=bfs(i,j)
    ans=max(ans,bfsm)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

res = 0
for i in range(h):
    for j in range(w):
        dist = [[-1] * w for _ in range(h)]
        dist[i][j] = 0
        d = deque()
        d.append([i, j])

        while len(d) > 0:
            pos_x, pos_y = d.popleft()
            dist_max = dist[pos_x][pos_y]
            for k in range(4):
                x, y = pos_x + dx[k], pos_y + dy[k]
                if 0 <= x < h and 0 <= y < w and s[x][y] == "." and dist[x][y] == -1:
                    dist[x][y] = dist[pos_x][pos_y] + 1
                    d.append([x, y])

        res = max(res, dist_max)

print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int,input().split())
s = [0]*(h+2)
s[0]  = ["#"]*(w+2)
s[-1] = ["#"]*(w+2)
for i in range(h):
    s[i+1] = ["#"] + list(input()) + ["#"]
ans = 0
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == "#":
            pass
        else:
            xs,ys = j,i
            qx = deque([])
            qx.append(xs)
            qy = deque([])
            qy.append(ys)
            reach = [[0 for j in range(w+2)] for i in range(h+2)]
            reach[ys][xs] = 1
            while qx:
                x = qx.popleft()
                y = qy.popleft()

                if s[y-1][x] == "." and reach[y-1][x] == 0:
                    qx.append(x)
                    qy.append(y-1)
                    reach[y-1][x] = reach[y][x] + 1
                if s[y+1][x] == "." and reach[y+1][x] == 0:
                    qx.append(x)
                    qy.append(y+1)
                    reach[y+1][x] = reach[y][x] + 1
                if s[y][x-1] == "." and reach[y][x-1] == 0:
                    qx.append(x-1)
                    qy.append(y)
                    reach[y][x-1] = reach[y][x] + 1
                if s[y][x+1] == "." and reach[y][x+1] == 0:
                    qx.append(x+1)
                    qy.append(y)
                    reach[y][x+1] = reach[y][x] + 1
            m = 0
            for i in range(h+2):
                m = max(m,max(reach[i][:])-1)
            ans = max(ans,m)
print(ans)