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:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    walls = [[c == '#' for c in s] for s in args[1:]]

    count = 0
    for y in range(h):
        for x in range(w):
            if not walls[y][x]:
                passed = [[False]*w for _ in range(h)]
                Q = deque()
                Q.append((x, y, 0))
                while Q:
                    x, y, c = Q.popleft()
                    if walls[y][x] or passed[y][x]:
                        continue

                    passed[y][x] = True
                    if count < c:
                        count = max(c, count)

                    if 0 < x:
                        Q.append((x-1, y, c+1))
                    if x+1 < w:
                        Q.append((x+1, y, c+1))
                    if 0 < y:
                        Q.append((x, y-1, c+1))
                    if y+1 < h:
                        Q.append((x, y+1, c+1))

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np

H, W = [int(x) for x in input().split()]
maze = np.zeros((H, W))

for i in range(H):
    for j, way in enumerate(input()):
        if way == '.':
            maze[i, j] = 1
        else:
            maze[i, j] = 0

able_list = []

for i in range(H):
    for j in range(W):
        able = []
        if maze[i,j] == 1:
            if 0 <= i-1 < H:
                if maze[i, j] == 1:
                    able.append([(i-1) * W + j, 1])
            if 0 <= j-1 < W:
                if maze[i, j-1] == 1:
                    able.append([i * W + j - 1, 1])
            if 0 <= j+1 < W:
                if maze[i, j+1] == 1:
                    able.append([i* W + j + 1, 1])
            if 0 <= i+1 < H:
                if maze[i+1, j] == 1:
                    able.append([(i+1)*W + j, 1])
        able_list.append(able)



def Dijkstra(list_adjlist, initnode):
    # list_Dを初期化
    list_D = [-1] * len(list_adjlist)
    # 始点の距離=0
    list_D[initnode] = 0
    # list_Tを初期化
    list_T = [-1] * len(list_adjlist)
    # 最短経路・距離が確定している点のリスト
    list_check = [False] * len(list_adjlist)
    # ヒープの初期化：暫定最短距離と点の名前をペアにしたリストをヒープに格納する
    list_S = []
    heapq.heappush(list_S, (list_D[initnode], initnode))
    # ヒープが空になるまで続ける
    while(len(list_S)):
        # ヒープから暫定最短距離が小さい点を取り出す
        pair_w_node = heapq.heappop(list_S)
        if list_check[pair_w_node[1]] is False:
            list_check[pair_w_node[1]] = True
            # 点pair_w_node[1]の各隣接点について調べる
            for neighbor in list_adjlist[pair_w_node[1]]:
                if list_D[neighbor[0]] == -1 or list_D[neighbor[0]] > list_D[pair_w_node[1]] + neighbor[1]:
                    list_D[neighbor[0]] = list_D[pair_w_node[1]] + neighbor[1]
                    list_T[neighbor[0]] = pair_w_node[1]
                    heapq.heappush(list_S, (list_D[neighbor[0]], neighbor[0]))
    return list_D, list_T

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i, j] == 1:
            list_D, list_T = Dijkstra(able_list, i*W + j)
            if ans < max(list_D):
                ans = max(list_D)
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from collections import deque

# 最短にする
# 0回以上でたどり着けるのでスタート=ゴールのことがある ふざけんな
h, w = map(int, input().split())
table = [[] for _ in range(h)]
for i in range(h):
    table[i] = list(input())


def bfs(y, x, t):
    steps = [0, 1, 0, -1, 0]
    queue = deque([[y, x]])
    arr = []
    while len(queue) > 0:
        cur_y, cur_x = queue.popleft()
        for i in range(4):
            next_y, next_x = cur_y + steps[i], cur_x + steps[i + 1]
            if 0 <= next_y < h and 0 <= next_x < w:
                if t[next_y][next_x] == "G":
                    arr.append(t[cur_y][cur_x])
                    continue
                if t[next_y][next_x] == ".":
                    t[next_y][next_x] = t[cur_y][cur_x] + 1
                    queue.append([next_y, next_x])

    return 0 if len(arr) == 0 else min(arr) + 1


ans = 0
for sy in range(h):
    for sx in range(w):
        # table[sy][sx]をスタート地点とする
        if table[sy][sx] != ".":
            continue
        for gy in range(sy, h):
            for gx in range(sx, w):
                if sy == gy and sx == gx:
                    continue
                if table[gy][gx] == ".":
                    mytable = deepcopy(table)
                    mytable[sy][sx] = 0
                    mytable[gy][gx] = "G"
                    # ans = min(ans, bfs(sy, sx, mytable))
                    ret = bfs(sy, sx, mytable)
                    ans = max(ans, ret)

print(ans)

Submission status: Wrong Answer

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

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

ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        start = (i, j)
        d = [[1<<10 for x in range(w)] for y in range(h)]

        stack = []
        stack.append((start[0], start[1]))
        d[start[0]][start[1]] = 0
        ma = 0
        while stack:
            y, x = stack.pop()
            if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                d[y-1][x] = d[y][x] + 1
                stack.append((y-1, x))
            if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                d[y][x+1] = d[y][x] + 1
                stack.append((y, x+1))
            if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                d[y+1][x] = d[y][x] + 1
                stack.append((y+1, x))
            if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                d[y][x-1] = d[y][x] + 1
                stack.append((y, x-1))
            if d[y][x] > ma:
                ma = d[y][x]
        ans.append(ma)
ans.sort()
print(ans[-1])

Submission status: Wrong Answer

Solution code:
def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    for start_i in range(len(points) - 1):
        for goal_i in range(start_i + 1, len(points)):
            max_step = max(max_step, count_step(MAP, points[start_i], points[goal_i]))

    print(max_step)


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


def count_step(MAP, start, goal):
    candidates = [(start, get_distance(start, goal), 0)]

    checked = {}
    while True:
        pos, _, step = candidates.pop(0)
        for m in MOVES:
            next_pos = (pos[0] + m[0], pos[1] + m[1])
            if next_pos in checked:
                continue
            if not is_valid(MAP, next_pos):
                continue
            checked[next_pos] = True
            distance = get_distance(next_pos, goal)
            if distance == 0:
                return step + 1
            candidates.append((next_pos, distance, step + 1))
        candidates.sort(key=lambda x: x[1] * 1.5 + x[2])


def get_distance(p, goal):
    return abs(p[0] - goal[0]) + abs(p[1] - goal[1])


def is_valid(MAP, pos):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= len(MAP) or pos[1] >= len(MAP[0]):
        return False

    if MAP[pos[0]][pos[1]] == '#':
        return False
    return True


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
INF = 1000
drc = [(-1, 0), (1, 0), (0, 1), (0, -1)]
def calc(sr, sc):
    dist = [[-1] * W for _ in range(H)]
    dist[sr][sc] = 0
    que = collections.deque()
    que.append((sr, sc))
    while len(que):
        r, c = que.popleft()
        for dr, dc in drc:
            nr, nc = r + dr, c + dc
            if nr < 0 or H <= nr or nc < 0 or W <= nc:
                continue
            if board[nr][nc] == 1 or dist[nr][nc] >= 0:
                continue
            dist[nr][nc] = dist[r][c] + 1
            que.append((nr, nc))
    return max(max(row for row in dist))



H, W = map(int, input().split())
board = [[int(x == "#") for x in input()] for _ in range(H)]
ans = 0
for r in range(H):
    for c in range(W):
        if board[r][c] == 0:
            ans = max(ans, calc(r, c))
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import itertools
r,c=map(int,input().split())
s=[list(input()) for i in range(r)]
ans=0
for i1 in range(r):
    for i2 in range(c):
        p=0
        a=[[s[j][i] for i in range(c)] for j in range(r)]
        sy,sx=i1,i2
        if a[sy][sx]=="#":
            break
                #print(sy,sx,gy,gx)
        q = queue.Queue()
        d=[(-1,0),(1,0),(0,-1),(0,1)]
        a[sy][sx]=0
        for i in d:
            if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
                a[sy+i[0]][sx+i[1]]=1
                q.put((sy+i[0],sx+i[1]))
        while not q.empty():
            y,x=q.get()
            for i in d:
                if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                    a[y+i[0]][x+i[1]]=a[y][x]+1
                    q.put((y+i[0],x+i[1]))
        for i in range(r):
            for j in range(c):
                if type(a[i][j])==int:
                    p=max(p,a[i][j])
        ans=max(p,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools
h,w=map(int,input().split())
s=["#"+input()+"#" for i in range(h)]
s.insert(0,'#'*(w+2))
s.append('#'*(w+2))
def dep(s,t,p,q,time):
    print(s)
    s[p][q]=min(time,s[p][q])
    time+=1
    if t[p+1][q]=="." :
        dep(s,t,p+1,q,time)
    if t[p-1][q]=="." :
        dep(s,t,p-1,q,time)
    if t[p][q+1]=="." :
        dep(s,t,p,q+1,time)
    if t[p][q-1]=="." :
        dep(s,t,p,q-1,time)
    return max(itertools.chain.from_iterable(s))

m=0
for i in range(h):
    for j in range(w):
        if s[i+1][j+1]=='.':
            t=[[-1 for l in range(w+2)] for l2 in range(h+2)]
            time=0
            q1=deque([])
            t[i+1][j+1]=time
            q1.appendleft([i+1,j+1])
            while len(q1)!=0:
                q=q1.pop()
                time=t[q[0]][q[1]]+1
                if s[q[0]+1][q[1]]=='.' and t[q[0]][q[1]]==-1:
                    t[q[0]+1][q[1]]=time
                    q1.appendleft([q[0]+1,q[1]])
                if s[q[0] - 1][q[1]] == '.' and t[q[0]-1][q[1]] == -1:
                    t[q[0] - 1][q[1]] = time
                    q1.appendleft([q[0] - 1, q[1]])
                if s[q[0]][q[1]+1] == '.' and t[q[0]][q[1]+1] == -1:
                    t[q[0] ][q[1]+1] = time
                    q1.appendleft([q[0] , q[1]+1])
                if s[q[0]][q[1]-1] == '.' and t[q[0]][q[1]-1] == -1:
                    t[q[0] ][q[1]-1] = time
                    q1.appendleft([q[0], q[1]-1])
            m=max(max(itertools.chain.from_iterable(t)),m)
print(m)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
square = []
for i in range(H):
    squaread = ['#']
    squaread+=(list(input()))
    squaread+=('#')
    square.append(squaread)
ad_square = [['#' for i in range(W+2)]]
ad_square += square
ad_square += [['#' for i in range(W+2)]]
numbersquare =[]
for i in range(H):
    numbersquare.append([0 for j in range(W)])
for i in range(H):
    i2 = i+1
    for j in range(W):
        j2 = j+1
        around = 0
        if ad_square[i2][j2]=='#':
            pass
        else:
            if ad_square[i2][j2-1]=='#':
                around += 1
            if ad_square[i2][j2+1]=='#':
                around += 1
            if ad_square[i2-1][j2]=='#':
                around += 1
            if ad_square[i2+1][j2]=='#':
                around += 1
            numbersquare[i2-1][j2-1] = around
number1 = 0
number2 =0
number3 =0
for i in range(len(numbersquare)):
    number2+=numbersquare[i].count(2)
    number3+=numbersquare[i].count(3)
print(sum([number2,number3]))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
field = [list(input())for i in range(h)]
a= [[10**4]*w for i in range(h)]

vec = [(-1,0),(1,0),(0,1),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        stack = [(i,j)]
        visited = [[0]*w for i in range(h)]
        a[i][j] = 0
        
        while stack:
            next = []
            for x,y in stack:
                
                if visited[x][y]:continue

                visited[x][y] = 1
                

                for tx,ty in vec:
                    nx = x+tx
                    ny = y+ty
                    if nx < 0 or ny <0 or nx >=h or ny >=w:continue
                    if field[nx][ny] == "#" :continue
                    if visited[nx][ny]:continue
                    next.append((nx,ny))
                    a[nx][ny] = min(a[x][y] + 1,a[nx][ny])
                    
                    
            stack = next
   
        for i in range(h):
            for j in range(w):
                if a[i][j] != 10**4:
                    ans = max(ans,a[i][j])
                a[i][j] = 10**4
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
def check(s,t):
    if (0 <= s <= w - 1) and (0 <= t <= h - 1):
        return True
    else:
        return False
def bfs(x, y, cost):
    if check(x,y):
        if grid[y][x] != "#":
            if cost < graph[y][x]:
                graph[y][x] = cost
                bfs(x+1,y,cost+1)
                bfs(x,y+1,cost+1)
                bfs(x-1,y,cost+1)
                bfs(x,y-1,cost+1)
ans = 1
inf = 70
for i in range(h):
    for j in range(w):
        graph = [[inf for _ in range(w)] for l in range(h)]
        bfs(j,i,0)
        g_max = 0
        for p in range(h):
            for q in range(w):
                if graph[p][q] != inf:
                    g_max = max(g_max, graph[p][q])
        ans = max(g_max, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

H,W=two_int()

maps = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    S = one_str()
    for index,j in enumerate(S):
        if j =="#":
            maps[i][index] = 1

import copy 

def dfs(pos, old_pos, root):
    # 停止条件
    # 深さに限らず，任意の停止条件を書く
    x,y = pos[0],pos[1]
    pos_str = str(pos[0])+"_"+str(pos[1])

    if  maps[y][x]==1:
        return 0, pos
    if pos_str in root:
        return len(root)-1, old_pos
    root[pos_str] = 1

    ret1,ret2,ret3,ret4 = 0,0,0,0
    if x >= 1:
        ret1,pos1 = dfs([x-1, y], pos, copy.deepcopy(root))
    
    if x < W-1:
        ret2,pos2 = dfs([x+1, y], pos, copy.deepcopy(root))

    if y >= 1:
        ret3,pos3 = dfs([x, y-1], pos, copy.deepcopy(root))

    if y < H-1:
        ret4,pos4 = dfs([x, y+1], pos, copy.deepcopy(root))

    temp = max(ret1, ret2, ret3, ret4)
    if temp==ret1:
        return ret1,pos1
    if temp==ret2:
        return ret2,pos2
    if temp==ret3:
        return ret3,pos3
    if temp==ret4:
        return ret4,pos4
    


def dfs2(pos, root, goal):
    # 停止条件
    # 深さに限らず，任意の停止条件を書く
    x,y = pos[0],pos[1]
    pos_str = str(pos[0])+"_"+str(pos[1])

    if pos_str in root or maps[y][x]==1:
        return 1000
    
    if pos_str==goal_str:
        return len(root)

        
    root[pos_str] = 1

    ret1,ret2,ret3,ret4 = 1000,1000,1000,1000
    if x >= 1:
        ret1 = dfs2([x-1, y], copy.deepcopy(root),goal_str)
    
    if x < W-1:
        ret2 = dfs2([x+1, y], copy.deepcopy(root),goal_str)

    if y >= 1:
        ret3 = dfs2([x, y-1], copy.deepcopy(root),goal_str)

    if y < H-1:
        ret4 = dfs2([x, y+1], copy.deepcopy(root),goal_str)

    return min(ret1, ret2, ret3, ret4)



#start位置探索
for y in range(H):
    for x in range(W):
        if maps[y][x]==0:
            break

# max(dfs([0,0],{}), dfs([0,H-1],{}), dfs([W-1,0],{}), dfs([W-1,H-1],{}))

pos,goal= dfs([x,y], [0,0],{})

goal_str = str(goal[0])+"_"+str(goal[1])

print(dfs2([x,y], {}, goal_str))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    walls = [[c == '#' for c in s] for s in args[1:]]

    head = None
    tail = None

    for y in range(h):
        for x in range(w):
            if not walls[y][x]:
                head = (x, y)
                cur, prev, count = 0, -1, 0
                while cur != prev:
                    passed = [[False]*w for _ in range(h)]
                    Q = deque([head+(0,)])
                    prev = cur
                    while Q:
                        x, y, c = Q.popleft()
                        if walls[y][x] or passed[y][x]:
                            continue

                        passed[y][x] = True
                        if count < c:
                            count = max(c, count)
                            tail = (x, y)

                        if 0 < x:
                            Q.append((x-1, y, c+1))
                        if x+1 < w:
                            Q.append((x+1, y, c+1))
                        if 0 < y:
                            Q.append((x, y-1, c+1))
                        if y+1 < h:
                            Q.append((x, y+1, c+1))
                    cur = count
                    head = tail

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve(S, s):
    if S[s[0]][s[1]] != ".":
        return -1
    queue = deque([s])
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[s[0]][s[1]] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if new_x in range(W) and new_y in range(H) and S[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
#    for v in visited:
#        print(v)
    return max(max(visited))


H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        ans = max(ans, solve(S, [i, l]))
print(ans)

Submission status: Wrong Answer

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

LOAD = '.'
WALL = '#'
NOT_REACHED = -1

h, w = [int(i) for i in input().split()]

s = [0] * h
for i in range(h):
    s[i] = input().strip()

def bfs(graph, queue, div):
    _max = 0
    while queue:
        current = queue.pop(0)

        top = (current[0] - 1, current[1])
        bottom = (current[0] + 1, current[1])
        left = (current[0], current[1] - 1)
        right = (current[0], current[1] + 1)

        for target in (top, bottom, left, right):
            if (target[0] < 0) or (target[0] >= h) or (target[1] < 0) or (target[1] >= w):
                continue
            if div[target] != NOT_REACHED:
                continue
            if graph[target[0]][target[1]] == LOAD:
                div[target] = div[current] + 1
                _max = max(div[target], _max)
                queue.append(target)
    return _max

ans = 0
for i in range(h):
    for j in range(w):
        queue = [(i, j)]
        div = {}
        for inner_i in range(h):
            for inner_j in range(w):
                div[(inner_i, inner_j)] = -1
        div[(i, j)] = 0
        ans = max(bfs(s, queue, div), ans)

if ans <= 0:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(39)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

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

def clear_maze(sx, sy, maze):

    INF = 0

    field_y_length = len(maze)
    field_x_length = len(maze[0])
    distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]

    def bfs():
        queue = []

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

        distance[sy][sx] = 0

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

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < field_y_length and 0 <= ny and ny < field_x_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
        return max(distance)

    return bfs()

ans = [0 for i in range(h*w)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            sx = j
            sy = i
            ans[i*w+j]=clear_maze(sx,sy,maze)
temp = 0
t1 = 0
for i in ans:
    if i!=0:
        temp = max(i)
        t1 = max(temp,t1)
print(t1)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
square = []
for i in range(H):
    squaread = ['#']
    squaread+=(list(input()))
    squaread+=('#')
    square.append(squaread)
ad_square = [['#' for i in range(W+2)]]
ad_square += square
ad_square += [['#' for i in range(W+2)]]
numbersquare =[]
for i in range(H):
    numbersquare.append([0 for j in range(W)])
for i in range(H):
    i2 = i+1
    for j in range(W):
        j2 = j+1
        around = 0
        if ad_square[i2][j2]=='#':
            pass
        else:
            if ad_square[i2][j2-1]=='#':
                around += 1
            if ad_square[i2][j2+1]=='#':
                around += 1
            if ad_square[i2-1][j2]=='#':
                around += 1
            if ad_square[i2+1][j2]=='#':
                around += 1
            numbersquare[i2-1][j2-1] = around
number1 = 0
number2 =0
number3 =0
for i in range(len(numbersquare)):
    number1+=numbersquare[i].count(1)//2
    number2+=numbersquare[i].count(2)
    number3+=numbersquare[i].count(3)
print(sum([number1,number2,number3])-1)

Submission status: Wrong Answer

Solution code:
import collections
INF = 1000
drc = [(-1, 0), (1, 0), (0, 1), (0, -1)]
def calc(sr, sc):
    dist = [[-1] * W for _ in range(H)]
    dist[sr][sc] = 0
    que = collections.deque()
    que.append((sr, sc))
    while len(que):
        r, c = que.popleft()
        for dr, dc in drc:
            nr, nc = r + dr, c + dc
            if nr < 0 or H <= nr or nc < 0 or W <= nc:
                continue
            if board[nr][nc] == 1 or dist[nr][nc] >= 0:
                continue
            dist[nr][nc] = dist[r][c] + 1
            que.append((nr, nc))
    return max(max(row for row in dist))



H, W = map(int, input().split())
board = [[int(x == "#") for x in input()] for _ in range(H)]
ans = 0
for r in range(H):
    for c in range(W):
        ans = max(ans, calc(r, c))
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import itertools
r,c=map(int,input().split())
s=[list(input()) for i in range(r)]
ans=0
for i1 in range(r):
    for i2 in range(c):
        p=0
        a=[[s[j][i] for i in range(c)] for j in range(r)]
        sy,sx=i1,i2
        if a[sy][sx]=="#":
            break
                #print(sy,sx,gy,gx)
        q = queue.Queue()
        d=[(-1,0),(1,0),(0,-1),(0,1)]
        a[sy][sx]=0
        for i in d:
            if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
                a[sy+i[0]][sx+i[1]]=1
                q.put((sy+i[0],sx+i[1]))
        while not q.empty():
            y,x=q.get()
            for i in d:
                if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                    a[y+i[0]][x+i[1]]=a[y][x]+1
                    p=a[y][x]+1
                    q.put((y+i[0],x+i[1]))
        ans=max(p,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
def calc_distance(maze,sx,sy,gx,gy):
        # mazeをリストに変換
        # Goalまでの距離としてはあり得ない数値を設定
        INF = 100000000

        field_x_length = len(maze[0])
        field_y_length = len(maze)

        # mazeと同じ配列構造ですべての箇所がINFで埋まっている二次元配列を作る
        # startからの距離をこのdistance配列に格納していく
        distance = []
        for i in range(field_y_length):
            distance.append([])
            for j in range(field_x_length):
                distance[i].append(INF)

        # queue配列を作り、ここに座標を格納する
        queue = []

        # queueの末尾にStart座標を入れる
        queue.insert(0, (sy, sx))

        # Startの座標距離は0に設定
        distance[sy][sx] = 0

        # Goalにつくまで以下ループ
        while True:
            # 最初に入れた要素を取り出す
            y, x = queue.pop()

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

            # 新しい座標(ny, nx)に現時点の座標から
            # (0, 1)(1, 0)(0, -1)(-1, 0)移動した値を代入  
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                # 移動先ny, nxが迷路の範囲内
                # かつ壁（maze配列が#）でなく、
                # かつ未到達（distance配列がINF）であるときに
                # 現時点の距離+1をdistance配列に格納する
                # 現時点の座標をqueue配列に格納する（再ループの時にその座標から始める）
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1

        # Goalについたらループを抜け、Goalまでの距離を返す
        return distance[gy][gx]
    
ans = 0
for i in range(H//2+1):
    sy = i
    for j in range(W//2+1):
        sx = j
        for k in range(H//2+1,H):
            gy = k
            for m in range(W//2+1,W):
                gx = m
        
            
                if maze[sy][sx] == "#" or maze[gy][gx] == "#" or ((sy == gy) and (gx == sx)):
                    pass
                else:
                    
                    score = calc_distance(maze,sx,sy,gx,gy)
                    ans = max(ans,score)
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import itertools
r,c=map(int,input().split())
s=[list(input()) for i in range(r)]
ans=0
for i1 in range(r):
    for i2 in range(c):
        p=0
        a=[[s[j][i] for i in range(c)] for j in range(r)]
        sy,sx=i1,i2
        if a[sy][sx]=="#":
            break
                #print(sy,sx,gy,gx)
        q = queue.Queue()
        d=[(-1,0),(1,0),(0,-1),(0,1)]
        a[sy][sx]=0
        for i in d:
            if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
                a[sy+i[0]][sx+i[1]]=1
                q.put((sy+i[0],sx+i[1]))
        while not q.empty():
            y,x=q.get()
            for i in d:
                if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                    a[y+i[0]][x+i[1]]=a[y][x]+1
                    p=a[y][x]+1
                    q.put((y+i[0],x+i[1]))
                ans=max(p,ans)
print(ans)