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())
s = [input() for _ in range(h)]

INF = 1001001001
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

def update(i, j, x):
    global dist, s, q
    if(dist[i][j] != INF): return
    dist[i][j] = x
    q.append([i, j])

res = 0
for si in range(h):
    for sj in range(w):
        
        dist = [[INF for _ in range(w)] for _ in range(h)]
        q = deque()
        update(si, sj, 0)
        
        while(q):
            i, j = q.popleft()
            
            for idir, jdir in zip(di, dj):
                ni = i + idir
                nj = j + jdir
                
                if(ni<0 or ni>=h or nj<0 or nj>=w): continue
                if(s[ni][nj] == '#'): continue
                
                update(ni, nj, dist[i][j]+1)
        
        for i in range(h):
            for j in range(w):
                if(dist[i][j]==INF): continue
                res = max(res, dist[i][j])

print(res)

Submission status: Wrong Answer

Solution code:
import queue

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

for i in range(h):
	mazeRow = list(input())
	maze.append(mazeRow)
	
maxRootCnt = 0

#スタート→ゴール全探索（ま？）
for roop_h in range(h):
	for roop_w in range(w):
		if maze[roop_h][roop_w] == '#':
			continue

		isSearched =  [[0] * w for i in range(h)]
		isLevel =  [[0] * w for i in range(h)]
		nowTansakuCnt = 0

		q = queue.Queue()
		q.put([roop_h,roop_w])

		# 探索済マスセット
		isSearched[roop_h][roop_w] = 1
		isLevel[roop_h][roop_w] = 0
		while not q.empty():
			n= q.get()
			nowLevel = isLevel[n[0]][n[1]]
			if nowLevel > maxRootCnt:
				maxRootCnt = nowLevel
			#北
			if n[0] != 0:
				if maze[n[0] -1][n[1]] == '.' and isSearched[n[0] -1][n[1]] == 0:
					q.put([n[0]-1,n[1]])
					isSearched[n[0] -1][n[1]] = 1
					isLevel[n[0] -1][n[1]] = nowLevel + 1
			#南
			if n[0] != h-1:
				if maze[n[0] +1][n[1]] == '.' and isSearched[n[0]+-1][n[1]] == 0:
					q.put([n[0]+1,n[1]])
					isSearched[n[0] +1][n[1]] = 1
					isLevel[n[0] +1][n[1]] = nowLevel + 1
				
			#西
			if n[1] != 0:
				if maze[n[0]][n[1]-1] == '.' and isSearched[n[0]][n[1]-1] == 0:
					q.put([n[0],n[1]-1])
					isSearched[n[0]][n[1]-1] = 1
					isLevel[n[0]][n[1]-1] = nowLevel + 1

			#東            
			if n[1] != w-1:
				if maze[n[0]][n[1]+1] == '.' and isSearched[n[0]][n[1]+1] == 0:
					q.put([n[0],n[1]+1])
					isSearched[n[0]][n[1]+1] = 1
					isLevel[n[0]][n[1]+1] = nowLevel + 1
				                    
print(maxRootCnt)

Submission status: Wrong Answer

Solution code:
import queue

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

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

for i in range(H):
    S[i]=input()

def bfs(i,j):
    max_d=0
    q=queue.Queue()
    q.put((i,j))
    d=[[0]*W for _ in range(H)]
    while not q.empty():
        loc=q.get()
        for k in range(len(dx)):
            x=loc[1]+dx[k]
            y=loc[0]+dy[k]
            if x>=0 and x<W and y>=0 and y<H:
                if S[y][x]==".":
                    if d[y][x]==0 and not(x==j and y==i):
                        q.put((y,x))
                        d[y][x]=d[loc[0]][loc[1]]+1
                        max_d=max(max_d,d[y][x])
    return max_d

ans=0
for i in range(H):
    for j in range(W):
        ans=max(bfs(i,j),ans)
        
print(ans)

Submission status: Wrong Answer

Solution code:
import queue

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

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

for i in range(H):
    S[i]=input()

def bfs(i,j):
    max_d=0
    q=queue.Queue()
    q.put((i,j))
    d=[[0]*W for _ in range(H)]
    while not q.empty():
        loc=q.get()
        for k in range(len(dx)):
            x=loc[1]+dx[k]
            y=loc[0]+dy[k]
            if x>=0 and x<W and y>=0 and y<H:
                if S[y][x]==".":
                    if d[y][x]==0:
                        q.put((y,x))
                        d[y][x]=d[loc[0]][loc[1]]+1
                        max_d=max(max_d,d[y][x])
    return max_d

ans=0
for i in range(H):
    for j in range(W):
        ans=max(bfs(i,j),ans)
        
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf,i) for i in range(n)]
    prev=[0]*n
    q=[i for i in d]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur][0]+dist
            if alt<d[dst][0]:
                d[dst]=(alt,dst)
                prev[dst]=cur
                heappush(q,(alt,dst))
    return [i for i,j in d],prev

def cv(i,j):
    return i*w+j
def rcv(x):
    return x//w,x%w




ans=0

h,w=LI()

mp=[[1]*(w+2)]
for i in range(h):
    mp.append([1]+[1 if i=='#' else 0 for i in input()]+[1])
mp.append([1]*(w+2))
h+=2
w+=2

n=h*w

def bfs(sh,sw):
    g=[[-1]*w for i in range(h)]
    dd=[(0,1),(0,-1),(1,0),(-1,0)]#+[(1,1),(1,-1),(-1,-1),(-1,1)]
    
    q=deque()
    q.append((sh,sw))
    g[sh][sw]=0
    while q:
        ch,cw=q.pop()
        
        for di,dj in dd:
            if mp[ch+di][cw+dj]==0 and g[ch+di][cw+dj]==-1:
                q.append((ch+di,cw+dj))
                g[ch+di][cw+dj]=min(g[ch][cw]+1,g[ch+di][cw+dj])
    MG=0
    for i in range(h):
        MG=max(MG,max(g[i]))
        
    
    return MG

ans=0
for i in range(1,h-1):
    for j in range(1,w-1):
        if mp[i][j]==1:continue
        ans=max(bfs(i,j),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#d maze master

from collections import deque

def bfs(sx,sy):
    cnt=0
    INF=100100100
    #mazeのまわりを"#"で囲ったので
    dist=[[INF]*(w+2) for _ in range(h+2)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

    que=deque([])
    que.append((sx,sy))
    dist[sx][sy]=0

    #while内でpopして空になったとき(最後の層)まで調べた
    while que:
        q=que.popleft()

        for i in range(4):
            next_x=q[0]+dx[i]
            next_y=q[1]+dy[i]

            if maze[next_x][next_y]!="#" and dist[next_x][next_y]==INF:
                que.append((next_x,next_y))
                dist[next_x][next_y]=dist[q[0]][q[1]]+1
                cnt=dist[next_x][next_y]
                #一番最後の層の距離に更新される
    return cnt

h,w=map(int,input().split())
maze=[]
ans=0
x=""
for i in range(w+2):
    x+="#"
maze.append(x)
for i in range(h):
    s=input()
    s='#'+s+'#'
    maze.append(s)
maze.append(x)
for i in range(1,h+1):
    for j in range(1,w+1):
        ans=max(ans,bfs(i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = -1
direc = [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(start):
  Dis = [[INF]*W for _ in range(H)]
  Dis[start[0]][start[1]]=0
  q = deque([])# スタック
  q.append(start)
  while len(q)!=0:
    h,w = q.popleft()# スタック取りだし（先頭）
    for d in direc:
      hs, ws = h + d[0], w + d[1]
      if 0<=hs<H and 0<=ws<W and Dis[hs][ws]==INF:
        if Gd[hs][ws]=='.':
          q.append([hs,ws])
          Dis[hs][ws]=Dis[h][w] + 1
  return max(max(Dis))
ans = INF
for h in range(H):
  for w in range(W):
    if Gd[h][w]=='.':
      ans = max(ans,dfs([h,w]))
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue

def bfs(HW, q):
    num = 0
    mem = []
    while not q.empty():
        current = q.get()
        if current[0] >= H or current[0] < 0 or current[1] >= W or current[1] < 0:
            continue
        if HW[current[0]][current[1]] == '#':
            continue

        if [current[0]+1,current[1]]  not in mem:
            mem.append([current[0]+1,current[1]])
            q.put([current[0]+1,current[1],current[2]+1])
        if [current[0],current[1]+1]  not in mem:
            mem.append([current[0],current[1]+1])
            q.put([current[0],current[1]+1,current[2]+1])
        if [current[0]-1,current[1]]  not in mem:
            mem.append([current[0]-1,current[1]])
            q.put([current[0]-1,current[1],current[2]+1])
        if [current[0],current[1]-1]  not in mem:
            mem.append([current[0],current[1]-1])
            q.put([current[0],current[1]-1,current[2]+1])
    return (current[2]-1)


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

HW = [[''] * W for i in range(H)]
for i in range(H):
    h = str(input())
    HW[i] = h

ans = 0
for si in range(H):
    for sj in range(W):
        if HW[si][sj] == '#':
            continue
        q = Queue()
        q.put([si,sj,0])
        ans = max(ans, bfs(HW, q))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#input
H, W = map(int, readline().split())
import numpy as np
S = np.array([readline() for _ in range(H)])

#output
import numpy as np
from collections import deque
INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int, input().split())
PATH = "."
WALL = "#"
z=0
# 迷路の配列を作成する。
maze=list()
for a in range(h):
 mazew=list()
 mazeh = input()
 for b in range(w):
  mazew.append(mazeh[b])
 maze.append(mazew)
for c in range(h):
 for d in range(w):
   # 地図上の未訪問地点を-1とする。
   # また、移動するごとに+1することで、スタート地点からの移動距離を保持する
  if maze[c][d]==WALL:
   break
  else:
   distance_visited = list()
   for l in range(h):
    distance_visited.append([-1] * w)
   # スタート地点を登録する。
   queue = deque([[c, d]])
   distance_visited[c][d] = 0
   while True:
    x,y = queue.popleft()
      # 現在地点の上下左右のマスを確認する。
    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
     new_x, new_y = x + i, y + j
       # それぞれのマスが移動できる場合、かつまだ移動したことが無い場合
     if new_x>=0 and new_x<=h-1 and new_y>=0 and new_y<=w-1:
      if maze[new_x][new_y] != WALL and distance_visited[new_x][new_y] == -1:
               # そのマスのスタートからの移動距離を設定し、またキューに登録する。
       distance_visited[new_x][new_y] = distance_visited[x][y] + 1
       queue.append([new_x, new_y])
       if distance_visited[new_x][new_y]>z:
        z=distance_visited[new_x][new_y]
    if queue==deque([]):
     break
print(z)

Submission status: Wrong Answer

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

r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    while que:
        i,j,k = que.popleft()
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        f[ti*w+tj] = k+1
                        que.append([ti,tj,k+1])
    return max(f)


res = 0
for i in range(h):
    for j in range(w):
        if s[i][j] ==".":
            tres = bfs(i,j)
            res = max(res,tres)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
grid = [[c for c in input()] for _ in range(N)]
mat = [[float('inf')]*(M*N) for _ in range(N*M)]

DX = [0, 0, 1, -1]
DY = [-1, 1, 0, 0]
for row in range(N):
    for col in range(M):
        if grid[row][col] == "#":
            continue
        for dx, dy in zip(DX, DY):
            if 0 <= row+dx < N and 0 <= col+dy < M:
                if grid[row+dx][col+dy] == "#":
                    continue
                mat[(row+dx)*M+col+dy][row*M+col] = 1
                mat[row*M+col][(row+dx)*M+col+dy] = 1
for k in range(N*M):
    for i in range(N*M):
        for j in range(N*M):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
ans = 0
for i in range(N*M):
    for j in range(N*M):
        if mat[i][j] != float('inf'):
            ans = max(ans, mat[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int, input().split())
PATH = "."
WALL = "#"
z=0
# 迷路の配列を作成する。
maze=list()
for a in range(h):
 mazew=list()
 mazeh = input()
 for b in range(w):
  mazew.append(mazeh[b])
 maze.append(mazew)
for c in range(h):
 for d in range(w):
   # 地図上の未訪問地点を-1とする。
   # また、移動するごとに+1することで、スタート地点からの移動距離を保持する
  distance_visited = list()
  for l in range(h):
   distance_visited.append([-1] * w)
   # スタート地点を登録する。
  queue = deque([[c, d]])
  distance_visited[c][d] = 0
  while True:
   x,y = queue.popleft()
      # 現在地点の上下左右のマスを確認する。
   for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
    new_x, new_y = x + i, y + j
       # それぞれのマスが移動できる場合、かつまだ移動したことが無い場合
    if new_x>=0 and new_x<=h-1 and new_y>=0 and new_y<=w-1:
     if maze[new_x][new_y] != WALL and distance_visited[new_x][new_y] == -1:
               # そのマスのスタートからの移動距離を設定し、またキューに登録する。
      distance_visited[new_x][new_y] = distance_visited[x][y] + 1
      queue.append([new_x, new_y])
      if distance_visited[new_x][new_y]>z:
       z=distance_visited[new_x][new_y]
   if queue==deque([]):
    break
print(z)

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int, input().split())
PATH = "."
WALL = "#"
z=0
# 迷路の配列を作成する。
maze=list()
for a in range(h):
 mazew=list()
 mazeh = input()
 for b in range(w):
  mazew.append(mazeh[b])
 maze.append(mazew)
 print(maze)
for c in range(h):
 for d in range(w):
   # 地図上の未訪問地点を-1とする。
   # また、移動するごとに+1することで、スタート地点からの移動距離を保持する
  distance_visited = list()
  for l in range(h):
   distance_visited.append([-1] * w)
   # スタート地点を登録する。
  queue = deque([[c, d]])
  distance_visited[c][d] = 0
  while True:
   x,y = queue.popleft()
      # 現在地点の上下左右のマスを確認する。
   for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
    new_x, new_y = x + i, y + j
       # それぞれのマスが移動できる場合、かつまだ移動したことが無い場合
    if new_x>=0 and new_x<=h-1 and new_y>=0 and new_y<=w-1:
     if maze[new_x][new_y] != WALL and distance_visited[new_x][new_y] == -1:
               # そのマスのスタートからの移動距離を設定し、またキューに登録する。
      distance_visited[new_x][new_y] = distance_visited[x][y] + 1
      queue.append([new_x, new_y])
      if distance_visited[new_x][new_y]>z:
       z=distance_visited[new_x][new_y]
   if queue==deque([]):
    break
print(z)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
grid = [[c for c in input()] for _ in range(N)]
mat = [[float('inf')]*(M*N) for _ in range(N*M)]

DX = [0, 0, 1, -1]
DY = [-1, 1, 0, 0]
for row in range(N):
    for col in range(M):
        if grid[row][col] == "#":
            continue
        for dx, dy in zip(DX, DY):
            if 0 <= row+dx < N and 0 <= col+dy < M:
                if grid[row+dx][col+dy] == "#":
                    continue
                mat[(row+dx)*M+col+dy][row*M+col] = 1
                mat[row*M+col][(row+dx)*M+col+dy] = 1
for k in range(N*M):
    for i in range(N*M):
        for j in range(N*M):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
ans = 0
for i in range(N*M):
    for j in range(N*M):
        if mat[i][j] != float('inf'):
            ans = max(ans, mat[i][j])
print(ans)

Submission status: Wrong Answer

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

di = [-1,0,1,0]
dj = [0,-1,0,1]

def BFS(i,j,que):
    count = 0
    for k in range(4):
        row = i + di[k]
        col = j + dj[k]
        if H > row >=0 and W >col >= 0 \
            and dist[row][col] == float('inf')\
                and S[row][col] != "#":
            
            que.append([row,col])
            dist[row][col] = dist[i][j] + 1
            count = dist[row][col]
    return count


path_max = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            break
        que = []
        stt = [i,j]
        que.append(stt)
        dist = [[float('inf') for ii in range(W)] for jj in range(H)]
        dist[i][j] = 0
        while que:
            idx = que[0]
            que.pop(0)
            count  = BFS(idx[0],idx[1],que)
            path_max = max(path_max,count)

print(path_max)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
grid = [[c for c in input()] for _ in range(N)]
mat = [[float('inf')]*(M*N) for _ in range(N*M)]

DX = [0, 0, 1, -1]
DY = [-1, 1, 0, 0]
for row in range(N):
    for col in range(M):
        if grid[row][col] == "#":
            continue
        for dx, dy in zip(DX, DY):
            if 0 <= row+dx < N and 0 <= col+dy < M:
                if grid[row+dx][col+dy] == "#":
                    continue
                mat[(row+dx)*M+col+dy][row*M+col] = 1
                mat[row*M+col][(row+dx)*M+col+dy] = 1
for k in range(N*M):
    for i in range(N*M):
        for j in range(N*M):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
ans = 0
for srow in range(N):
    for scol in range(M):
        if grid[srow][scol] == "#":
            continue
        for erow in range(N):
            for ecol in range(M):
                if grid[erow][ecol] == "#":
                    continue
                else:
                    ans = max(mat[srow*M+scol][erow*M+ecol], ans)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
M=[]
for i in range(h):
    s=input()
    H=[]
    for j in range(w):
        H.append(0) if s[j]=="." else H.append(1)
    M.append(H)

def make2D(x,y):
    aM=[]
    for i in range(h):
        aH=[]
        for j in range(w):
            aH.append(0) if M[i][j]==0 else aH.append(-1)
        aM.append(aH)
    return aM

from collections import deque
ans=0
for i in range(h):
    for j in range(w):
        print(i,j)
        if M[i][j]==1:
            continue
        aM=make2D(h,w)
        q=deque()
        q.append([i,j])
        while q:
            now=q.popleft()
            for a,b in ([0,1],[1,0],[0,-1],[-1,0]):
                if 0<=now[0]+a<h and 0<=now[1]+b<w:
                    if aM[now[0]+a][now[1]+b]==0 and (now[0]+a!=i or now[1]+b!=j):
                        aM[now[0]+a][now[1]+b]=aM[now[0]][now[1]]+1
                        q.append([now[0]+a,now[1]+b])
            if len(q)==0:
                break
        m=0
        for z in range(h):
            m=max(m,max(aM[z]))
        ans=max(ans,m)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
M=[]
for i in range(h):
    s=input()
    H=[]
    for j in range(w):
        H.append(0) if s[j]=="." else H.append(1)
    M.append(H)

def make2D(x,y):
    aM=[]
    for i in range(h):
        aH=[]
        for j in range(w):
            aH.append(0) if M[i][j]==0 else aH.append(-1)
        aM.append(aH)
    return aM

from collections import deque
ans=0
for i in range(h):
    for j in range(w):
        print(i,j)
        if M[i][j]==1:
            continue
        aM=make2D(h,w)
        q=deque()
        q.append([i,j])
        while q:
            now=q.popleft()
            for a,b in ([0,1],[1,0],[0,-1],[-1,0]):
                if 0<=now[0]+a<h and 0<=now[1]+b<w:
                    if aM[now[0]+a][now[1]+b]==0 and (now[0]+a!=i or now[1]+b!=j):
                        aM[now[0]+a][now[1]+b]=aM[now[0]][now[1]]+1
                        q.append([now[0]+a,now[1]+b])
            if len(q)==0:
                break
            print(aM)
        m=0
        for z in range(h):
            m=max(m,max(aM[z]))
        ans=max(ans,m)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
from collections import deque
di=[-1,0,1,0]
dj=[0,-1,0,1]
INF=1001001001
ans=0
for si in range(h):
    for sj in range(w):
        dist=[[INF]*w for _ in range(h)]
        dist[si][sj]=0
        q=deque([(si,sj)])
        while len(q)>0:
            i,j=q.popleft()
            for dir in range(4):
                ni=i+di[dir]
                nj=j+dj[dir]
                if(ni<0 or ni>=h or nj<0 or nj>=w): continue
                if(s[ni][nj]=='#'): continue
                if(dist[ni][nj]!=INF): continue
                q.append((ni,nj))
                dist[ni][nj]=dist[i][j]+1
        for i in range(h):
            for j in range(w):
                if dist[i][j]==INF: continue
                ans=max(ans,dist[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
inf=float("inf")
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))

def dist(a,b):
  if S[a][b]=="#":
    return 0
  else:
    ret=0
    D=[[inf]*(w+2) for _ in range(h+2)]
    D[a][b]=0
    Visit=[100*a+b]
    while Visit:
      v=Visit.pop()
      va,vb=v//100,v%100
      for dx,dy in d:
        if S[va+dx][vb+dy]=="#":
          continue
        elif D[va+dx][vb+dy]>D[va][vb]+1:
          Visit.append((va+dx)*100+(vb+dy))
          D[va+dx][vb+dy]=D[va][vb]+1
          ret=max(ret,D[va+dx][vb+dy])
    return ret
ans=0
for i in range(h):
  for j in range(w):
    ans=max(dist(i+1,j+1),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import copy
import numpy as np

def getmax(H2, W2, S):
    lp=True
    st=np.max(S)
    while lp:
        lp=False
        for i in range(1,H2-1):
            for j in range(1,W2-1):
                if (S[i][j]==0 and \
                    ( S[i-1][j]==st or \
                      S[i][j-1]==st or \
                      S[i+1][j]==st or \
                      S[i][j+1]==st)):
                    S[i][j]=st+1
                    lp=True
        st+=1
    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
    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)

    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:
H, W = map(int, input().split())
S = [0 for j in range(H)]
for i in range(H):
    S[i] = list(str(input()))
TF = [[False for i in range(W)] for j in range(H)]
first = [0,0]
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            TF[j][i] = True
        else:
            first = [j,i]
distance = [[0 for i in range(W)] for j in range(H)]
def bfs(s):
    Q = []
    TF[s[0]][s[1]] = True
    Q.append(s)
    while Q:
        v = Q.pop(0)
        next = [[v[0], v[1]+1], [v[0], v[1]-1],[v[0]+1, v[1]], [v[0]-1,v[1]]]
        for u in next:
            if u[0] >= 0 and u[0] <= H-1 and u[1] >= 0 and u[1] <= W-1:
                if TF[u[0]][u[1]] == False:
                    distance[u[0]][u[1]] = distance[v[0]][v[1]] + 1
                    TF[u[0]][u[1]] = True
                    Q.append(u)
bfs(first)
#print(first)
#print(distance)
maxd = 0
for j in range(H):
    for i in range(W):
        maxd = max(maxd,distance[j][i])
        if maxd == distance[j][i]:
            first = [j,i]

ddd = [[] for i in range(H*W+1)]
for j in range(H):
    for i in range(W):
        ddd[distance[j][i]].append([j,i])
for k in range(H*W,-1,-1):
    if len(ddd[k]) > 0:
        maxd = 0
        for first in ddd[k]:
            TF = [[False for i in range(W)] for j in range(H)]
            for j in range(H):
                for i in range(W):
                    if S[j][i] == '#':
                        TF[j][i] = True
            distance = [[0 for i in range(W)] for j in range(H)]
            bfs(first)
            #print(first)
            #print(distance)
            for j in range(H):
                for i in range(W):
                    maxd = max(maxd,distance[j][i])
        break
print(maxd)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [0 for j in range(H)]
for i in range(H):
    S[i] = list(str(input()))
TF = [[False for i in range(W)] for j in range(H)]
first = [0,0]
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            TF[j][i] = True
        else:
            first = [j,i]
distance = [[0 for i in range(W)] for j in range(H)]
def bfs(s):
    Q = []
    TF[s[0]][s[1]] = True
    Q.append(s)
    while Q:
        v = Q.pop(0)
        next = [[v[0], v[1]+1], [v[0], v[1]-1],[v[0]+1, v[1]], [v[0]-1,v[1]]]
        for u in next:
            if u[0] >= 0 and u[0] <= H-1 and u[1] >= 0 and u[1] <= W-1:
                if TF[u[0]][u[1]] == False:
                    distance[u[0]][u[1]] = distance[v[0]][v[1]] + 1
                    TF[u[0]][u[1]] = True
                    Q.append(u)
bfs(first)
#print(first)
#print(distance)
maxd = 0
for j in range(H):
    for i in range(W):
        maxd = max(maxd,distance[j][i])
        if maxd == distance[j][i]:
            first = [j,i]
TF = [[False for i in range(W)] for j in range(H)]
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            TF[j][i] = True
distance = [[0 for i in range(W)] for j in range(H)]
bfs(first)
#print(first)
#print(distance)
maxd = 0
for j in range(H):
    for i in range(W):
        maxd = max(maxd,distance[j][i])
print(maxd)

Submission status: Wrong Answer

Solution code:
import copy

def agent(maze,ori):
    global H
    global W

    hi=ori[0]
    wi=ori[1]
    root=[]
    if hi > 0:
        root.append([hi-1,wi])
    if hi < H-1:
        root.append([hi+1,wi])
    if wi > 0:
        root.append([hi,wi-1])
    if wi < W-1:
        root.append([hi,wi+1])
    
    for h,w in root:
        if maze[h][w]==".":
            maze[h][w]=maze[hi][wi]+1
            agent(maze,[h,w])
        elif maze[h][w]=="#":
            pass
        else:
            if maze[h][w] > maze[hi][wi]+1:
                maze[h][w]=maze[hi][wi]+1
                agent(maze,[h,w])


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

maze=[]
for h in range(H):
    maze_w=list(input())
    lis=[]
    for e in maze_w:
        if e =="#":
            lis.append(-1)
        else:
            lis.append(e)

    maze.append(lis)

maze_ori=copy.deepcopy(maze)
maxd=0

for h in range(H):
    for w  in range(W):
        maze=copy.deepcopy(maze_ori)
        if maze[h][w]==".":
            maze[h][w]=0
            agent(maze,[h,w])
            maxd=max(maxd,max(max(maze)))
        else:
            pass


print(maxd)