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:
h,w = map(int,input().split())
g=[input() for _ in range(h)]

def cost(x):
    v=[[0]*w for _ in range(h)]
    que = [x]
    ans=-1
    while que:
        newque = []
        for X,Y in que:
            for x,y in ((0,-1),(-1,0),(0,1),(1,0)):
                if 0<=X+x<w and 0<=Y+y<h and g[Y+y][X+x]=='.' and v[Y+y][X+x]==0:
                    v[Y+y][X+x] = 1
                    newque.append((X+x,Y+y))
        ans+=1
        que = newque
    return ans

ans = 0
for i in range(w):
    for j in range(h):
        if g[j][i]=='.':
            ans = max(ans,cost((i,j)))
print(ans)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter

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

cost = np.zeros((h,w),dtype = int) + 999
done = np.zeros((h,w),dtype = bool)
barrier = np.zeros((h,w),dtype = bool)

g=np.array([[0,1,0],
            [1,1,1],
            [0,1,0]])

for i in range(h):
    maze[i]=list(maze[i])
    for j in range(w):
        if maze[i][j] == '#':
           barrier[i][j]= True

n_cost_max=0
for ystart in range(h):
    for xstart in range(w):
        if barrier[ystart,xstart]:
            break
        else:
            cost.fill(999)
            done.fill(False)
            cost[ystart,xstart]=0
            done[ystart,xstart]=True
            for i in range(999):
                n_done=(np.count_nonzero(done+barrier))
                if n_done==done.size:
                    break
                else:
                    done_next = maximum_filter(done,footprint=g)*~done
                    cost_next = minimum_filter(cost,footprint=g) * done_next
                    cost_next[done_next] +=1
                    cost[done_next]=cost_next[done_next]
                    cost[barrier]=999
                    done[done_next]=done_next[done_next]
                    done[barrier]=False
            n_cost=np.max(cost*~barrier)
            if n_cost > n_cost_max:
                n_cost_max = n_cost
print(n_cost_max)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter

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

cost = np.zeros((h,w),dtype = int) + 999
done = np.zeros((h,w),dtype = bool)
barrier = np.zeros((h,w),dtype = bool)

g=np.array([[0,1,0],
            [1,1,1],
            [0,1,0]])

for i in range(h):
    maze[i]=list(maze[i])
    for j in range(w):
        if maze[i][j] == '#':
           barrier[i][j]= True

n_cost_max=0
for ystart in range(h):
    for xstart in range(w):
        if barrier[ystart,xstart]:
            break
        else:
            cost.fill(999)
            done.fill(False)
            cost[ystart,xstart]=0
            done[ystart,xstart]=True
            for i in range(999):
                n_done=(np.count_nonzero(done+barrier))
                if n_done==done.size:
                    break
                else:
                    done_next = maximum_filter(done,footprint=g)*~done
                    cost_next = minimum_filter(cost,footprint=g)
                    cost_next[done_next] +=1
                    cost[done_next]=cost_next[done_next]
                    cost[barrier]=999
                    done[done_next]=done_next[done_next]
                    done[barrier]=False
            n_cost=np.max(cost*~barrier)
            if n_cost > n_cost_max:
                n_cost_max = n_cost
print(n_cost_max)

Submission status: Wrong Answer

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

def is_street(s, t):
    return S[s][t] == '.'

def count(maze):
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    m = []
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0

    q = [[h, w]]
    while len(q) != 0:
        t, u = q.pop(0)
        cost = m[t][u]

        # 上
        ue = [t-1, u]
        if ue[0] >= 0 and m[ue[0]][ue[1]] == -1 and is_street(ue[0], ue[1]):
            m[ue[0]][ue[1]] = cost + 1
            q.append(ue)

        shita = [t+1, u]
        if shita[0] < H and m[shita[0]][shita[1]] == -1 and is_street(shita[0], shita[1]) :
            m[shita[0]][shita[1]] = cost + 1
            q.append(shita)

        hidari = [t, u-1]
        if hidari[1] >= 0 and m[hidari[0]][hidari[1]] == -1 and is_street(hidari[0], hidari[1]):
            m[hidari[0]][hidari[1]] = cost + 1
            q.append(hidari)

        migi = [t, u+1]
        if migi[1] < W and m[migi[0]][migi[1]] == -1 and is_street(migi[0], migi[1]):
            m[migi[0]][migi[1]] = cost + 1
            q.append(migi)

    max_cost = count(m)
    return max_cost

ans = -1
for i in range(H):
    for j in range(W):
        c = bfs(i, j)
        ans = max(ans, c)

print(ans)

Submission status: Wrong Answer

Solution code:
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]
#迷路の白マスを数える作業
white=[]
for i in range(r):
    for j in range(c):
        if meiro[i][j]==".":
            white.append([i+1,j+1])
#迷路の外を＃で囲む
for i in range(r):
    meiro[i].insert(c,"#")
    meiro[i].insert(0,"#")
meiro.insert(0,["#"]*(c+2))
meiro.append(["#"]*(c+2))
#print(meiro)
def bfs(sx,sy):
    idou=[[0,1],[0,-1],[1,0],[-1,0]]
    tesuu=[[-1]*(c+2) for i in range(r+2)]
    from collections import deque
    tesuu[sx][sy]=0
    #print(tesuu)
    quest=deque([[sx,sy]])#最初に見る場所
    while len(quest)!=0:
        see=quest.popleft()
        for i in idou:
            if meiro[see[0]+i[0]][see[1]+i[1]]=="#":
                continue
            if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
                continue
            quest.append([see[0]+i[0],see[1]+i[1]])
            tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
    return max(max(tesuu))
tesuu_=[]
for i in range(len(white)):
    tesuu_.append(bfs(white[i][0],white[i][1]))
print(max(tesuu_))

Submission status: Wrong Answer

Solution code:
H, W = list(map(int,input().split()))
S = ["#"*(W+2)]
for y in range(H):
    S.append("#"+input()+"#")
S.append("#"*(W+2))
ret = 0
for py in range(1,H+1):
    for px in range(1,W+1):
        if S[py][px]=="#":
            continue
        d = [[-1 for x in range(W+2)] for y in range(H+2)]
        d[py][px]=0
        q=[(py,px)]
        while q:
            y1,x1=q.pop(0)
            for dy,dx in ((0,1),(0,-1),(1,0),(-1,0)):
                y2=y1+dy
                x2=x1+dx
                if S[y2][x2]=="#" or d[y2][x2]>=0:
                    continue
                d[y2][x2]=d[y1][x1]+1
                q.append((y2,x2))
        ret = max(ret, max(max(d)))
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

def bfs(x,y):
    dist = 1
    maze = copy.deepcopy(maze_i)
    visited = deque()
    visited.append((x,y))
    maze[y][x] == "#"
    destination = deque()
    search = [(1,0),(-1,0),(0,1),(0,-1)]
    for (dx,dy) in search:
        if maze[y+dy][x+dx] == ".":
            destination.append((x+dx,y+dy))
    same_dist = len(destination)
    moved = 0
    x = destination[0][0]
    y = destination[0][1]
    while destination:
        maze[y][x] = "#"
        visited.append((x,y))
        destination.popleft()
        for (dx,dy) in search:
            if maze[y+dy][x+dx] == ".":
                if (x+dx,y+dy) not in destination:
                    destination.append((x+dx,y+dy))
        if len(destination) >= 1:
            x = destination[0][0]
            y = destination[0][1]
            moved += 1
            if moved == same_dist:
                dist += 1
                moved = 0
                same_dist = len(destination)
    return dist

H,W = map(int,input().split())
maze_i = [list("#"*(W+2))] + [list("#" + input() + "#") for i in range(H)] + [list("#"*(W+2))]
ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if maze_i[y][x] == ".":
            ans = max(ans,bfs(x,y))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

def bfs(x,y):
    dist = 1
    moved = 1
    maze = copy.deepcopy(maze_i)
    visited = deque()
    visited.append((x,y))
    maze[y][x] == "#"
    destination = deque()
    search = [(1,0),(-1,0),(0,1),(0,-1)]
    for (dx,dy) in search:
        if maze[y+dy][x+dx] == ".":
            destination.append((x+dx,y+dy))
    same_dist = len(destination)
    x = destination[0][0]
    y = destination[0][1]
    while destination:
        maze[y][x] = "#"
        visited.append((x,y))
        destination.popleft()
        for (dx,dy) in search:
            if maze[y+dy][x+dx] == ".":
                if (x+dx,y+dy) not in destination:
                    destination.append((x+dx,y+dy))
        if len(destination) >= 1:
            x = destination[0][0]
            y = destination[0][1]
            moved += 1
            if moved == same_dist:
                dist += 1
                same_dist += len(destination)
    return dist

H,W = map(int,input().split())
maze_i = [list("#"*(W+2))] + [list("#" + input() + "#") for i in range(H)] + [list("#"*(W+2))]
ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if maze_i[y][x] == ".":
            ans = max(ans,bfs(x,y))

print(ans)

Submission status: Wrong Answer

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

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

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] != '#':
            mat[i][next_idx] = 1

for i in range(w*h):
    #print(i,i,i,i,i,i,i,i,i)
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 10**18
tmp = []

for i in range(w*h):
    for j in range(w*h):
        if ans > mat[i][j]:
            tmp.append(mat[i][j])
            
print(max(tmp))

Submission status: Wrong Answer

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



H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
que = deque()
ans  = -1
for sx in range(W):
    for sy in range(H): # スタート地点のループ
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        que.append((sy,sx))
        dist[sy][sx] = 0
        while que:
            y,x = que.popleft()
            for temp in go:
                gx,gy = temp
                nx = x + gx
                ny = y + gy
                if 0<= nx < W and 0<= ny < H and C[ny][nx] != "#":
                    if dist[ny][nx] == -1: # ここの更新にminはいらない(幅優先なので自明に最短距離を進む)
                        dist[ny][nx] = dist[y][x] + 1
                        que.append( (ny,nx))
        for temp in dist:
            cand = max(temp)
            ans = max(ans,cand)
print(ans)

Submission status: Wrong Answer

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

def bfs(que):
  d = 0
  while que:
    y,x = que.popleft()
    d = dist[y][x]
    for dy, dx in ((0,1),(1,0),(0,-1),(-1, 0)):
      next_y = y + dy
      next_x = x + dx
      if(0 <= next_y and next_y < h and 0 <= next_x and next_x < w and maze[next_y][next_x] != "#" and dist[next_y][next_x] == -1):
        que.append((next_y,next_x))
        dist[next_y][next_x] = d + 1
  return d

ans = -1
for i in range(h):
  for j in range(w):
    que = deque()
    dist = [ [-1]*w for _ in range(h) ]
    dist[i][j] = 0
    que.append((i, j))
    ans = max([ans, bfs(que)])
print(ans)

Submission status: Wrong Answer

Solution code:
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.state = 0
        self.cost = -1

    def __str__(self):
        return str(self.cost)

    def __repr__(self):
        return str(self.cost)


def show(points):
    for row in points:
        print(*row)


def maxp(points):
    mp = 0
    for row in points:
        for cell in row:
            mp = max(cell.cost, mp)
    return mp


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


for sy in range(h):
    for sx in range(w):
        p = [[Point(x, y) for x in range(w)] for y in range(h)]
        next_search = [(sx, sy)]
        p[sy][sx].cost = 0
        while next_search:
            x, y = next_search.pop(0)
            t = p[y][x]
            if t.state == -1:
                continue
            t.state = -1
            if s[y + 1][x + 1] == "#":
                continue
            if s[y + 1][x] == ".":
                u = p[y][x - 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x - 1, y))
            if s[y + 1][x + 2] == ".":
                u = p[y][x + 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x + 1, y))
            if s[y][x + 1] == ".":
                u = p[y - 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y - 1))
            if s[y + 2][x + 1] == ".":
                u = p[y + 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y + 1))
        ans = max(maxp(p), ans)
        show(p)
        print()
print(ans)

Submission status: Wrong Answer

Solution code:
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.state = 0
        self.cost = -1

    def __str__(self):
        return str(self.cost)

    def __repr__(self):
        return str(self.cost)


def show(points):
    for row in points:
        print(*row)


def maxp(points):
    mp = 0
    for row in points:
        for cell in row:
            mp = max(cell.cost, mp)
    return mp


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


for sy in range(h):
    for sx in range(w):
        p = [[Point(x, y) for x in range(w)] for y in range(h)]
        next_search = [(sx, sy)]
        p[sy][sx].cost = 0
        while next_search:
            x, y = next_search.pop()
            t = p[y][x]
            if t.state == -1:
                continue
            t.state = -1
            if s[y + 1][x + 1] == "#":
                continue
            if s[y + 1][x] == ".":
                u = p[y][x - 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x - 1, y))
            if s[y + 1][x + 2] == ".":
                u = p[y][x + 1]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x + 1, y))
            if s[y][x + 1] == ".":
                u = p[y - 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y - 1))
            if s[y + 2][x + 1] == ".":
                u = p[y + 1][x]
                u.cost = t.cost + 1 if u.cost == -1 else min(t.cost + 1, u.cost)
                next_search.append((x, y + 1))
        ans = max(maxp(p), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=[int(i) for i in input().split()]
# c=[[i for i in input().split()] for _ in range(h)]
C=list(input() for _ in range(H))
C=list(list(i) for i in C) #visited_listを用いずに壁にしていく方法ではリスト化が必要

def bfs(maze,s1,s2,g1,g2):
    for y in range(H):
        for x in range(W):
            if maze[y][x]!='#':
                maze[y][x]=10**9

    maze[s1][s2]=0
    que=deque([[s1,s2]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if nexty >= 0 and nexty < H and nextx >= 0 and nextx < W:
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    return maze[g1][g2]

ans=0
for s1,c_w in enumerate(C):
    for s2,c in enumerate(c_w):
        if C[s1][s2]=="#":
            break
        else:
            for g1,c_w in enumerate(C):
                for g2,c in enumerate(c_w):
                    if C[g1][g2]=="#":
                        break
                    else:
                        temp=bfs(C,s1,s2,g1,g2)
                        ans=max(temp,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w =map(int, input().split())
a =['#'*(w+2)] + ['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans=0
for ii in range(h):
    for jj in range(w):
        if a[ii+1][jj+1]=='#':
            continue
        count=1
        n=[(ii+1,jj+1)]
        route={n[0]:0}
        p=[[1,0],[0,1],[-1,0],[0,-1]]
        while count != 100:
            route2 = route.copy()
            n2=[]
            for i in n:
                for j in p:
                    np=(i[0]+j[0],i[1]+j[1])
                    if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                        n2.append(np)
                        route[np]=count
            n=n2
            count+=1
            if route == route2:
                break
        ans=max(ans,max(route.values()))
        #print(ans, route)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w =map(int, input().split())
a =['#'*(w+2)] + ['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans=0
for ii in range(h):
    for jj in range(w):
        count=1
        n=[(ii+1,jj+1)]
        route={n[0]:0}
        p=[[1,0],[0,1],[-1,0],[0,-1]]
        while count != 100:
            route2 = route.copy()
            n2=[]
            for i in n:
                for j in p:
                    np=(i[0]+j[0],i[1]+j[1])
                    if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                        n2.append(np)
                        route[np]=count
            n=n2
            count+=1
            if route == route2:
                break
        ans=max(ans,max(route.values()))
        #print(ans, route)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w =map(int, input().split())
a =['#'*(w+2)] + ['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans=0
for ii in range(h):
    for jj in range(w):
        count=1
        n=[(ii,jj)]
        route={n[0]:0}
        p=[[1,0],[0,1],[-1,0],[0,-1]]
        while count != 100:
            route2 = route.copy()
            n2=[]
            for i in n:
                for j in p:
                    np=(i[0]+j[0],i[1]+j[1])
                    if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                        n2.append(np)
                        route[np]=count
            n=n2
            count+=1
            if route == route2:
                break
        ans=max(ans,max(route.values()))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w =map(int, input().split())
a =['#'*(w+2)] + ['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans=0
for ii in range(h):
    for jj in range(w):
        for k in range(h):
            for l in range(w):
                ys, xs = ii+1, jj+1
                yg, xg = k+1, l+1
                
                if yg<ys or xg<xs:
                    continue
                    
                n=[(ys-1,xs-1)]
                route={n[0]:0}
                p=[[1,0],[0,1],[-1,0],[0,-1]]
                count=1
                while route.get((yg-1,xg-1),0)==0 and count != 100:
                    n2=[]
                    for i in n:
                        for j in p:
                            np=(i[0]+j[0],i[1]+j[1])
                            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                                n2.append(np)
                                route[np]=count
                    n=n2
                    count+=1
                ans=max(ans,max(route.values()))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w =map(int, input().split())
a =['#'*(w+2)] + ['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans=0
for ii in range(h):
    for jj in range(w):
        for k in range(h):
            for l in range(w):
                ys, xs = ii+1, jj+1
                yg, xg = k+1, l+1
                
                if yg<ys or xg<xs:
                    continue
                    
                n=[(ys-1,xs-1)]
                route={n[0]:0}
                p=[[1,0],[0,1],[-1,0],[0,-1]]
                count=1
                while route.get((yg-1,xg-1),0)==0 and count != 100:
                    n2=[]
                    for i in n:
                        for j in p:
                            np=(i[0]+j[0],i[1]+j[1])
                            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                                n2.append(np)
                                route[np]=count
                    n=n2
                    count+=1
                ans=max(ans,max(route.values()))
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

h,w = [int(i) for i in input().split()]
m = [list(input()) for i in range(h)]
for l in m:
    l.insert(0,'#')
    l.append('#')
m.insert(0,['#']*(w+2))
m.append(['#']*(w+2))

x = 0
y = 0
ans = 0

def numap(i,j,m):
    global x
    global y
    global ans
    que = [[i,j]]
    count = 0
    while que:
        newque = []
        for q in que:
            if m[q[0]][q[1]]=='.':
                x=q[0]
                y=q[1]
                m[x][y]=count
                newque.append([x+1,y])
                newque.append([x,y+1])
                newque.append([x-1,y])
                newque.append([x,y-1])
        que = newque
        count+=1
    ans = max(ans,count-2)

while True:
    flag = 0
    mp = copy.deepcopy(m)
    breakflag = False
    for i,a in enumerate(mp):
        for j,b in enumerate(a):
            if b == '.':
                numap(i,j,mp)
                breakflag = True
                break
        if breakflag:
            break
    if breakflag == False:
        break
    numap(x,y,m)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

h,w = [int(i) for i in input().split()]
m = [list(input()) for i in range(h)]
for l in m:
    l.insert(0,'#')
    l.append('#')
m.insert(0,['#']*(w+2))
m.append(['#']*(w+2))

x = 0
y = 0
ans = 0

def numap(i,j,m):
    global x
    global y
    global ans
    que = [[i,j]]
    count = 0
    while que:
        newque = []
        for q in que:
            if m[q[0]][q[1]]=='.':
                x=q[0]
                y=q[1]
                m[x][y]=count
                newque.append([x+1,y])
                newque.append([x,y+1])
                newque.append([x-1,y])
                newque.append([x,y-1])
        que = newque
        count+=1
    ans = max(ans,count-2)
    
# i行j列 という指定の仕方になる
mp = copy.deepcopy(m)
breakflag = False
for i,a in enumerate(mp):
    for j,b in enumerate(a):
        if b == '.':
            numap(i,j,mp)
            breakflag = True
            break
    if breakflag:
        break
numap(x,y,m)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
iH, iW = map(int, input().split())
naAll = np.zeros((iH+2, iW+2), dtype=int) - 1
#0123:udlr
iID0 = 0
for iH0 in range(iH):
  s = input()
  for i, s0 in enumerate(s):
    if s0 == ".":
      naAll[iH0+1, i+1] = iID0
      iID0 += 1
lMaze = [[] for _ in range(iID0)]
lPoss = []
for iH0 in range(iH):
  for iW0 in range(iW):
    if naAll[iH0+1, iW0+1] >= 0:
      iID = naAll[iH0 + 1, iW0 + 1]
      if naAll[iH0 + 2, iW0 + 1] >= 0:
        lMaze[iID].append(naAll[iH0 + 2, iW0 + 1])
      if naAll[iH0 + 1, iW0 + 2] >= 0:
        lMaze[iID].append(naAll[iH0 + 1, iW0 + 2])
      if naAll[iH0    , iW0 + 1] >= 0:
        lMaze[iID].append(naAll[iH0    , iW0 + 1])
      if naAll[iH0 + 1, iW0    ] >= 0:
        lMaze[iID].append(naAll[iH0 + 1, iW0    ])
      if not( (naAll[iH0 + 2, iW0 + 1] >= 0 and \
               naAll[iH0    , iW0 + 1] >= 0) or
              (naAll[iH0 + 1, iW0 + 2] >= 0 and \
               naAll[iH0 + 1, iW0    ] >= 0) ):
        lPoss.append(iID)
      #print(iID, lMaze)
lMax = []
for iID in lPoss:
  lState = [0]*iID0
  lState[iID] = 1
  lMazeNow = [lMaze[iID]]
  iPre        = 1
  iTime       = 0
  while iPre < iID0:
    lMazeNow0 = []
    for lMazeNext in lMazeNow :
      for iIDnext in lMazeNext:
        if lState[iIDnext] == 0:
          lState[iIDnext] = 1
          iPre += 1
          lMazeNow0.append(lMaze[iIDnext])
    lMazeNow = lMazeNow0
    iTime += 1
    #print(iID, iTime, lState)
  lMax.append(iTime)
print(max(lMax))
#print(lMaze)
#print(naAll)

Submission status: Wrong Answer

Solution code:
from collections import deque

d=[(1,0),(0,1),(-1,0),(0,-1)]
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
def BFS(i,j):
    q = deque()
    dist = [[-1]*W for _ in range(H)]
    if M[i][j] == '.':

        #前処理
        Ma = 0
        q.append((i, j))#スタート地点挿入
        dist[i][j] = 0
        while q:
            cx,cy = q.popleft()
            for nx,ny in d:
                x ,y= cx+nx,cy+ny
                if 0<= x < H and 0<= y < W and M[x][y] == "." and dist[x][y]==-1:
                    dist[x][y]=dist[cx][cy]+1
                    Ma = max(Ma,dist[x][y])
                    q.append((x,y))
        return Ma
    return 0
for i in range(H):#全部の地点でBFSをためす
    for j in range(W):
        Max_list.append(BFS(i,j))
print(Max_list)
print(max(Max_list))

Submission status: Wrong Answer

Solution code:
import queue

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

ddx = [1,-1,0,0]
ddy = [0,0,1,-1]

INF = 1<<30
ans = 0
for sx in range(W):
    for sy in range(H):            
        d = 0
        q = queue.Queue()
        dist = [[INF]*W for _ in range(H)]
        dist[sy][sx] = 0
        q.put([sx,sy])
        while not q.empty():
            x,y = q.get()
            for i in range(4):
                dx = ddx[i]
                dy = ddy[i]
                if y+dy<0 or y+dy>=H or x+dx<0 or x+dx>=W:
                    continue
                if S[y+dy][x+dx] == '.' and dist[y+dy][x+dx] == INF:
                    dist[y+dy][x+dx] = dist[y][x] + 1
                    q.put([x+dx,y+dy])
        
        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    d = max(d,dist[i][j])
            
        ans = max(ans,d)
        
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
Atlas = [list(input()) for i in range(H)]
 
def BFS(a,b,atlas):
  times = 0
  queue = [[a, b]]
  old_queue = []
  while True:
    new_queue = []
    changed = False
    for x, y in queue:
      if x+1 < H:
        if atlas[x+1][y] != "#" and not [x+1, y] in old_queue:
          new_queue.append([x+1, y])
          old_queue.append([x+1, y])
          changed = True
      if x-1 >= 0:
        if atlas[x-1][y] != "#" and not [x-1, y] in old_queue:
          new_queue.append([x-1, y])
          old_queue.append([x-1, y])
          changed = True
      if y+1 < W:
        if atlas[x][y+1] != "#" and not [x, y+1] in old_queue:
          new_queue.append([x, y+1])
          old_queue.append([x, y+1])
          changed = True
      if y-1 >= 0:
        if atlas[x][y-1] != "#" and not [x, y-1] in old_queue:
          new_queue.append([x, y-1])
          old_queue.append([x, y-1])
          changed = True
    queue = new_queue
    if not changed:
      break
    times += 1
  return times
 
TIMES = 0
for j in range(H):
  for k in range(W):
    if Atlas[j][k] == "#":
      continue
    new_TIMES = BFS(j, k, Atlas)
    if new_TIMES > TIMES:
      TIMES = new_TIMES
      
print(TIMES)

Submission status: Wrong Answer

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

def BFS(a,b,atlas):
  times = 0
  queue = [[a, b]]
  old_queue = []
  while True:
    new_queue = []
    changed = False
    for x, y in queue:
      if x+1 < H:
        if atlas[x+1][y] != "#" and not [x+1, y] in old_queue:
          new_queue.append([x+1, y])
          old_queue.append([x+1, y])
          changed = True
      if x-1 >= 0:
        if atlas[x-1][y] != "#" and not [x-1, y] in old_queue:
          new_queue.append([x-1, y])
          old_queue.append([x-1, y])
          changed = True
      if y+1 < W:
        if atlas[x][y+1] != "#" and not [x, y+1] in old_queue:
          new_queue.append([x, y+1])
          old_queue.append([x, y+1])
          changed = True
      if y-1 >= 0:
        if atlas[x][y-1] != "#" and not [x, y-1] in old_queue:
          new_queue.append([x, y-1])
          old_queue.append([x, y-1])
          changed = True
    queue = new_queue
    if not changed:
      break
    times += 1
  return times
 
TIMES = 0
for j in range(H):
  for k in range(W):
    if Atlas[j][k] == "#":
      break
    new_TIMES = BFS(j, k, Atlas)
    if new_TIMES > TIMES:
      TIMES = new_TIMES
      
print(TIMES)