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:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
S = [input()[:-1] for _ in [0]*H]


def bfs(h, w, H, W):
    from collections import deque
    visited = [[False]*W for _ in range(H)]
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    q.append((0, h, w))
    while q:
        d, h, w = q.popleft()
        visited[h][w] = True

        for dh, dw in dirs:
            if 0 <= h+dh < H and 0 <= w+dw < W and not visited[h+dh][w+dw] and S[h][w] == '.':
                q.append((d+1, h+dh, w+dw))

    return d, h, w

ans = 1 << 30
for h, _S in enumerate(S):
    for w, s in enumerate(_S):
        if s == '.':
            d, h, w = bfs(h, w, H, W)
            if d < ans:
                ans = d

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
S = [input()[:-1] for _ in [0]*H]


def bfs(h, w, H, W):
    from collections import deque
    visited = [[False]*W for _ in range(H)]
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    q.append((0, h, w))
    while q:
        d, h, w = q.popleft()
        visited[h][w] = True

        for dh, dw in dirs:
            if 0 <= h+dh < H and 0 <= w+dw < W and not visited[h+dh][w+dw] and S[h][w] == '.':
                q.append((d+1, h+dh, w+dw))

    return d, h, w


for h, _S in enumerate(S):
    for w, s in enumerate(_S):
        if s == '.':
            _, h, w = bfs(h, w, H, W)
            break
ans, *_ = bfs(h, w, H, W)
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC151 D-Maze Master
import queue
H,W = map(int,input().split())
maze = [input() for _ in range(H)]
dydx = ((0,1),(0,-1),(1,0),(-1,0))

def reach(sy,sx):
    visited = [[0]*W for _ in range(H)]
    q = queue.Queue()
    q.put((sy,sx,0))
    while True:
        y,x,d = q.get()
        for dy,dx in dydx:
            if (0<=y+dy<H)&(0<=x+dx<W):
                if maze[y+dy][x+dx] == '#' or visited[y+dy][x+dx] == 1:
                    continue
                visited[y+dy][x+dx] = 1
                q.put((y+dy,x+dx,d+1))
        if q.empty():
            ans = d
            break
    return ans

d = -1
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        d = max(d,reach(sy,sx))
                
print(d)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())
    
dij=[-1,0,1,0,-1]
def update(i,j,x,d,q):
    if(d[i][j]!=-1):return
    d[i][j]=x
    q.append((i,j))
    ...
m=-1
for i in range(h):
    for j in range(w):
        if(s[i][j]=="#"):continue
        d=[[-1 for ii in range(w)] for jj in range(h)]
        q=[]
        update(i,j,0,d,q)
        while q:
            xy=q.pop(0)
            xx=xy[0]
            yy=xy[1]
            for k in range(4):
                ni=xx+dij[k]
                nj=yy+dij[k+1]
                if(ni<0 or ni>=h or nj<0 or nj>=w):continue
                if(s[ni][nj]=="#"):continue
                update(ni,nj,d[xx][yy]+1,d,q)
        m=max(max(max(d)),m)
print(m)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc151/tasks/abc151_d

from collections import deque

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


def bfs(sx, sy):
    count = [[0] * w for i in range(h)]
    check = [[0] * w for i in range(h)]
    d = deque([[sx, sy]])
    while d:
        x, y = d.popleft()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            if (
                not (0 <= tx < h)
                or not (0 <= ty < w)
                or maze[tx][ty] == "#"
                or check[tx][ty] == 1
            ):
                continue
            else:
                count[tx][ty] = count[x][y] + 1
                check[tx][ty] = 1
                d.append([tx, ty])

    result = 0
    for k in count:
        for l in k:
            result = max(result, l)
    return result


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

Submission status: Wrong Answer

Solution code:
import math
import itertools
from collections import deque
import bisect
import heapq

def IN(): return int(input())
def sIN(): return input()
def lIN(): return list(input())
def MAP(): return map(int,input().split())
def LMAP(): return list(map(int,input().split()))
def TATE(n): return [input() for i in range(n)]
ans = 0

def bfs(sx,sy,gx,gy):
    d = [[float("inf")] * w for i in range(h)]

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

    que = deque([])
    que.append((sx, sy))#スタート座標の記録
    d[sx][sy] = 0#スタートからスタートへの最短距離は0

    while que:#中身がなくなるまで
        p = que.popleft()
        if p[0] == gx and p[1] == gy:#ゴールなら終わり
            break
        for m in range(4):#現在地から4方向の移動を考える
            nx = p[0] + dx[m]
            ny = p[1] + dy[m]

            if 0 <= nx < h and 0 <= ny < w:
              if maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))#↑格子点からでない＆壁でない＆まだ通ってない
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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

for i in range(h):#sx座標指定0~h-1
  for j in range(w):#sy座標指定0~w-1
    if maze[i][j] == '#':
      continue
    else:
      for k in range(i,h):#gx座標指定
        for l in range(j,w):#gy座標指定
          if maze[k][l] == '.':
            ans = max(bfs(i,j,k,l),ans)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int, input().split())
S=[[str(c) for c in l.strip()] for l in sys.stdin]
  
def make_a(X,i,j):
  a=[0]*4
  if (i-1)>=0:
    a[0]=X[i-1][j]
  else:
    a[0]=H*W
  if (i+1)<=H-1:
    a[1]=X[i+1][j]
  else:
    a[1]=0
  if (j-1)>0:
    a[2]=X[i][j-1]
  else:
    a[2]=0
  if (j+1)<=W-1:
    a[3]=X[i][j+1]
  else:
    a[3]=0
  return a

def len_path(i,j):
  T=[[0]*W]*H
  for c in range(H):
    for d in range(W):
      if S[c][d]=="#":
        T[c][d]=H*W
  T[i][j]=1
  for s in range(H*W):
    for k in range(H):
      for l in range(W):
        if T[k][l]==0:
          if not min(make_a(T,k,l))==0:
            T[k][l]=make_a(T,k,l)+1
  L=T
  for c in range(H):
    for d in range(W):
      if T[c][d]==H*W:
        L[c][d]=0
  return max(max(L))-1

Q=[[0]*W]*H  
for i in range(H):
  for j in range(W):
    Q[i][j]=len_path(i,j)
print(max(max(Q)))

Submission status: Wrong Answer

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


def dfs(a,b):
    d = deque([])
    d.append([a,b])
    n = [1,0,-1,0]
    m = [0,1,0,-1]
    l = [[-1]*w for _ in range(h)]
    l[a][b]=0
    while len(d)!=0:
        #print(l)
        s = d.popleft()
        s1,s2 = s[0],s[1]
        for i in range(4):
            if 0<=s1+m[i] and s1+m[i]<=h-1 and 0<=s2+n[i] and s2+n[i]<=w-1:
                if sss[s1+m[i]][s2+n[i]]=="." and l[s1+m[i]][s2+n[i]]==-1:
                    d.append([s1+m[i],s2+n[i]])
                    l[s1+m[i]][s2+n[i]] = l[s1][s2]+1
    m = max(l)
    mm = max(m)
    return mm
t = 0
for i in range(w):
    for j in range(h):
      if sss[j][i]==".":
        t = max(t,dfs(j,i))
print(t)

Submission status: Wrong Answer

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


def dfs(a,b):
    d = deque([])
    d.append([a,b])
    n = [1,0,-1,0]
    m = [0,1,0,-1]
    l = [[-1]*w for _ in range(h)]
    l[a][b]=0
    while len(d)!=0:
        #print(l)
        s = d.popleft()
        s1,s2 = s[0],s[1]
        for i in range(4):
            if 0<=s1+m[i] and s1+m[i]<=h-1 and 0<=s2+n[i] and s2+n[i]<=w-1:
                if sss[s1+m[i]][s2+n[i]]=="." and l[s1+m[i]][s2+n[i]]==-1:
                    d.append([s1+m[i],s2+n[i]])
                    l[s1+m[i]][s2+n[i]] = l[s1][s2]+1
    m = max(l)
    mm = max(m)
    return mm
t = 0
for i in range(w):
    for j in range(h):
        t = max(t,dfs(j,i))
print(t)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
field = ['#' * (W+2)] * (H+2)
for i in range(1, H+1):
    field[i] = '#' + input() + '#'
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ans = 0

for i in range(1, H+1):
    for j in range(1, W+1):
        q = deque()
        q.append([i, j])
        dist = [[-1 for _ in range(W+2)] for _ in range(H+2)]
        dist[i][j] = 0
        dist_max = 0
        while len(q) != 0:
            current = q.popleft()
            x = current[0]
            y = current[1]

            for d in range(4):
                next_x = x + dx[d]
                next_y = y + dy[d]

                if field[next_x][next_y] == '#':
                    continue

                if dist[next_x][next_y] != -1:
                    continue

                q.append([next_x, next_y])
                dist[next_x][next_y] = dist[x][y] + 1
                dist_max = max(dist_max, dist[next_x][next_y])
        ans = max(ans, dist_max)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
h, w = map(int, input().split())
grid = []
scoresInit = [[500 for i in range(w)] for j in range(h)]

for i in range(h):
  grid.append(list(input()))
  for j in range(w):
    if grid[i][j] == "#":
      scoresInit[i][j] = -1

ans = 0
for i in range(h):
  for j in range(w):
    scores = copy.deepcopy(scoresInit)
    scores[i][j] = 0
    queue = [(i,j)]
    while queue != []:
      (x, y) = queue.pop(0)
      if x-1 >= 0 and grid[x-1][y] != "#" and scores[x-1][y] > scores[x][y]+1:
        scores[x-1][y] = scores[x][y]+1
        queue.append((x-1, y))
      if x+1 < h and grid[x+1][y] != "#" and scores[x+1][y] > scores[x][y]+1:
        scores[x+1][y] = scores[x][y]+1
        queue.append((x+1, y))
      if y-1 >= 0 and grid[x][y-1] != "#" and scores[x][y-1] > scores[x][y]+1:
        scores[x][y-1] = scores[x][y]+1
        queue.append((x, y-1))
      if y+1 < w and grid[x][y+1] != "#" and scores[x][y+1] > scores[x][y]+1:
        scores[x][y+1] = scores[x][y]+1
        queue.append((x, y+1))
    ansTmp = 0
    for k in range(len(scores)):
      ansTmp = max(ansTmp, max(scores[k]))
    ans = max(ans, ansTmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = []
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      wall.add((x, y))
    else:
      if x > 0 and x < W-1:
        if route[y][x-1] == '#' and route[y][x+1] == '#':
          continue
      if y > 0 and y < H-1:
        if route[y-1][x] == '#' and route[y+1][x] == '#':
          continue
      start.append((x, y))

score = -1
for xy in start:
  d = deque()
  d.append((xy[0],xy[1],0))
  step = 0
  already = set() | wall
  while len(d) > 0:
    now = d.popleft()
    already.add(now[:-1])
    step = now[2]+1
    x,y = now[0]-1, now[1]
    if (x, y) not in already and x >= 0:
      d.append((x, y, step))
    x, y = x+1, y-1
    if (x, y) not in already and y >= 0:
      d.append((x, y, step))
    x, y = x+1, y+1
    if (x, y) not in already and x < W:
      d.append((x, y, step))
    x, y = x-1, y+1
    if (x, y) not in already and y < H:
      d.append((x, y, step))
  score = max(step-1, score)
  
print(score)

Submission status: Wrong Answer

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

route = []
for _ in range(H):
  route.append(input())
  
dp = [[0 for _ in range(W)] for __ in range(H)]

wall = set()
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      wall.add((x, H-y-1))
      
start_list = []
start_list.append((0,0))
d = deque()
d.append((0,0))
already = set() | wall
score = -1
while len(d) > 0:
  now = d.popleft()
  already.add(now)
  move = True
  x,y = now[0]-1, now[1]
  if (x, y) not in already and x >= 0:
    d.append((x, y))
    move = False
  x, y = x+1, y-1
  if (x, y) not in already and y >= 0:
    d.append((x, y))
    move = False
  x, y = x+1, y+1
  if (x, y) not in already and x < W:
    d.append((x, y))
    move = False
  x, y = x-1, y+1
  if (x, y) not in already and y < H:
    d.append((x, y))
    move = False
  if move:
    start_list.append(now)

for xy in start_list:
  d = deque()
  d.append((xy[0],xy[1],0))
  step = 0
  already = set() | wall
  while len(d) > 0:
    now = d.popleft()
    already.add(now[:-1])
    step = now[2]+1
    x,y = now[0]-1, now[1]
    if (x, y) not in already and x >= 0:
      d.append((x, y, step))
    x, y = x+1, y-1
    if (x, y) not in already and y >= 0:
      d.append((x, y, step))
    x, y = x+1, y+1
    if (x, y) not in already and x < W:
      d.append((x, y, step))
    x, y = x-1, y+1
    if (x, y) not in already and y < H:
      d.append((x, y, step))
  score = max(step-1, score)
  
print(score)

Submission status: Wrong Answer

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

route = []
for _ in range(H):
  route.append(input())
  
dp = [[0 for _ in range(W)] for __ in range(H)]

already = set()
already.add((0,0))
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      already.add((x, H-y-1))

d = deque()
d.append((0,0,0))
while len(d) > 0:
  now = d.popleft()
  already.add(now[:-1])
  if now[:-1] == (W-1, H-1):
    print(now[-1])
    break
  step = now[2]+1
  x,y = now[0]-1, now[1]
  if (x, y) not in already and x >= 0:
    d.append((x, y, step))
  x, y = x+1, y-1
  if (x, y) not in already and y >= 0:
    d.append((x, y, step))
  x, y = x+1, y+1
  if (x, y) not in already and x < W:
    d.append((x, y, step))
  x, y = x-1, y+1
  if (x, y) not in already and y < H:
    d.append((x, y, step))

Submission status: Wrong Answer

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

route = []
for _ in range(H):
  route.append(input())
  
dp = [[0 for _ in range(W)] for __ in range(H)]

already = set()
already.add((0,0))
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      already.add((x, H-y-1))

d = deque()
d.append((0,0,0))
while len(d) > 0:
  now = d.popleft()
  if now[:-1] == (W-1, H-1):
    print(now[-1])
    break
  step = now[2]+1
  x,y = now[0]-1, now[1]
  if (x, y) not in already and x >= 0:
    d.append((x, y, step))
  x, y = x+1, y-1
  if (x, y) not in already and y >= 0:
    d.append((x, y, step))
  x, y = x+1, y+1
  if (x, y) not in already and x < W:
    d.append((x, y, step))
  x, y = x-1, y+1
  if (x, y) not in already and y < H:
    d.append((x, y, step))

Submission status: Wrong Answer

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

route = []
for _ in range(H):
  route.append(input())
  
dp = [[0 for _ in range(W)] for __ in range(H)]

already = set()
already.add((0,0))
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      already.add((x, y))

d = deque()
d.append((0,0,0))
while len(d) > 0:
  now = d.popleft()
  if now[:-1] == (W-1, H-1):
    print(now[-1])
    break
  step = now[2]+1
  x,y = now[0]-1, now[1]
  if (x, y) not in already and x >= 0:
    d.append((x, y, step))
  x, y = x+1, y-1
  if (x, y) not in already and y >= 0:
    d.append((x, y, step))
  x, y = x+1, y+1
  if (x, y) not in already and x < W:
    d.append((x, y, step))
  x, y = x-1, y+1
  if (x, y) not in already and y < H:
    d.append((x, y, step))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def bfs(sx, sy):
    que = deque([])
    que.append((sx, sy))
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = [[-1] * w for i in range(h)]
    d[sy][sx] = 0
    while que:
        s = que.popleft()
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and d[ny][nx] == -1:
                que.append((nx, ny))
                d[ny][nx] = d[s[1]][s[0]] + 1
    
    tmp = 0
    for i in range(h):
        for j in range(w):
            tmp = max(tmp, d[i][j])
    
    return tmp

ans = 0
for i in range(w):
    for j in range(h):
        ans = max(ans, bfs(i, j))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def bfs(sx, sy):
    que = deque([])
    que.append((sx, sy))
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = [[-1] * w for i in range(h)]
    d[sy][sx] = 0
    while que:
        s = que.popleft()
        for i in range(4):
            nx = s[0] + dx[i]
            ny = s[1] + dy[i]
            
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and d[ny][nx] == -1:
                que.append((nx, ny))
                d[ny][nx] = d[s[1]][s[0]] + 1
    return d[s[1]][s[0]]

ans = 0
for i in range(w):
    for j in range(h):
        ans = max(ans, bfs(i, j))

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
	from collections import deque

	h, w = map(int, input().split())
	s = [input() for i in range(h)] # [[input()] for ...] は誤答 （文字列も配列であることを考えると3重配列になっちゃう） 
	directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] # [y軸, x軸]
	ans = 0

	for sh in range(h): # start hight
		for sw in range(w):
			if s[sh][sw] == "#":
				continue
			distance = [[-1 for j in range(w)] for i in range(h)]
			distance[sh][sw] = 0
			q = deque([[sh, sw]]) # 1段目の[]はdequeの引数がイテラブルであるため、2段目の[]はy軸x軸のペアを表現するため

			while q:
				y, x = q.popleft() # アンパックしてくれる
				for i, j in directions:
					ny, nx = y+i, x+j

					# エリア内判定
					if not ((0 <= ny < h) and (0 <= nx < w)):
						continue
					# 壁判定
					elif s[ny][nx] == "#":
						continue
					# 訪問済み判定
					elif distance[ny][nx] != -1:
						continue

					distance[ny][nx] = distance[y][x] + 1
					q.append([ny, nx]) # q.append([[ny, nx]]) は誤答
			ans = max(ans, max(max(distance)))
	print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
# 距離をキューから取り出してから更新する
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W

    d = deque()
    d.append((x, y, 0))
    while(len(d) != 0):
        h, w, distance = d.popleft()
        if c[h][w] == '.' and dist[h][w] == -1:
            dist[h][w] = distance
            if h != 0 and c[h-1][w] == '.':
                # if dist[h-1][w] == -1:
                d.append((h-1, w, distance+1))
            if h != H-1 and c[h+1][w] == '.':
                # if dist[h+1][w] == -1:
                d.append((h+1, w, distance+1))
            if w != 0 and c[h][w-1] == '.':
                # if dist[h][w-1] == -1:
                d.append((h, w-1, distance+1))
            if w != W-1 and c[h][w+1] == '.':
                # if dist[h][w+1] == -1:
                d.append((h, w+1, distance+1))
    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()
 
from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    visited = [False] * (H * W)
    q = deque([(start[0], start[1], 0)])
    max_d = 0
    while q:
        (i, j, d) = q.popleft()
        max_d = max(max_d, d)
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                visited[(i + dy) * W + j + dx] = True
                q.append((i + dy, j + dx, d + 1))
    return max_d
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
# 距離をキューから取り出してから更新する
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    #dist[x][y] = 0
    d = deque()
    d.append((x, y, 0))
    while(len(d) != 0):
        h, w, distance = d.popleft()
        if c[h][w] == '.' and dist[h][w] == -1:
            dist[h][w] = distance
            if h != 0 and c[h-1][w] == '.':
                if dist[h-1][w] == -1:
                    d.append((h-1, w, distance+1))
            if h != H-1 and c[h+1][w] == '.':
                if dist[h+1][w] == -1:
                    d.append((h+1, w, distance+1))
            if w != 0 and c[h][w-1] == '.':
                if dist[h][w-1] == -1:
                    d.append((h, w-1, distance+1))
            if w != W-1 and c[h][w+1] == '.':
                if dist[h][w+1] == -1:
                    d.append((h, w+1, distance+1))
    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
# 距離をキューから取り出してから更新する
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[x][y] = 0
    d = deque()
    d.append((x, y, 0))
    while(len(d) != 0):
        h, w, distance = d.popleft()
        if c[h][w] == '.':
            if h != 0 and c[h-1][w] == '.':
                if dist[h-1][w] == -1:
                    dist[h-1][w] = distance+1
                    d.append((h-1, w, distance+1))
            if h != H-1 and c[h+1][w] == '.':
                if dist[h+1][w] == -1:
                    dist[h+1][w] = distance+1
                    d.append((h+1, w, distance+1))
            if w != 0 and c[h][w-1] == '.':
                if dist[h][w-1] == -1:
                    dist[h][w-1] = distance+1
                    d.append((h, w-1, distance+1))
            if w != W-1 and c[h][w+1] == '.':
                if dist[h][w+1] == -1:
                    dist[h][w+1] = distance+1
                    d.append((h, w+1, distance+1))

    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
# 距離をキューから取り出してから更新する
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[x][y] = 0
    d = deque()
    d.append((x, y, dist[x][y]))
    while(len(d) != 0):
        h, w, distance = d.popleft()
        if c[h][w] == '.':
            if h != 0 and c[h-1][w] == '.':
                if dist[h-1][w] == -1:
                    dist[h-1][w] = distance+1
                    d.append((h-1, w, dist[h-1][w]))
            if h != H-1 and c[h+1][w] == '.':
                if dist[h+1][w] == -1:
                    dist[h+1][w] = distance+1
                    d.append((h+1, w, dist[h+1][w]))
            if w != 0 and c[h][w-1] == '.':
                if dist[h][w-1] == -1:
                    dist[h][w-1] = distance+1
                    d.append((h, w-1, dist[h][w-1]))
            if w != W-1 and c[h][w+1] == '.':
                if dist[h][w+1] == -1:
                    dist[h][w+1] = distance+1
                    d.append((h, w+1, dist[h][w+1]))

    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
H, W = map(int, input().split())
# 縦H,横W
c = [None]*H
for i in range(H):
    c[i] = input()
# print(c)


def BFS(x, y):
    dist = [-1]*H
    for k in range(H):
        dist[k] = [-1]*W
    dist[x][y] = 0
    d = deque()
    d.append((x, y, dist[x][y]))
    while(len(d) != 0):
        h, w, distance = d.popleft()
        if c[h][w] == '.':
            if h != 0 and dist[h-1][w] == -1:  # 上
                if c[h-1][w] == '.':
                    dist[h-1][w] = distance+1
                    d.append((h-1, w, dist[h-1][w]))

            if h != H-1 and dist[h+1][w] == -1:  # 下
                if c[h+1][w] == '.':
                    dist[h+1][w] = distance+1
                    d.append((h+1, w, dist[h+1][w]))

            if w != 0 and dist[h][w-1] == -1:  # 左
                if c[h][w-1] == '.':
                    dist[h][w-1] = distance+1
                    d.append((h, w-1, dist[h][w-1]))

            if w != W-1 and dist[h][w+1] == -1:  # 右
                if c[h][w+1] == '.':
                    dist[h][w+1] = distance+1
                    d.append((h, w+1, dist[h][w+1]))

    # print(dist)
    return dist


ans = -1
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = max(max(BFS(i, j)))
            ans = max(ans, tmp)
print(ans)