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 queue

H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
x = 0
y = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]


for _ in range(H):
    MAP.append(list(input()))

def bfs(S):
    que = queue.Queue()
    d = [[INF for i in range(W)] for j in range(H)]
    que.put(S)
    d[S[x]][S[y]] = 0
    
    while not que.empty():
        p = que.get()
        for i in range(4):
            nx = p[x] + dx[i]
            ny = p[y] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] != "#" and d[nx][ny] == INF:
                que.put([nx,ny])
                d[nx][ny] = d[p[x]][p[y]] + 1
    
    MAX = -1
    for i in range(H):
        for j in range(W):
            if d[i][j] != INF and MAX < d[i][j]:
                MAX = d[i][j]
                index = [i,j]
    return MAX, index

MAX, START = bfs([0,0])
MAX, GOAL = bfs(START)

print(MAX)

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int,input().split())
MAP = []
x = 0
y = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]


for _ in range(H):
    MAP.append(list(input()))

def bfs(A,B):
    que = queue.Queue()
    d = [[-1 for i in range(W)] for j in range(H)]
    que.put(A)
    d[A[x]][A[y]] = 0
    
    while que:
        p = que.get()
        if p == B:
            break
        for i in range(4):
            nx = p[x] + dx[i]
            ny = p[y] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] != "#" and d[nx][ny] == -1:
                que.put([nx,ny])
                d[nx][ny] = d[p[x]][p[y]] + 1
    
    return d[B[x]][B[y]]

print(max(bfs([0,0],[H-1,0]),bfs([0,0],[0,W-1]),bfs([0,0],[H-1,W-1]),bfs([H-1,0],[0,W-1]),bfs([H-1,0],[H-1,W-1]),bfs([0,W-1],[H-1,W-1])))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import queue

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

def bfs(h, w):
    q = queue.Queue()
    q.put((h, w, 0))
    f = [[False] * W for _ in range(H)]
    max_d = 0
    while q.qsize() > 0:
        h, w, d = q.get()
        f[h][w] = True
        max_d = max(max_d, d)
        for dh, dw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if h + dh >= 0 and h + dh < H and w + dw >= 0 and w + dw < W:
                if f[h+dh][w+dw] == False and m[h+dh][w+dw] == '.':
                    q.put((h+dh, w+dw, d+1))
    return max_d    

max_d = 0
for h in range(H):
    for w in range(W):
        max_d = max(max_d, bfs(h, w))
        
print(max_d)

Submission status: Wrong Answer

Solution code:
import copy
import collections
import sys


def input():
    return sys.stdin.readline()[:-1]


def bfs(sx, sy, gx, gy):
    # sx,sy := スタートの座標
    # gx,gy := ゴールの座標
    que = collections.deque()
    que.append([sx, sy])
    d = [[inf]*W for _ in range(H)]
    d[sx][sy] = 0
    s = copy.copy(field)
    while (len(que) > 0):
        p = que.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 and s[nx][ny] != "#" and d[nx][ny] == inf):
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]


inf = float('inf')
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
d = [[inf]*W for _ in range(H)]

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

cand = []
memo = []

for h1 in range(H):
    for w1 in range(W):
        for h2 in range(H):
            for w2 in range(W):
                if h1 == h2 and w1 == w2:
                    continue
                cand.append([h1, w1, h2, w2])
for c in cand:
    res = bfs(*c)
    if res != float('inf'):
        memo.append(res)
print(max(memo))

Submission status: Wrong Answer

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

M = [str(input()) for _ in range(h)]
M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

from collections import deque
ans = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        if M[sy][sx] == '#':
            continue
        q = deque()
        q.append((sy, sx))
        visit = [[-1]*(w+2) for _ in range(h+2)]
        visit[sy][sx] = 0
        while q:
            y, x = q.popleft()
            for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
                ny, nx = y+dy, x+dx
                if visit[ny][nx] == -1 and M[ny][nx] != '#':
                    visit[ny][nx] = visit[y][x]+1
                    q.append((ny, nx))
        ans = max(ans, max(max(visit)))
print(ans)

Submission status: Wrong Answer

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

M = [str(input()) for _ in range(h)]
M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

from collections import deque
ans = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        q = deque()
        q.append((sy, sx))
        visit = [[-1]*(w+2) for _ in range(h+2)]
        visit[sy][sx] = 0
        while q:
            y, x = q.popleft()
            for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
                ny, nx = y+dy, x+dx
                if visit[ny][nx] == -1 and M[ny][nx] != '#':
                    visit[ny][nx] = visit[y][x]+1
                    q.append((ny, nx))
        ans = max(ans, max(max(row) for row in visit))
print(ans)

Submission status: Wrong Answer

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

M = [str(input()) for _ in range(h)]
M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

from collections import deque
ans = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        q = deque()
        q.append((sy, sx))
        visit = [[-1]*(w+2) for _ in range(h+2)]
        visit[sy][sx] = 0
        while q:
            y, x = q.popleft()
            for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
                ny, nx = y+dy, x+dx
                if visit[ny][nx] == -1 and M[ny][nx] != '#':
                    visit[ny][nx] = visit[y][x]+1
                    q.append((ny, nx))
        ans = max(ans, max([max(row) for row in visit]))
print(ans)

Submission status: Wrong Answer

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

M = [str(input()) for _ in range(h)]
M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

from collections import deque
ans = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        q = deque()
        q.append((sy, sx))
        visit = [[-1]*(w+2) for _ in range(h+2)]
        visit[sy][sx] = 0
        while q:
            y, x = q.popleft()
            for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
                ny, nx = y+dy, x+dx
                if visit[ny][nx] == -1 and M[ny][nx] != '#':
                    visit[ny][nx] = visit[y][x]+1
                    q.append((ny, nx))
        ans = max(ans, max(max(visit)))
print(ans)

Submission status: Wrong Answer

Solution code:
#各道ごとに幅優先探索で一番遠い道への距離を調べ、リストに加えていく
#幅優先探索でキューを使う

H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = ''.join(['#']*(W+2))
S[-1] = ''.join(['#']*(W+2))
for i in range(1,H+1):
  S[i] = '#'+input()+'#'

maxd = 0
import queue
dy = [1,0,-1,0]
dx = [0,1,0,-1]
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=='.':
      visited = [[False]*(W+2) for _ in range(H+2)]
      q = queue.Queue()
      q.put([h,w,0])
      while not q.empty():
        a,b,c = q.get()
        for i in range(4):
          y,x = a+dy[i], b+dx[i]
          if S[y][x]=='.' and visited[y][x]==False:
            q.put([y,x,c+1])
            visited[y][x]=True
      maxd = max(maxd,c)
print(maxd)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
h, w = map(int,input().split())
s = [input() for _ in range(h)]
result = []
for xx in range(h):
    for yy in range(w):
        if s[xx][yy]==".":
            visit = np.array([np.array([-1 for _ in range(w)]) for __ in range(h)])
            visit[xx][yy] = 0

            q = deque([[xx,yy]])
            while q:
                x, y = q.pop()
                for i in [-1, 1]:
                    if 0 <= x+i and x+i < h:
                        if s[x+i][y] != "#" and visit[x+i][y] < 0:
                            visit[x+i][y] = visit[x][y]+1
                            q.append([x+i, y])
                    if 0 <= y+i and y+i < w:
                        if s[x][y+i] != "#" and visit[x][y+i] < 0:
                            visit[x][y+i] = visit[x][y]+1
                            q.append([x, y+i])
            result.append(max(visit.flatten()))
print(max(result))

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
ans=0
fence=["#"]*(W+2)
field=[fence]
for _ in range(H):
  L=list(input())
  field.append(["#"]+L+["#"])
field.append(fence)
for i in range(1,H+1):
  for j in range(1,W+1):
    if field[i][j]==".": 
      pos=deque([[i,j,0]])
      while pos:
        x,y,depth=pos.popleft()
        field[x][y]="#"
        if field[x-1][y]!="#":
          pos.append([x-1,y,depth+1])
        if field[x+1][y]!="#":
          pos.append([x+1,y,depth+1])
        if field[x][y+1]!="#":
          pos.append([x,y+1,depth+1])
        if field[x][y-1]!="#":
          pos.append([x,y-1,depth+1])
      if ans<depth:
        ans=depth
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = float("inf")

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

N = H*W

data = ["#" * (W+2)]
for i in range(H):
  data.append("#"+input()+"#")
data.append("#" * (W+2))

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

nodes = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if data[i][j] == ".":
      nodes.append((i,j))

FARTHEST = 0

for start_node in nodes:
  i = start_node[0]
  j = start_node[1]
  d = [[INF]*(W+2) for i in range(H+2)]
  d[i][j] = 0
  q = deque([(i,j)])
  res = 0
  while q:
    x,y = q.popleft()
    nd = d[x][y]+1
    for o in offsets:
      nx, ny = x+o[0], y+o[1]
      if data[nx][ny] == "#":
        continue
      if nd < d[nx][ny]:
        d[nx][ny] = nd
        q.append((nx,ny))
        res = nd

print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
#input = sys.stdin.readline

def main():        
    h,w=map(int,input().split())
    s=[[]*w for _ in range(h)]
    for i in range(h):
        s[i]=list(input())
    ans=0
    chk=deque()
    d=[[0,1],[0,-1],[1,0],[-1,0]]
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            a=[[-1]*w for _ in range(h)]
            a[i][j]=0
            chk.append([i,j])
            while chk:
                x,y=chk.popleft()
                bx,by=x,y
                for dx,dy in d:
                    x=dx+bx
                    y=dy+by
                    if x>=0 and y>=0 and x<=h-1 and y<=w-1:
                        if s[x][y]=='.' and a[x][y]==-1:
                            chk.append([x,y])
                            a[x][y]=a[bx][by]+1
                ans=max(ans,max(max(a)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

N = H*W

data = ["#" * (W+2)]
for i in range(H):
  data.append("#"+input()+"#")
data.append("#" * (W+2))

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

tree = {}
for i in range(1,H+1):
  for j in range(1,W+1):
    if data[i][j] != ".":
      pass
    else:
      tree[(i,j)] = []
      for o in offsets:
        i_ = i+o[0]
        j_ = j+o[1]
        if data[i_][j_] == "." :
          tree[(i,j)].append((i_,j_))

  
######1回目#####
flag = set()
# キューを作成して初期ノード(root)を入れる
q = deque()
q.append(list(tree.keys())[0])
farthest = None

# キューが空になるまで繰り返す
while len(q) > 0:
    # キューの先頭（左端）からnodeを取り出す
    node = q.popleft()
    if node is not None:
        farthest = node
        flag.add(node)
        childs = tree[node]
        for child in childs:
          if child not in flag:
            q.append(child)

  
######2回目#####
flag = set()
# キューを作成して初期ノード(root)を入れる
q = deque()
q.append((farthest,0))
farthest_ = None

# キューが空になるまで繰り返す
while len(q) > 0:
    # キューの先頭（左端）からnodeを取り出す
    data = q.popleft()
    node = data[0]
    distance = data[1]
    if node is not None:
        farthest_ = (node,distance)
        flag.add(node)
        childs = tree[node]
        for child in childs:
          if child not in flag:
            q.append((child,distance+1))

print(farthest_[1])

Submission status: Wrong Answer

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

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


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q = deque([[s, t]])
    while q:
        x, y = q.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q.append([nx, ny])
            depth[nx][ny] += r
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Wrong Answer

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

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


def bfs(s, t):
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q = deque([[s, t]])
    while q:
        x, y = q.popleft()
        visited[x][y] += 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q.append([nx, ny])
            depth[nx][ny] = depth[x][y] + 1
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Wrong Answer

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

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
ans = 0
for i in range(h):
    for j in range(w):
        visited = [[False] * w for _ in range(h)]
        depth = np.zeros((h, w))
        q = deque([[i, j]])
        while q:
            x, y = q.popleft()
            visited[x][y] = True
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if nx < 0 or h-1 < nx:
                    continue
                if ny < 0 or w-1 < ny:
                    continue

                if mass[nx][ny] == "#":
                    continue
                if visited[nx][ny]:
                    continue

                q.append([nx, ny])
                depth[nx][ny] = depth[x][y] + 1
        ans = max(ans, np.max(depth))
print(int(ans))

Submission status: Wrong Answer

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

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
ans = 0
for i in range(h):
    for j in range(w):
        visited = [[False] * w for _ in range(h)]
        depth = [[0] * w for _ in range(h)]
        q = deque([[i, j]])
        while q:
            x, y = q.popleft()
            visited[x][y] = True
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if nx < 0 or h-1 < nx:
                    continue
                if ny < 0 or w-1 < ny:
                    continue

                if mass[nx][ny] == "#":
                    continue
                if visited[nx][ny]:
                    continue

                q.append([nx, ny])
                depth[nx][ny] = depth[x][y] + 1
        for row in depth:
            ans = max(ans, max(row))
print(ans)

Submission status: Wrong Answer

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

  
already = [[False]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if mapping[i][j] == "#":
      already[i][j] = True


ans = 0

for i in range(h):
  for j in range(w):
    if already[i][j]:
      continue
    
    yet = copy.deepcopy(already)
    yet[i][j] = True
    not_yet = deque([])
    
    depth = [[0]*w for i in range(h)]
    
    if i != 0 and not yet[i-1][j]:
        not_yet.append([i-1, j])
        depth[i-1][j] = 1
        yet[i-1][j] = True
    if i != h-1 and not yet[i+1][j]:
        not_yet.append([i+1, j])
        depth[i+1][j] = 1
        yet[i+1][j] = True
    if j != 0 and not yet[i][j-1]:
        not_yet.append([i, j-1])
        depth[i][j-1] = 1
        yet[i][j-1] = True
    if j != w-1 and not yet[i][j+1]:
        not_yet.append([i, j+1])
        depth[i][j+1] = 1
        yet[i][j+1] = True
    
    while len(not_yet) > 0:
        key = not_yet.popleft()
        a, b = key[0], key[1]
        
        if a != 0 and not yet[a-1][b]:
            not_yet.append([a-1, b])
            yet[a-1][b] = True
            depth[a-1][b] = depth[a][b]+1
            
        if a != h-1 and not yet[a+1][b]:
            not_yet.append([a+1, b])
            yet[a+1][b] = True
            depth[a+1][b] = depth[a][b]+1
            
        if b != 0 and not yet[a][b-1]:
            not_yet.append([a, b-1])
            yet[a][b-1] = True
            depth[a][b-1] = depth[a][b]+1
            
        if b != w-1 and not yet[a][b+1]:
            not_yet.append([a, b+1])
            yet[a][b+1] = True
            depth[a][b+1] = depth[a][b]+1
            
    k = 0
    for i in range(h):
        for j in range(w):
            if k < depth[i][j]:
                k = depth[i][j]
    if ans < k:
        ans = k

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]
inf = 1000000
dist = [[inf]*(W*H) for _ in range(W*H)]

def bfs(s):
    seen = set()
    stk = [(s, 0)]
    while stk:
        pt, dst = stk.pop()
        ph, pw = pt//W, pt%W
        if(pt in seen and dst>=dist[s][pt]):
            continue
        seen.add(pt)

        if(S[ph][pw]=='#'):
            dist[s][pt] = 0
            continue

        for x,y in ((1,0), (-1,0), (0, 1), (0,-1)):
            if((not 0<=pw+x<W )or (not 0<=ph+y<H)):
                continue
            else:
                ns = (ph+y)*W + (pw+x)
                stk.insert(0, (ns, dst+1))
        dist[s][pt] = min(dst, dist[s][pt])
        
ans = 0
for s in range(H*W):
    h, w = s//W, s%W
    if(S[h][w]=='#'):
        continue
    bfs(s)
    
    ans = max(ans, max(dist[s]))

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]
inf = 1000000
dist = [[inf]*(W*H) for _ in range(W*H)]

def bfs(s):
    seen = set()
    stk = [(s, 0)]
    while stk:
        pt, dst = stk.pop()
        ph, pw = pt//W, pt%W
        if(pt in seen):
            continue
        seen.add(pt)

        if(S[ph][pw]=='#'):
            dist[s][pt] = 0
            continue

        for x,y in ((1,0), (-1,0), (0, 1), (0,-1)):
            if((not 0<=pw+x<W )or (not 0<=ph+y<H)):
                continue
            else:
                ns = (ph+y)*W + (pw+x)
                stk.insert(0, (ns, dst+1))
        dist[s][pt] = min(dst, dist[s][pt])
        
ans = 0
for s in range(H*W):
    h, w = s//W, s%W
    if(S[h][w]=='#'):
        continue
    bfs(s)
    
    ans = max(ans, max(dist[s]))

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]
inf = 1000000
dist = [[inf]*(W*H) for _ in range(W*H)]

def bfs(s):
    seen = set()
    stk = [(s, 0)]
    while stk:
        pt, dst = stk.pop()
        ph, pw = pt//W, pt%W
        if(pt in seen):
            continue
        seen.add(pt)

        if(S[ph][pw]=='#'):
            dist[s][pt] = 0
            continue

        for x,y in ((1,0), (-1,0), (0, 1), (0,-1)):
            if((not 0<=pw+x<W )or (not 0<=ph+y<H)):
                continue
            else:
                ns = (ph+y)*W + (pw+x)
                stk.insert(0, (ns, dst+1))
        dist[s][pt] = min(dst, dist[s][pt])
        
ans = 0
for s in range(H*W-1):
    h, w = s//W, s%W
    if(S[h][w]=='#'):
        continue
    bfs(s)
    
    ans = max(ans, max(dist[s]))

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]
inf = 1000000
dist = [[inf]*(W*H) for _ in range(W*H)]

def dfs(s):
    stk = [(s, 0, set())]
    while stk:
        pt, dst, seen = stk.pop()
        ph, pw = pt//W, pt%W
        if(pt in seen):
            continue
        seen.add(pt)

        if(S[ph][pw]=='#'):
            dist[s][pt] = 0
            continue

        for x,y in ((1,0), (-1,0), (0, 1), (0,-1)):
            if((not 0<=pw+x<W )or (not 0<=ph+y<H)):
                continue
            else:
                ns = (ph+y)*W + (pw+x)
                nseen = set(seen)
                stk.append((ns, dst+1, nseen))
        dist[s][pt] = min(dst, dist[s][pt])
        
ans = 0
for s in range(H*W-1):
    h, w = s//W, s%W
    if(S[h][w]=='#'):
        continue
    dfs(s)
    
    ans = max(ans, max(dist[s]))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [0] * h
for i in range(h):
    maze[i] = list(input())
# print(maze)
INF = int(1e10 + 7)
d = [[INF] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# que = deque([('x', 'y')])
# print(que)
# print(que[0])

def bfs(x, y):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([(x, y)])
    d[x][y] = 0

    while len(que) != 0:
        val = que.popleft()

        for i in range(4):
            nx = val[0] + dx[i]
            ny = (val[1] + dy[i])
            if (0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '#' and d[nx][ny] == INF):
                que.append((nx, ny))
                d[nx][ny] = d[val[0]][val[1]] + 1
    maxval = 0
    for i in range(h):
        for j in range(w):
            if d[i][j] > maxval and d[i][j] != INF:
                maxval = d[i][j]
    return maxval

maxans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            if bfs(i, j) > maxans:
                maxans = bfs(i, j)
print(maxans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product
H,W = map(int,input().split())

S = ["#"*(W+2)]
for i in range(H):
    S.append("#"+ input() + "#")
S.append("#"*(W+2))

H += 2
W += 2

max_dist = 0
for sy,sx in product(range(1,H),range(1,W)):
    dist = [[H+W+1]*W for i in range(H)]
    if S[sy][sx] == "#":
        continue
    dq = deque([(sy,sx)])
    dist[sy][sx] = 0
    while dq:
        py,px = dq.popleft()
        for ny, nx in [(py+1,px),(py-1,px),(py,px+1),(py,px-1)]:
            if S[ny][nx] == "#":
                continue
            if dist[ny][nx] > dist[py][px] + 1:
                dist[ny][nx] = dist[py][px] + 1
                max_dist = max(max_dist, dist[ny][nx])
                dq.append((ny,nx))

print(max_dist)

Submission status: Wrong Answer

Solution code:
import queue

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


def srch(h,w):
    ans = 0
    cnt = [[-1 for _ in range(W)] for _ in range(H)]
    que = queue.Queue()
    li1 = [1,0,-1,0]
    li2 = [0,1,0,-1]
    ans = 0

    que.put([h,w,0])
    cnt[h][w]=0

    while not(que.empty()):
        plc = que.get()
        y = plc[0]
        x = plc[1]
        ans = plc[2]

        for i in range(4):
            ny,nx = y+li1[i], x+li2[i]
            # print(ny,nx)
            if ny>=0 and ny<H and nx>=0 and nx<W and cnt[ny][nx]==-1 and S[ny][nx]==".":
                ans += 1
                cnt[ny][nx]= ans
                que.put([ny,nx,ans])
    return ans


ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans = max(ans,srch(h,w))
        # print(h,w,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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


def srch(h,w):
    ans = 0
    cnt = [[-1 for _ in range(W)] for _ in range(H)]
    que = queue.Queue()
    li1 = [1,0,-1,0]
    li2 = [0,1,0,-1]
    ans = 0

    que.put([h,w,0])
    cnt[h][w]=0

    while not(que.empty()):
        plc = que.get()
        y = plc[0]
        x = plc[1]
        ans = plc[2]

        for i in range(4):
            ny,nx = y+li1[i], x+li2[i]
            # print(ny,nx)
            if ny>=0 and ny<H and nx>=0 and nx<W and cnt[ny][nx]==-1 and S[ny][nx]==".":
                ans += 1
                cnt[ny][nx]= ans
                que.put([ny,nx,ans])

    return ans


ans = 0

for h in range(H):
    for w in range(W):
        ans = max(ans,srch(h,w))
        # print(h,w,ans)

print(ans)

Submission status: Wrong Answer

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

from collections import deque
import numpy as np
def bfs(sy, sx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        #if y == gy and x == gx:
            #break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    d = np.array(d)
    return np.max(d)

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
from collections import deque
def bfs(sy, sx, gy, gx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    return d[gy][gx]

ans = 0
for gy in range(h):
    for gx in range(w):
        for sy in range(h):
            for sx in range(w):
                ans = max(ans, bfs(gy, gx, sy, sx))
print(ans)

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
h,w=map(int,input().split())
s=[]

for i in range(h):
    s.append(list(input()))
dx=[1,0,-1,0]#東南西北
dy=[0,-1,0,1]
ans=0
def search(i,j):
    if s[i][j]=="#":
        return 0
    max_step=0
    que=deque()
    que.append([i,j])#1現在地
    dist=[[-1 for _ in range(w)] for _ in range (h)]
    #(h,w)
    dist[i][j]=0#現在地は0
    while que:#行き先が無くなるまで
        y,x=que.popleft()#現在地を取り出す(y,x)
        for dir in range(4):
            nx=x+dx[dir]#行き先(nx,xy)
            ny=y+dy[dir]
            if ny<0 or ny>=h or nx<0 or nx>=w or s[ny][nx]=="#":#壁の中
                pass#何もしない
            elif dist[ny][nx]!=-1:#捜索済み
                pass
            elif s[ny][nx]==".":
            #未捜索地点"."
                dist[ny][nx]=dist[y][x]+1#1進む
                que.append([ny,nx])
    out=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]==-1:
                pass
            out=max(out,dist[i][j])
    return out

for i in range(h):
    for j in range(w):
        step=search(i,j)#(j,i)の時の最大移動数を求める
        print(step)
        if ans<step:
            ans=step
print(ans)

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
h,w=map(int,input().split())
s=[]

for i in range(h):
    s.append(list(input()))
dx=[1,0,-1,0]#東南西北
dy=[0,-1,0,1]
ans=0
def search(i,j):
    if s[i][j]=="#":
        return 0
    max_step=0
    que=deque()
    que.append([i,j])#1現在地
    dist=[[-1 for _ in range(w)] for _ in range (h)]
    #(h,w)
    dist[i][j]=0#現在地は0
    while que:#行き先が無くなるまで
        y,x=que.popleft()#現在地を取り出す(y,x)
        for dir in range(4):
            nx=x+dx[dir]#行き先(nx,xy)
            ny=y+dy[dir]
            if ny<0 or ny>=h or nx<0 or nx>=w or s[ny][nx]=="#":
              	#壁の中
                pass
            elif dist[ny][nx]!=-1:
              	#捜索済み
                pass
            else:
              	#未捜索地点"."
                dist[ny][nx]=dist[y][x]+1#1進む
                que.append([ny,nx])
    out=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]==-1:
                break
            out=max(out,dist[i][j])
    return out

for i in range(h):
    for j in range(w):
        step=search(i,j)#(j,i)の時の最大移動数を求める
        if ans<step:
            ans=step
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

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

ans = 0
for x in range(H):
    for y in range(W):
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])
        
        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])
        
        #start位置は0で初期化
        distance[x][y] = 0
        #print(distance[0])
        #print(distance[1])
        #print(distance[2])
        ans = max(ans, np.max(distance))
        
print(ans)