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())

maze=[]
INF=10**6
dx=[1,0,-1,0]
dy=[0,1,0,-1]

#マップ入力
for i in range(h):
    row=list(input())
    maze.append(row)


ans=0
for i in range(h):
    for j in range(w):
        queue=deque()
        d=[]
        used=[]
        for i in range(h):
            used.append([False for k in range(w)])
            d.append([INF for k in range(w)])
            
        if maze[i][j]==".":
            d[i][j]=0
            used[i][j]=True
            queue.append([i,j])

            while len(queue)>0:
                y,x=queue.popleft()
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=ny<h and 0<=nx<w:
                        if d[ny][nx]>d[y][x]+1 and maze[ny][nx]=="." and 0==used[ny][nx]:
                            d[ny][nx]=d[y][x]+1
                            ans=max(ans,d[ny][nx])
                            queue.append([ny,nx])
                            used[ny][nx]=True
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for si in range(H):
    for sj in range(W):
      if S[si][sj] == '#':
        continue

      dist = [[-1 for _ in range(W)] for _ in range(H)]
      q = deque()

      def update(pos, num):
        i, j = pos
        if dist[i][j] != -1:
          return
        dist[i][j] = num
        q.append(pos)

      start = (si, sj)
      update(start, 0)

      while q:
        qi, qj = q.popleft()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          update((ni, nj), dist[qi][qj]+1)
          ans = max(ans, dist[qi][qj])
    return ans


if __name__ == "__main__":
  print(main())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for si in range(H):
    for sj in range(W):
      if S[si][sj] == '#':
        continue

      dist = [[-1 for _ in range(W)] for _ in range(H)]
      q = deque()

      def update(pos, num):
        i, j = pos
        if dist[i][j] != -1:
          return
        dist[i][j] = num
        q.append(pos)

      start = (si, sj)
      update(start, 0)

      while q:
        qi, qj = q.popleft()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          update((ni, nj), dist[qi][qj]+1)
      ans = max(ans, max([max(x) for x in dist]))
    return ans


if __name__ == "__main__":
  print(main())

Submission status: Wrong Answer

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

maze=[]
INF=10**6
dx=[1,0,-1,0]
dy=[0,1,0,-1]

#マップ入力
for i in range(h):
    row=list(input())
    maze.append(row)


ans=0
for i in range(h):
    for j in range(w):
        queue=deque()
        d=[]
        used=[]
        for i in range(h):
            used.append([False for j in range(w)])
            d.append([INF for j in range(w)])
            
        if maze[i][j]==".":
            d[i][j]=0
            used[i][j]=True
            queue.append([i,j])

            while len(queue)>0:
                y,x=queue.popleft()
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=ny<h and 0<=nx<w:
                        if d[ny][nx]>d[y][x]+1 and maze[ny][nx]=="." and 0==used[ny][nx]:
                            d[ny][nx]=d[y][x]+1
                            ans=max(ans,d[ny][nx])
                            queue.append([ny,nx])
                            used[ny][nx]=True
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import deque
H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[False for _ in range(W)] for _ in range(H)]
    q = deque([[sx, sy]])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    maze[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(len(dx)):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny]\
                and maze[nx][ny] == ".":
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
                    q.append([nx, ny])
    dist = -1
    for i in range(H):
        dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x,y))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for i in range(H):
    for j in range(W):
      if S[i][j] == '#':
        continue

      dist = [[-1 for _ in range(W)] for _ in range(H)]
      q = deque()

      def update(pos, num):
        i, j = pos
        if dist[i][j] != -1:
          return
        dist[i][j] = num
        q.append(pos)

      start = (i, j)
      update(start, 0)

      while q:
        qi, qj = q.popleft()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          update((ni, nj), dist[qi][qj]+1)
      ans = max(ans, max(max(x) for x in dist))
    return ans


if __name__ == "__main__":
  print(main())

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import deque
H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[False for _ in range(W)] for _ in range(H)]
    q = deque([[sx, sy]])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    maze[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(len(dx)):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny]\
                and maze[nx][ny] == ".":
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
                    q.append([nx, ny])
    dist = -1
    for i in range(H):
        dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x,y))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for i in range(H):
    for j in range(W):
      if S[i][j] == '#':
        continue

      dist = [[-1 for _ in range(W)] for _ in range(H)]
      q = deque()

      def update(pos, num):
        i, j = pos
        if dist[i][j] != -1:
          return
        dist[i][j] = num
        q.append(pos)

      start = (i, j)
      update(start, 0)

      while q:
        qi, qj = q.pop()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          update((ni, nj), dist[qi][qj]+1)
      ans = max(ans, max(max(x) for x in dist))
    return ans


if __name__ == "__main__":
  print(main())

Submission status: Wrong Answer

Solution code:
import collections

H, W = [int(s) for s in input().split(' ')]

S = list()
for y in range(H):
    row = list(input())
    for x in range(W):
        if row[x] == '.':
            S.append((x, y))

graph = dict()
for s in S:
    graph[s] = list()
    if (s[0] > 0) and ((s[0] - 1, s[1]) in S):
        graph[s].append((s[0] - 1, s[1]))
    if (s[0] < W - 1) and ((s[0] + 1, s[1]) in S):
        graph[s].append((s[0] + 1, s[1]))
    if (s[1] > 0) and ((s[0], s[1] - 1) in S):
        graph[s].append((s[0], s[1] - 1))
    if (s[1] < H - 1) and ((s[0], s[1] + 1) in S):
        graph[s].append((s[0], s[1] + 1))

def max_route(S, graph):
    max_r = 0
    for root in S:
        r = breadth_first_search(graph, root)
        if r > 0 and r > max_r:
            max_r = r
    return max_r

def breadth_first_search(graph, root):
    visited = list()
    queue = collections.deque([root])
    step = 0
    while True:
        next_queue = collections.deque([])
        next_visited = list()
        while queue:
            vertex = queue.popleft()
            for neighbour in graph[vertex]:
                if neighbour not in visited:
                    next_visited.append(neighbour)
                    next_queue.append(neighbour)
        if len(next_queue) > 0:
            step += 1
            queue = next_queue
            visited.extend(next_visited)
            continue
        else:
            break

    return step

mr = max_route(S, graph)
print(mr)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import queue
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for i in range(H):
    for j in range(W):
      dist = [[-1 for _ in range(W)] for _ in range(H)]
      if S[i][j] == '#':
        continue
      start = (i, j)
      q = queue.Queue()

      def update(pos, num):
        i, j = pos
        if dist[i][j] != -1:
          return
        dist[i][j] = num
        q.put(pos)
      update(start, 0)
      while not q.empty():
        qi, qj = q.get()
        for di, dj in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          update((ni, nj), dist[qi][qj]+1)
      ans = max(ans, max(max(x) for x in dist))
    return ans


if __name__ == "__main__":
  print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited = [[False] * w for _ in range(h)]
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z + 1
                        visited[nx][ny] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h, w))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z
                        visited[x, y] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
h,w=map(int,input().split())
meiro = [list(input()) for i in range(h)]
#meiro[y][x]
def bfs(a,b):#縦横,0<a<h-1, 0<b<w-1
    maxdist=0
    da=[1,-1,0,0]
    db=[0,0,1,-1]
    dist=[[-1]*w for i in range(h)]
    dist[a][b]=0
    stack=deque([(a,b)])
    while stack:
        y,x=stack.popleft()
        D=dist[y][x]
        for dy,dx in zip(da,db):
            X=x+dx
            Y=y+dy
            if 0<=Y and Y<=h-1 and X<=w-1 and 0<=X:
                if meiro[Y][X]=='.':
                    if dist[Y][X]==-1:
                        dist[Y][X]=D+1
                        stack.append((Y,X))
                    elif dist[Y][X]>0:
                        dist[Y][X]=min(dist[Y][X],D+1)
                else:
                    dist[Y][X]==-(10**6)
    return dist
saidai=0
for i in range(h):
    for j in range(w):
        saidai=max(saidai,np.array(bfs(i,j)).max())
print(saidai)

Submission status: Wrong Answer

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

from collections import deque

############### TESTCASE ###############
test = ""
#test = \
"""
3 3
...
...
...
ans 4
"""

"""
3 5
...#.
.#.#.
.#...
ans 10
"""

"""
7 7
#######
#.#...#
#...#.#
#...#.#
#.#.#.#
#...#.#
#######
ans 12
"""

########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
################# MAIN ################# 

h, w = map(int, input2().split())
s = ["#" * (w+2)]
s += ["#" + input2() + "#" for _ in range(h)]
s += ["#" * (w+2)]
t = [[0 for _ in range(w+2)] for _ in range(h+2)]

for hi in range(1, h+1):
    for wi in range(1, w+1):
        if s[hi][wi] == ".":
            history = {(hi, wi): 0}
            Q = deque([(hi, wi)])
            
            while Q:
                tmp = Q.popleft()
                next_to = (
                    (tmp[0] + 1, tmp[1]),
                    (tmp[0] - 1, tmp[1]),
                    (tmp[0], tmp[1] + 1),
                    (tmp[0], tmp[1] - 1))
                
                for nex in next_to:
                    form = s[nex[0]][nex[1]]
                    if (form == ".") and (nex not in history):
                        history[nex] = history[tmp] + 1
                        Q.append(nex)
                        
            t[hi][wi] = max(history.values())
        
print(max(max(t)))
#for _ in s:
#    print(_)
#for _ in t:
#    print(_)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]


def calc(sh, sw):
    dist = [[float('inf')] * W for i in range(H)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dist[sh][sw] = 0
    que = deque([[sh, sw]])

    while que:
        sh, sw = que.pop()
        for dh, dw in directions:
            if not ((0 <= sh + dh < H) and (0 <= sw + dw < W)):
                continue

            if G[sh + dh][sw + dw] == '#':
                continue

            if dist[sh + dh][sw + dw] != float('inf'):
                continue

            dist[sh + dh][sw + dw] = dist[sh][sw] + 1
            que.appendleft([sh + dh, sw + dw])

    ret = 0
    for d in dist:
        for w in range(W):
            if d[w] == float('inf'):
                continue
            ret = max(ret, d[w])

    return ret


ans = 0
for sh in range(H):
    for sw in range(W):
        ans = max(ans, calc(sh, sw))

print(ans)

Submission status: Wrong Answer

Solution code:
import collections


def search(data, w, h, start):
    maps = [[0] * w for i in range(h)]
    move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    que = collections.deque([(start[1], start[0])])
    maps[start[1]][start[0]] = 0
    result = 0
    while que:
        y, x = que.popleft()
        num = maps[y][x]
        for m in move:
            if 0 <= y+m[0] < h and 0 <= x+m[1] < w:
                if maps[y+m[0]][x+m[1]] != 0:
                    continue
                if data[y+m[0]][x+m[1]] == '#':
                    continue
                elif data[y+m[0]][x+m[1]] == '.':
                    maps[y+m[0]][x+m[1]] = num+1
                    result = max(result, maps[y+m[0]][x+m[1]])
                    que.append((y+m[0], x+m[1]))
    return result


def main():
    h, w = map(int, input().split())
    data = []
    for i in range(h):
        tmp = input()
        data.append([j for j in tmp])

    ans = 0
    for i in range(h*w-1):
        if data[i//w][i % w] == '.':
            ans = max(search(data, w, h, (i % w, i//w)), ans)
    print(ans)


main()

Submission status: Wrong Answer

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

Glaph = [[float("inf") for i in range(H*W)] for j in range( H*W )]
for i in range(H):
  for j in range(W):
    
    if S[i][j] == ".":
      if i == j:
        Glaph[i*W+j][i*W+j] = 0
      if i-1 != -1 and S[i-1][j] == ".":
        Glaph[i*W+j][(i-1)*W+j] = 1
      if i+1 != H and S[i+1][j] == ".":
        Glaph[i*W+j][(i+1)*W+j] = 1
      if j-1 != -1 and S[i][j-1] == ".":
        Glaph[i*W+j][i*W+(j-1)] = 1
      if j+1 != W and S[i][j+1] == ".":
        Glaph[i*W+j][i*W+(j+1)] = 1
        
def warshall_floyd(n) : # nは頂点数
  for i in range(n):      # 経由する頂点
    for j in range(n):    # 開始頂点
      for k in range(n):  # 終端
        Glaph[j][k] = min(Glaph[j][k], Glaph[j][i] + Glaph[i][k])
        
warshall_floyd(H*W)

ans = 0
for i in range(H*W):
  for j in range(H*W):
    if Glaph[i][j]!=float("inf"):
      ans=max(ans,Glaph[i][j])
      

print(ans)

Submission status: Wrong Answer

Solution code:
#First In First Outのキュー
from collections import deque #dequeを用いる

import copy #参照渡し

#入力
h,w= map(int,input().split())

maze = [list(input()) for _ in range(h)] #訪問先を変更するために、listにする

ans=0

def bfs(sx,sy,c):
  maxlen=0
  que = deque() #キューに要素を追加するときはque.append([i,j])、取り出すときはque.popleft()
  que.append([sx,sy,0]) #初期値

  dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]] # ↓、→、←、↑

  #bfs キューから取り出し、移動先をキューに追加、キューから取り出し、移動先をキューに追加...を繰り返す
  while que: #ゴールに着くまでにキューの要素がなくなったらゴール不可

    x,y,tmp = que.popleft() #キューから要素を取り出す（座標を取り出す）

    for dx,dy in dxy: #(x,y)→(next_x,next_y)の1マス分の移動を考える（上下左右で4パターン存在）

      if 0 <= x+dx < w and 0 <= y+dy < h and c[y+dy][x+dx]=='.': #(移動先は行列内) かつ (空きマスの場合)
        que.append([x+dx,y+dy,tmp+1]) #キューに移動先を追加して、移動先の手数を+1する
        c[y+dy][x+dx] = '@' #訪問済みは@に置換する
        maxlen=max(maxlen,tmp+1)# maxlenを更新
  return maxlen

for Sy in range(h):
  for Sx in range(w):
    Maze=copy.deepcopy(maze)
    if Maze[Sy][Sx]=='.':
      #print(Sy,Sx,Gy,Gx,Maze)
      Tmp=bfs(Sx,Sy,Maze)
      #print(Sy,Sx,Gy,Gx,Maze)
      ans=max(ans,Tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
#First In First Outのキュー
from collections import deque #dequeを用いる

import copy #参照渡し

#入力
h,w= map(int,input().split())

maze = [list(input()) for _ in range(h)] #訪問先を変更するために、listにする

ans=0

def bfs(sx,sy,c):
  maxlen=0
  que = deque() #キューに要素を追加するときはque.append([i,j])、取り出すときはque.popleft()
  que.append([sx,sy,0]) #初期値

  dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]] # ↓、→、←、↑

  #bfs キューから取り出し、移動先をキューに追加、キューから取り出し、移動先をキューに追加...を繰り返す
  while que: #ゴールに着くまでにキューの要素がなくなったらゴール不可

    x,y,tmp = que.popleft() #キューから要素を取り出す（座標を取り出す）

    for dx,dy in dxy: #(x,y)→(next_x,next_y)の1マス分の移動を考える（上下左右で4パターン存在）

      if 0 <= x+dx < w and 0 <= y+dy < h and c[y+dy][x+dx]=='.': #(移動先は行列内) かつ (空きマスの場合)
        que.append([x+dx,y+dy,tmp+1]) #キューに移動先を追加して、移動先の手数を+1する
        c[y+dy][x+dx] = '@' #訪問済みは@に置換する
        maxlen=max(maxlen,tmp+1)# maxlenを更新
  return maxlen

for Sy in range(1,h):
  for Sx in range(1,w):
    Maze=copy.deepcopy(maze)
    if Maze[Sy][Sx]=='.':
      #print(Sy,Sx,Gy,Gx,Maze)
      Tmp=bfs(Sx,Sy,Maze)
      #print(Sy,Sx,Gy,Gx,Maze)
      ans=max(ans,Tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
ans = 0
si, sj = 0, 0

for i in range(h):
    s.append(input())

for x in range(h):
    for y in range(w):
        if s[x][y] == '#':
            continue
        q = deque()
        q.append((0, (x, y)))
        done = set()
        temp = 0

        while q:
            dis, tup = q.popleft()
            i, j = tup[0], tup[1]
            temp = max(temp, dis)

            # Right
            if j < w - 1 and s[i][j + 1] == '.':
                if str(i) + ':' + str(j + 1) not in done:
                    done.add(str(i) + ':' + str(j + 1))
                    q.append((dis + 1, (i, j + 1)))

            # Left
            if j > 0 and s[i][j - 1] == '.':
                if str(i) + ':' + str(j - 1) not in done:
                    done.add(str(i) + ':' + str(j - 1))
                    q.append((dis + 1, (i, j - 1)))

            # Up
            if i > 0 and s[i - 1][j] == '.':
                if str(i - 1) + ':' + str(j) not in done:
                    done.add(str(i - 1) + ':' + str(j))
                    q.append((dis + 1, (i - 1, j)))

            # Down
            if i < h - 1 and s[i + 1][j] == '.':
                if str(i + 1) + ':' + str(j) not in done:
                    done.add(str(i + 1) + ':' + str(j))
                    q.append((dis + 1, (i + 1, j)))

        if temp > ans:
            # print('\nUpdate:', x, y)
            # print('temp, ans:', temp, ans)
            ans = temp
            si, sj = x, y

        # ans = max(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque



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

step=[[1,0],[-1,0],[0,1],[0,-1]]

mx=0
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":continue
        chk=[[False]*W for i in range(H)]
        q=deque([[h,w,0]])
        chk[h][w]=True
        while q:
            y,x,c=q.popleft()
            for dh,dw in step:
                if not (0<=y+dh<H and 0<=x+dw<W):continue
                if S[y+dh][x+dw]=="#":continue
                if chk[y+dh][x+dw]==False:
                    c+=1
                    chk[y+dh][x+dw]=True
                    q.append([y+dh,x+dw,c])
                else:
                    mx=max(mx,c)

print(mx)

Submission status: Wrong Answer

Solution code:

from collections import deque



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

step=[[1,0],[-1,0],[0,1],[0,-1]]

mx=0
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":continue
        chk=[[False]*W for i in range(H)]
        q=deque([[h,w,0]])
        chk[h][w]=True
        while q:
            y,x,c=q.popleft()
            for dh,dw in step:
                if not (0<=y+dh<H):continue
                if not (0<=x+dw<W):continue
                if S[y+dh][x+dw]=="#":continue
                if chk[y+dh][x+dw]==False:
                    c+=1
                    chk[y+dh][x+dw]=True
                    q.append([y+dh,x+dw,c])
                else:
                    mx=max(mx,c)

print(mx)

Submission status: Wrong Answer

Solution code:

from collections import deque



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

step=[[1,0],[-1,0],[0,1],[0,-1]]

mx=0
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":continue
        chk=[[False]*W for i in range(H)]
        q=deque([[h,w,0]])
        chk[h][w]=True
        while q:
            y,x,c=q.popleft()
            for dh,dw in step:
                if y+dh<0 or y+dh>=H:continue
                if x+dw<0 or x+dw>=W:continue
                if S[y+dh][x+dw]=="#":continue
                if chk[y+dh][x+dw]==False:
                    c+=1
                    chk[y+dh][x+dw]=True
                    q.append([y+dh,x+dw,c])
                else:
                    mx=max(mx,c)

print(mx)

Submission status: Wrong Answer

Solution code:

def bfs(start, maze):
    from collections import deque
    visited = {start}
    q = deque([(start, 0)])
    dmax = 0
    while q:
        pos, dist = q.popleft()
        dmax = max(dmax, dist)
        for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx = pos[0] + dx
            ny = pos[1] + dy
            if (nx, ny) not in visited and 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny]==".":
                visited.add((nx, ny))
                q.append(((nx, ny), dist+1))
    return dmax


def main():
    H, W = [int(x) for x in input().split()]
    maze = [input() for _ in range(H)]
    starts = [(x, y) for x in range(H) for y in range(W)]
    ans = 0
    for pos in starts:
        ans = max(ans, bfs(pos, maze))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
h += 2; w += 2
maze = ["#" + input() + "#" for _ in range(h-2)]
guard = "#" * (w)
maze.insert(0, guard)
maze.append(guard)

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
ans = 0

for y in range(h):
    for x in range(w):
        if maze[y][x] == "#":
            continue
        dist = [[0] * w for _ in range(h)]
        visited = [[0] * w for _ in range(h)]
        visited[y][x] = 1
        q = deque([(x, y)])
        while q:
            x, y = q.popleft()
            for dx, dy in dxy:
                nx, ny = x+dx, y+dy
                if maze[ny][nx] == "#":
                    continue
                if visited[ny][nx]:
                    continue
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.append((nx, ny))

print(max(max(d) for d in dist))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
ans = 0
si, sj = 0, 0

for i in range(h):
    s.append(input())

for x in range(h):
    for y in range(w):
        if s[x][y] == '#':
            continue
        q = deque()
        q.append((0, (x, y)))
        done = set()
        temp = 0

        while q:
            dis, tup = q.popleft()
            i, j = tup[0], tup[1]
            # if str(i) + str(j) in done:
            #     continue
            temp = max(temp, dis)


            # Right
            if j < w - 1 and s[i][j + 1] == '.':
                if str(i) + str(j + 1) not in done:
                    done.add(str(i) + str(j + 1))
                    q.append((dis + 1, (i, j + 1)))

            # Left
            if j > 0 and s[i][j - 1] == '.':
                if str(i) + str(j - 1) not in done:
                    done.add(str(i) + str(j - 1))
                    q.append((dis + 1, (i, j - 1)))

            # Up
            if i > 0 and s[i - 1][j] == '.':
                if str(i - 1) + str(j) not in done:
                    done.add(str(i - 1) + str(j))
                    q.append((dis + 1, (i - 1, j)))

            # Down
            if i < h - 1 and s[i + 1][j] == '.':
                if str(i + 1) + str(j) not in done:
                    done.add(str(i + 1) + str(j))
                    q.append((dis + 1, (i + 1, j)))

        if temp > ans:
            ans = temp
            si, sj = x, y

        # ans = max(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:
#First In First Outのキュー
from collections import deque #dequeを用いる

import copy #参照渡し

#入力
h,w= map(int,input().split())

maze = [list(input()) for _ in range(h)] #訪問先を変更するために、listにする

ans=0

def bfs(sx,sy,gx,gy,c):
  
  que = deque() #キューに要素を追加するときはque.append([i,j])、取り出すときはque.popleft()
  que.append([sx,sy,0]) #初期値

  dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]] # ↓、→、←、↑

  #bfs キューから取り出し、移動先をキューに追加、キューから取り出し、移動先をキューに追加...を繰り返す
  while que: #ゴールに着くまでにキューの要素がなくなったらゴール不可

    x,y,tmp = que.popleft() #キューから要素を取り出す（座標を取り出す）

    for dx,dy in dxy: #(x,y)→(next_x,next_y)の1マス分の移動を考える（上下左右で4パターン存在）

      if 0 <= x+dx < w and 0 <= y+dy < h and maze[y+dy][x+dx]=='.': #(移動先は行列内) かつ (空きマスの場合)
        que.append([x+dx,y+dy,tmp+1]) #キューに移動先を追加して、移動先の手数を+1する
        c[y+dy][x+dx] = '#' #訪問済みは壁に置換する
        if x+dx == gx-1 and y+dy == gy-1: #移動先がゴール地点になったら終了                      
          return tmp+1

for Sy in range(1,h):
  for Sx in range(1,w):
    for Gy in range(1,h):
      for Gx in range(1,w):
        Maze=copy.deepcopy(maze)
        if Maze[Sy][Sx]=='.':
          if Maze[Gy][Gx]=='.':
            if Sy!=Gy:
              if Sx!=Gx:
                #print(Sy,Sx,Gy,Gx,Maze)
                Tmp=bfs(Sx,Sy,Gx,Gy,Maze)
                #print(Sy,Sx,Gy,Gx,Maze)
                ans=max(ans,Tmp)
print(ans)