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:
#!/usr/bin/env python3
import copy
import numpy as np

def getmax(H2, W2, S):
    lp=True
    st=0
    while lp:
        lp=False
        for i in range(1,H2-1):
            for j in range(1,W2-1):
                if S[i][j]==0:
                    if (S[i-1][j]<1 and
                        S[i][j-1]<1 and
                        S[i+1][j]<1 and
                        S[i][j+1]<1):
                        continue
                    S[i][j]=max(S[i-1][j],S[i][j-1],S[i+1][j],S[i][j+1])+1
                    lp=True
    maxS=np.max(S)
    n=0
    p=[]
    for i in range(1,H2-1):
        for j in range(1,W2-1):
            if S[i][j]==maxS:
                n+=1
                p.append((i,j))

    return(maxS, n, p)

def solve(H2, W2, S):
    T=copy.deepcopy(S)
    #try1
    lp=True
    while lp:
        for i in range(1,H2-1):
            for j in range(1,W2-1):
                if S[i][j]==0:
                    S[i][j]=1
                    lp=False
                if not lp:
                    break
            if not lp:
                break

    maxS, n, p=getmax(H2, W2, S)

    ans=0
    #print("#",maxS, n, p)
    for k in range(n):
        S=copy.deepcopy(T)
        S[p[k][0]][p[k][1]]=1
        maxS, _, _=getmax(H2, W2, S)
        ans=max(maxS, ans)

    #while True:
    print(ans-1)
    return

def main():
    H, W = map(int, input().split())
    SS=[[-1 for _ in range(W+2)] for _ in range(H+2)]
    S=[]
    for _ in range(H):
        S.append(list(input()))
    for i in range(H):
        for j in range(W):
            SS[i+1][j+1]=0 if S[i][j]=="." else -1
    solve(H+2, W+2, SS)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

H,W = map(int,input().split(' '))
MAP = [None]*H
for i in range(H):
    MAP[i] = list(input())




ANS = 0
for i in range(H):
    for j in range(W):
        st = MAP[i][j]
        if st=='.':
            VISITED = [None]*H
            MAX = [0]
            for m in range(H):
                VISITED[m] = [False for _ in range(W)]

            cnt_MAP = [None]*H

            for m in range(H):
                cnt_MAP[m] = [0 for _ in range(W)]

            def dfs(h,w,cnt,v):
                if (not (0<=h<H)) or (not (0<=w<W)):
                    return
                if MAP[h][w]=='#':
                    return

                cnt += 1

                if cnt_MAP[h][w]==0 or cnt_MAP[h][w]>cnt:
                    cnt_MAP[h][w] = cnt
                else:
                    return

                dfs(h+1,w,cnt,v)
                dfs(h-1,w,cnt,v)
                dfs(h,w+1,cnt,v)
                dfs(h,w-1,cnt,v)

            dfs(i,j,-1,VISITED)
            tmp = 0
            for i in range(H):
                tmp = max(tmp,max(cnt_MAP[i]))
            ANS = max(ANS,tmp)

print(ANS)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
from itertools import groupby, permutations, combinations
from fractions import gcd
import numpy as np
from sys import stdin, stderr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def movement_max(start_h, start_w, maze):
    H, W = len(maze), len(maze[0])
    score = []
    unvisited = set()
    visited = set()
    unvisited.add(start_h + start_w*100)
    for h in range(H):
        score.append([1000] * W)
        for w in range(W):
            if maze[h][w] == "#":
                visited.add(h + w*100)
    score[start_h][start_w] = 0
    ret = 0
    while len(unvisited) > 0:
        hw = unvisited.pop()
        h = hw % 100
        w = hw // 100
        visited.add(hw)
        if maze[h][w] == "#":
            continue
        s = score[h][w] + 1
        ret = max(ret, score[h][w])
        if h > 0:
            score[h-1][w] = min(s, score[h-1][w])
            if (h-1 + w*100) not in visited:
                unvisited.add(h-1 + w*100)
        if h < H - 1:
            score[h+1][w] = min(s, score[h+1][w])
            if (h+1 + w*100) not in visited:
                unvisited.add(h+1 + w*100)
        if w > 0:
            score[h][w-1] = min(s, score[h][w-1])
            if (h + (w-1)*100) not in visited:
                unvisited.add(h + (w-1)*100)
        if w < W - 1:
            score[h][w+1] = min(s, score[h][w+1])
            if (h + (w+1)*100) not in visited:
                unvisited.add(h + (w+1)*100)
    return ret


def main():
    H, W = [int(x) for x in input().split()]
    maze = [""] * H
    score = []
    for i in range(H):
        maze[i] = input()
        score.append([-1] * W)
    result = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            score[h][w] = movement_max(h, w, maze)
            result = max(result, movement_max(h, w, maze))
            # print(result)
        # print(score[h])
    return result


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

Submission status: Wrong Answer

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

def clear_maze(sx, sy, gx, gy, maze):
    INF = float('infinity')
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]

    def bfs():
        queue = deque([])
        queue.append((sx, sy))
        distance[sx][sy] = 0
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        while queue:
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]
                if (0 <= nx < field_x_length) and (0 <= ny < field_y_length):
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.appendleft((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1
        return distance[gx][gy]
    return bfs()


pairs = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            pairs.append([i, j])

MAX = 0
for i in range(len(pairs)):
    sx, sy = pairs[i]
    gx, gy = pairs[len(pairs) - i - 1]
    r = clear_maze(sx, sy, gx, gy, maze)
    MAX = max(MAX, r)
print(MAX)

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, root):
    # 停止条件
    # 深さに限らず，任意の停止条件を書く
    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 len(root)-1, pos
    root[pos_str] = 1

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

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

    if y < H-1:
        ret4,pos4 = dfs([x, y+1], 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],{}))

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

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

print(dfs2([0,H-1], {}, goal_str))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s_list = [input().split() for _ in range(h)]
wall_count = sum([s[0].count('#') for s in s_list])
max_route = (h-1 + w-1) + wall_count
print(max_route)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

h, w = map(int, input().split())
square = []

for i in range(h):
  _s = input()
  for j in range(w):
    if _s[j] == ".":
      square.append((i, j))

squares = len(square)
d = [[float("inf") for i in range(squares)] for j in range(squares)]

for i in range(squares):
  d[i][i] = 0

for i in range(squares - 1):
  for j in range(i + 1, squares):
    a_x, a_y = square[i]
    b_x, b_y = square[j]
    if (a_x == b_x and abs(a_y - b_y) == 1) or (a_y == b_y and abs(a_x - b_x) == 1):
      d[i][j] = d[j][i] = 1

d = warshall_floyd(d, squares)
print(max(max(d)))

Submission status: Wrong Answer

Solution code:
import copy

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

def solve(sx,sy):
	flg = copy.deepcopy(flg_orig)
	flg[sx][sy] = 0
	q = [[sx,sy]]
	cnt = 0
	while q != []:
		cx, cy = q.pop(0)
		cd = flg[cx][cy]
		nps = [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]
		for nx,ny in nps:
			if not (0 <= nx < H and 0 <= ny < W):
				continue
			if flg[nx][ny] == "#":
				continue
			if flg[nx][ny] <= cd+1:
				continue
			else:
				flg[nx][ny] = cd + 1

			q.append([nx,ny])

	cnt = 0
	for i in range(H):
		for j in range(W):
			if flg[i][j] == "#":
				continue
			else:
				cnt = max(cnt,flg[i][j])

	return cnt

INF = float("inf")
flg_orig = [[INF for _ in range(W)] for _ in range(H)]
for i in range(H):
	for j in range(W):
		if S[i][j] == "#":
			flg_orig[i][j] = "#"


ans = 0
for start_x in range(H):
	for start_y in range(W):
		tmp_cnt = solve(start_x, start_y)
		ans = max(ans, tmp_cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue
import itertools
def solve():

    H, W = map(int, input().split())
    S = []
    for i in range(H):
        tmp = list(input())
        S.append(tmp)
    
    dw = (1,0,-1,0)
    dh = (0,1,0,-1)

    comb = itertools.combinations(tuple(range(200)), 2)
    mx = 0

    for c in comb:
        
        startH = c[0]
        startW = c[1]
        if startH >= H or startW >= W or S[startH][startW] == '#':
            continue

        q = Queue()
        cur = P(startH, startW)
        q.put(cur)

        time = [[float('inf')] * W for i in range(H)]
        time[startH][startW] = 0

        while not q.empty():
            p = q.get()
            
            for i in range(4):
                nh = p.H + dh[i]
                nw = p.W + dw[i] 
                if 0 <= nh and nh < H and 0 <= nw and nw < W and time[nh][nw] == float('inf') and S[nh][nw] != '#':
                    q.put(P(nh, nw))
                    time[nh][nw] = time[p.H][p.W] + 1
        
        flatten = list(itertools.chain.from_iterable(time))
        for i in range(len(flatten)):
            if flatten[i] == float('inf'):
                flatten[i] = 0 

        localmx = max(flatten)
        mx = max(localmx, mx)

    print(mx)

class P():
    def __init__(self, H, W):
        self.H = H
        self.W = W

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
from collections import deque
def bfs():
    cnt = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while len(Q) > 0:
        q = Q.popleft()
        y,x =  q[0], q[1]
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "#" and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = -1
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "." and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = box[y][x] + 1
                Q.append([ny,nx])
    for i in range(H):
        if len(box[i]) == 0:
            continue
        else:
            ans.append(max(box[i]))
    return


H,W = map(int,input().split())
S = [ []for _ in range(H)]
for i in range(H):
    S[i] = list(input())
ans = []
INF = 50**2
Q = deque()
for i in range(H):
    for j in range(W):
        #各マス目に到達するために必要な移動回数
        box = [[0 for _ in range(W)] for __ in range(H)]
        Q.append([i,j])
        bfs()
if len(ans)==0:
    print(0)
    exit()
print(max(ans))

Submission status: Wrong Answer

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

def clear_maze(sx, sy, gx, gy, maze):
    INF = float('infinity')
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]

    def bfs():
        queue = deque([])
        queue.append((sx, sy))
        distance[sx][sy] = 0
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        while queue:
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]
                if (0 <= nx < field_x_length) and (0 <= ny < field_y_length):
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.appendleft((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1
        return distance[gx][gy]
    return bfs()


pairs = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            pairs.append([i, j])

MAX = 0
for i in range(len(pairs)// 2):
    sx, sy = pairs[i]
    gx, gy = pairs[len(pairs) - i - 1]
    r = clear_maze(sx, sy, gx, gy, maze)
    MAX = max(MAX, r)
print(MAX)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy


def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    h,w=map(int,input().split())
    s=[input() for i in range(h)]
    for i in range(h):
        s[i]=list(s[i])
    for i in range(h):
        for j in range(w):
            if s[i][j]==".":
                s[i][j]=1000
            else:
                s[i][j]=9999
 #   print(s)
    start=[0,0]
    for i in range(h):
        start[1]=s[i].index(min(s[i]))
        if min(s[i]) >= 1111:
            continue
        else:
            start[0]=i
            break
 #   print(start)
    s[start[0]][start[1]]=0

    for kk in range(2000):

        for i in range(h):
            for j in range(w):
                if s[i][j]>1000:
                    continue
                if i+1<h:
                    if s[i][j]>s[i+1][j] and s[i+1][j]<1000:
                            s[i][j]=s[i+1][j]+1
                if i-1>=0:
                    if s[i][j] > s[i - 1][j] and s[i - 1][j] < 1000:
                            s[i][j] = s[i - 1][j] + 1
                if j+1<w:
                    if s[i][j] > s[i][j+1] and s[i][j+1] < 1000:
                            s[i][j] = s[i][j+1] + 1
                if j-1>=0:
                    if s[i][j] > s[i][j - 1] and s[i][j - 1] < 1000:
                            s[i][j] = s[i][j - 1] + 1

 #   print(s)

    temp=[0,0]
    tempm=0
    for i in range(h):
        for j in range(w):
            if s[i][j]>tempm and s[i][j]<9999:
                tempm=s[i][j]
                temp=[i,j]
            if s[i][j]<9999:
                s[i][j]=1000
    start=[temp[0],temp[1]]
    s[start[0]][start[1]]=0

    for kk in range(2000):

        for i in range(h):
            for j in range(w):
                if s[i][j]>1000:
                    continue
                if i+1<h:
                    if s[i][j]>s[i+1][j] and s[i+1][j]<1000:
                            s[i][j]=s[i+1][j]+1
                if i-1>=0:
                    if s[i][j] > s[i - 1][j] and s[i - 1][j] < 1000:
                            s[i][j] = s[i - 1][j] + 1
                if j+1<w:
                    if s[i][j] > s[i][j+1] and s[i][j+1] < 1000:
                            s[i][j] = s[i][j+1] + 1
                if j-1>=0:
                    if s[i][j] > s[i][j - 1] and s[i][j - 1] < 1000:
                            s[i][j] = s[i][j - 1] + 1

#    print(s)
#    for i in range(h):
#        print(s[i])

    temp = [0, 0]
    tempm = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] > tempm and s[i][j] < 9999:
                tempm = s[i][j]
                temp = [i, j]
            if s[i][j] < 9999:
                s[i][j] = 1000

    print(tempm)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from array import array

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

nodes = h*w

g = []

for i in range(nodes):
    g.append(array('l', [10000000] * (w * h)))

for i in range(nodes):
    g[i][i] = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            continue
        if maze[i][j] == '.':
            if i > 0 and maze[i-1][j] != '#':
                g[i * w + j][(i-1) * w + j] = 1
                g[(i-1) * w + j][i * w + j] = 1
            if i < h-1 and maze[i+1][j] != '#':
                g[i * w + j][(i+1) * w + j] = 1
                g[(i+1) * w + j][i * w + j] = 1
            if j > 0 and maze[i][j-1] != '#':
                g[i * w + j][i * w + j-1] = 1
                g[i * w + j-1][i * w + j] = 1
            if j < w-1 and maze[i][j+1] != '#':
                g[i * w + j][i * w + j+1] = 1
                g[i * w + j+1][i * w + j] = 1

def floyed(g, nodes):
    result = 0
    for k in range(nodes):
        for i in range(nodes):
            if i == k:
                continue
            if g[i][k] == 10000000:
                continue
            for j in range(nodes):
                if g[k][j] == 10000000:
                    continue
                if i == j or i == k or k == j:
                    continue
                if g[i][j] > g[i][k] + g[k][j]:
                    g[i][j] = g[i][k] + g[k][j]
                    if g[i][j] < 10000000 and g[i][j] > result:
                        result = g[i][j]
    return result

print(floyed(g,nodes))

Submission status: Wrong Answer

Solution code:
input = raw_input

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

meiro = []
coords = []
for i in range(h):
    line = list(input())
    cur_coords = [(j, i) for j in range(w) if line[j] == "."]
    coords += cur_coords
    meiro.append(line)

graphs = []
graph = {}
for cur_coord in coords:
    x, y = cur_coord
    tugi_kouhos = [(x+dx, y) for dx in [-1, 1] if 0 <= x+dx < w]
    tugi_kouhos += [(x, y+dy) for dy in [-1, 1] if 0 <= y+dy < h]
    childs = []
    for tugi_kouho in tugi_kouhos:
        if tugi_kouho in coords:
            childs.append(tugi_kouho)
    graph[cur_coord] = childs


depth_dict_org = {}
for coord in coords:
    depth_dict_org[coord] = None

def calc_depth(coord1):
    depth_dict = depth_dict_org.copy()

    cur_coord = coord1
    #end_coord = coord2
    cur_depth = 0
    used_coords = [coord1]

    childs = graph[coord1]
    while len(childs) != 0:
        cur_depth += 1
        next_childs = []
        used_coords += childs
        for child in childs:
            res = get_childs(child, used_coords)
            #print("child", child, res)
            #print(used_coords)
            if len(res) == 0:
                return cur_depth
            next_childs += res

        childs = list(set(next_childs))
        #print(childs)

    return 0

def get_childs(jibun, used_coords):
    
    childs = []
    for child in graph[jibun]:
        if child not in used_coords:
            childs.append(child)
    return childs
       

n_coords = len(coords)
max_depth = 0
for i in range(n_coords):
    coord1 = coords[i]
    cur_depth = calc_depth(coord1)
    max_depth = max(max_depth, cur_depth)

print(max_depth)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10**8)
H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    # for j in range(W):
    #     if tmp[j] == ".":
    #         tmp[j] = 1
    #     else:
    #         tmp[j] = 0
    maze.append(tmp[:])
# print(*maze, sep="\n")
# exit()
def dfs(i, j, cnt):
    if i < 0 or j < 0 or i > H-1 or j > W-1 or maze[i][j] == "#" or visited[i][j]:
        # top.append(cnt)
        return
    if maze[i][j] == "g":
        top.append(cnt)
        top[0] = max(top[0], cnt)
    
    visited[i][j] = True
    cnt += 1
    dfs(i+1, j, cnt)
    dfs(i-1, j, cnt)
    dfs(i, j+1, cnt)
    dfs(i, j-1, cnt)

ans = -1
for sx in range(H):
    for sy in range(W):
        for ex in range(H):
            for ey in range(W):
                if maze[sx][sy] == "#" or maze[ex][ey] == "#":
                    continue
                if sx == ex and sy == ey:
                    continue
                maze[ex][ey] = "g"
                top = [-1]
                visited = [[False for _ in range(W)] for _ in range(H)]
                dfs(sx, sy, 0)
                # print(top)
                maze[ex][ey] = "."
                # print(top)
                if top[0] == -1:
                    continue
                ans = max(ans, top[0])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
from collections import deque
def bfs():
    cnt = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while len(Q) > 0:
        q = Q.popleft()
        y,x =  q[0], q[1]
        if cnt >= H*W:
            for i in range(H):
                if len(box[i]) == 0:
                    continue
                else:
                    ans.append(max(box[i]))
            return
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "#" and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = -1
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "." and box[ny][nx] == 0:
                cnt += 1
                box[ny][nx] = box[y][x] + 1
                Q.append([ny,nx])
    for i in range(H):
        if len(box[i]) == 0:
            continue
        else:
            ans.append(max(box[i]))
    return


H,W = map(int,input().split())
S = [ []for _ in range(H)]
for i in range(H):
    S[i] = list(input())
ans = []
INF = 50**2
Q = deque()
for i in range(H):
    for j in range(W):
        #各マス目に到達するために必要な移動回数
        box = [[0 for _ in range(W)] for __ in range(H)]
        Q.append([i,j])
        bfs()
if len(ans)==0:
    print(0)
    exit()
print(max(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def solve(s):
    offset = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = [[-1] * W for _ in range(H)]
    visited[0][0] = 0
    
    if s[0] < W and s[1] < H:
        if S[s[1]][s[0]] != "#":
            visited[s[1]][s[0]] = 1
        else:
            return visited

    if s[0] >= W or s[1] >= H:
        return visited
    
    q = deque()
    q.append(s)

    while q:
        x, y = q.popleft()

        for u, v in offset:
            if not (0 <= x + u < W) or not (0 <= y + v < H):
                continue

            if visited[y + v][x + u] > -1 or S[y + v][x + u] == "#":
                continue

            visited[y + v][x + u] = visited[y][x] + 1
            q.append((x + u, y + v))
            
    return visited

ans_1 = (0, 0, 0)
for y, v in enumerate(solve((0, 1))):
    for x, c in enumerate(v):
        if c >= ans_1[2]:
            ans_1 = (x, y, c)
        
ans_2 = (0, 0, 0)
for y, v in enumerate(solve((1, 0))):
    for x, c in enumerate(v):
        if c >= ans_2[2]:
            ans_2 = (x, y, c)
        
if ans_1[0] == ans_2[0] and ans_1[1] == ans_2[1]:
    print(min(ans_1[2], ans_2[2]))
else:
    print(ans_1[2] + ans_2[2])

Submission status: Wrong Answer

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

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


def bfs(h,w,n):
    yoyaku=[]
    if h>0:
        if lis[h-1][w]>n+1 and mp[h-1][w]!="#":
            yoyaku.append([h-1,w,n+1])
    if w>0:
        if lis[h][w-1]>n+1 and mp[h][w-1]!="#":
            yoyaku.append([h,w-1,n+1])
    if h<H-1:
        if lis[h+1][w]>n+1 and mp[h+1][w]!="#":
            yoyaku.append([h+1,w,n+1])
    if w<W-1:
        if lis[h][w+1]>n+1 and mp[h][w+1]!="#":
            yoyaku.append([h,w+1,n+1])
    
    lis[h][w]=min(n,lis[h][w])
    return yoyaku

    

mp=[]
for _ in range(H):
    mp.append(list(input()))

ans=[]

for h in range(H):
    for w in range(W):
        lis=[[1000]*W for i in range(H)]
        que=deque([[[h,w,0]]]) if mp[h][w]!="#" else []
        pre=0
        while True:
            if len(que)==0:
                break
            else:
                temp=que.pop()
                #print(temp)
                for tem in temp:
                    pre=max(pre,tem[2])
                    que.append(bfs(tem[0],tem[1],tem[2]))
                    
        pre=0
        for item in lis:
            for tem in item:
                pre=max(pre,tem)    
        ans.append(pre)
    
print(max(ans))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from copy import deepcopy

input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
m = [['#' for _ in range(w+2)] for _ in range(h+2)]

for hi in range(1, h+1):
    for wi, s in enumerate(input().strip(), start=1):
        m[hi][wi] = s
        if s == '.':
            hs, ws = hi, wi

def bfs(hs, ws, m):
    cost = 0
    q = deque([])
    m[hs][ws] = '#'
    for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
        if m[hs+offset[0]][ws+offset[1]] == '.':
            q.append((hs+offset[0], ws+offset[1]))
    while q:
        cost += 1
        q_ = deque(q)
        q = deque([])
        for h, w in q_:
            m[h][w] = '#'
            for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
                if m[h+offset[0]][w+offset[1]] == '.':
                    q.append((h+offset[0], w+offset[1]))

    return cost, h, w

maxi = -1
maxi_ = 0
while maxi != maxi_:
    maxi_ = maxi
    maxi, hs, ws = bfs(hs, ws, deepcopy(m[:]))

print(maxi)