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 copy
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
def check(s,t):
    if (0 <= s <= w - 1) and (0 <= t <= h - 1):
        return True
    else:
        return False
def bfs(x, y, cost):
    if check(x,y):
        if grid[y][x] != "#":
            if cost < graph[y][x]:
                graph[y][x] = cost
                bfs(x+1,y,cost+1)
                bfs(x,y+1,cost+1)
                bfs(x-1,y,cost+1)
                bfs(x,y-1,cost+1)
global ans
ans = 0
inf = 50
for i in range(h):
    for j in range(w):
        graph = [[inf for p in range(w)] for q in range(h)]
        bfs(i,j,0)
        g_max = 0
        for p in range(h):
            for q in range(w):
                if graph[p][q] != inf:
                    g_max = max(g_max, graph[p][q])
        ans = max(g_max, ans)
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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


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

    head = None
    for y in range(h):
        for x in range(w):
            if not walls[y][x]:
                head = (x, y)
                break
        if head:
            break

    passed = [[False]*w for _ in range(h)]

    count = 0
    tail = head

    Q = deque([head+(0,)])

    while Q:
        x, y, c = Q.popleft()
        if walls[y][x] or passed[y][x]:
            continue

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

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

    Q.append(tail+(0,))
    passed = [[False]*w for _ in range(h)]

    count = 0

    while Q:
        x, y, c = Q.popleft()
        if walls[y][x] or passed[y][x]:
            continue

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

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

    return str(count)


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	global Y
	global X
	global q
	global maps
	global maze

	H,W = inputMap()
	Y = H
	X = W
	mapmap = []
	ser = []
	for i in range(H):
		tmp = input()
		tmp = tmp[:-1]
		mapmap.append(tmp)

		for j,val in enumerate(tmp):
			if val == ".":
				ser.append((i,j))

	maps = [[-1 for _ in range(X)] for _ in range(Y)]
	maze = mapmap
	q = Queue()

	tmp = ser[0]
	s,e = tmp
	ans = serchs(s,e,s,e)

	ans = 0
	for i in maps:
		tmp = max(i)
		if tmp > ans:
			ans = tmp
			
	print(ans)

def serchs(start_y,start_x, goal_y,goal_x):
	q.enqueue((start_y, start_x))
	maps[start_y][start_x] = 0
	run()

	return(maps[goal_y][goal_x])

def run():
	while True:
		tmp = q.dequeue()
		if tmp == None:
			return

		y, x = tmp

		counts = maps[y][x] + 1
		if not y <= 0 and maps[y-1][x] == -1 and maze[y-1][x] == ".":
			q.enqueue((y-1, x))
			maps[y-1][x] = counts
		if not x <= 0 and maps[y][x-1] == -1 and maze[y][x-1] == ".":
			q.enqueue((y, x-1))
			maps[y][x-1] = counts
		if not y >= Y-1 and maps[y+1][x] == -1 and maze[y+1][x] == ".":
			q.enqueue((y+1, x))
			maps[y+1][x] = counts
		if not x >= X-1 and maps[y][x+1] == -1 and maze[y][x+1] == ".":
			q.enqueue((y, x+1))
			maps[y][x+1] = counts

class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

    print(mx)

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

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque

def search(h, w, pre_h, pre_w):
    can = []
    if h > 0:
        can.append((h-1, w))
    if h < H-1:
        can.append((h+1, w))
    if w > 0:
        can.append((h, w-1))
    if w < W-1:
        can.append((h, w+1))
    res = []
    for h, w in can:
        if S[h][w]=='.' and (h, w) != (pre_h, pre_w):
            res.append((h, w))
    return res

def bfs(h, w):
    d = [[float('inf') for _ in range(W)] for _ in range(H)]
    d[h][w] = 0
    pre_h, pre_w = h, w
    adj_list = search(h, w, pre_h, pre_w)
    open_list = deque([])
    closed_list = []
    closed_list = set(closed_list)
    for adj in adj_list:
        open_list.append((adj[0], adj[1], pre_h, pre_w))
    cnt = 0
    while True:
        if len(open_list) == 0:
            break
        h, w, pre_h, pre_w = open_list.popleft()
        closed_list.add((h, w, pre_h, pre_w))
        d[h][w] = min(d[h][w], d[pre_h][pre_w] + 1)
        adj_list = search(h, w, pre_h, pre_w)
        for adj in adj_list:
            if (adj[0], adj[1], h, w) in closed_list:
                continue
            open_list.append((adj[0], adj[1], h, w))

    res = 0
    global dh
    global dw
    res = 0
    for h in range(H):
        for w in range(W):
            if not d[h][w] == float('inf'):
                if res < d[h][w]:
                    dh, dw = h, w
                    res = d[h][w]
    return res

def bounday():
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                return False
    return True

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

dh, dw = 0, 0

if __name__ == "__main__":

    if bounday():
        print(H+W-2)
        exit(0)

    h, w = 0, 0
    bfs(0, 0)
    print(bfs(dh, dw))

Submission status: Wrong Answer

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

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

                visited[x][y] = 1
                

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])


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

sy, sx, gy, gx = 3, 1, 1, 5

maze = ["#"*(W+2)]
for i in range(H):
    tmp = "#"
    tmp += input()
    tmp += "#"
    maze.append(tmp)
maze.append("#"*(W+2))
    
#for i in range(H+2):
#    print(maze[i])

max_bfs = 0
for sy in range(1, H+2):
    for sx in range(1, W+2):
        for gy in range(1, H+2):
            for gx in range(1, W+2):
                if maze[sy][sx] == "." and maze[gy][gx] == ".":
                    sharp_count_1 = 0
                    sharp_count_2 = 0
                    if maze[sy-1][sx] == "#":
                        sharp_count_1 += 1
                    if maze[sy][sx-1] == "#":
                        sharp_count_1 += 1    
                    if maze[sy+1][sx] == "#":
                        sharp_count_1 += 1    
                    if maze[sy][sx+1] == "#":
                        sharp_count_1 += 1
                    if maze[gy-1][gx] == "#":
                        sharp_count_2 += 1
                    if maze[gy][gx-1] == "#":
                        sharp_count_2 += 1
                    if maze[gy+1][gx] == "#":
                        sharp_count_2 += 1
                    if maze[gy][gx+1] == "#":
                        sharp_count_2 += 1
                        
                    if sharp_count_1 >= 2 and sharp_count_2 >= 2:
                        visited = [[-1]*(W+2) for j in range(H+2)]
                        tmp_bfs = bfs(maze, visited, sy, sx, gy, gx)
                        if tmp_bfs > max_bfs:
                            max_bfs = tmp_bfs
                
print(max_bfs)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
memo = [[False]*(W+2) for _ in range(H+2)]
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    for ey in range(sy, H+1):
      for ex in range(1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
        memo[ey][ex] = True
    memo[sy][sx] = True
print(Ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

maze = [list(input()) for _ in range(h)]
#print(maze)
ans = 0
def solve(sx, sy, gx, gy):
    reached = [[0 for _ in range(w)] for _ in range(h)]
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]    
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "#":
                continue
            if reached[next_x][next_y] != 0:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    return reached[gx][gy]

for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                if maze[i][j] == "." and maze[k][l] == ".":
                    res = solve(i, j, k, l)
                    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

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

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

    comb = itertools.combinations(tuple(range(20)), 2)
    mx = -1

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

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

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

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

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

    print(mx)

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

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())                                   # ノードの訪問済みフラグ
a = [['#']+[i for i in input()]+['#'] for j in range(H)]
a = [['#' for i in range(W+2)]]+a+[['#' for i in range(W+2)]]
b=[x for x in a if "." in x] # "#"が入っている行のみ抽出した2次元配列 右辺の意味合いとしては，「aの各行を代入したxについて，もしx内に#があればリストに加える」
c=zip(*[y for y in zip(*b) if "." in y]) # yは各列を示しており，"#"が入っている列のみを抽出した2次元配列
graph = []
for d in c:
  graph.append(list(d))
H = len(graph)
W = len(graph[0])
for i in range(H):
  graph[i].append('#')
  graph[i].insert(0,'#')
graph = [['#' for i in range(W+2)]] + graph + [['#' for i in range(W+2)]]
import copy
# dfs:ノードvについて、エッジで接続した未訪問のノードを浅いほうから訪問(LILO)
def dfs(start,goal):
    visited = [[False for i in range(W+2)] for j in range(H+2)]
    step = 0
    queue = [start]
    queue_2 = []
    while len(queue) != 0:
        step += 1
        for now in queue:
          visited[now[0]][now[1]] = True
          for next in [[1,0],[0,1],[-1,0],[0,-1]]:
            if visited[now[0]+next[0]][now[1]+next[1]] == True:continue
            if graph[now[0]+next[0]][now[1]+next[1]] == '#':continue
            if [now[0]+next[0],now[1]+next[1]] == goal:return step
            if [now[0]+next[0],now[1]+next[1]] in queue_2:continue
            queue_2.append([now[0]+next[0],now[1]+next[1]])
        queue.clear()
        queue = copy.deepcopy(queue_2)
        queue_2.clear()
    return -1
hidariue = [1,1]
migiue = [1,W]
hidarisita = [H,1]
migisita = [H,W]
while True:
  if graph[hidariue[0]][hidariue[1]]=='#':
    hidariue[0]+=1
  elif graph[migiue[0]][migiue[1]]=='#':
    migiue[0]+=1
  elif graph[hidarisita[0]][hidarisita[1]]=='#':
    hidarisita[0]-=1
  elif graph[migisita[0]][migisita[1]]=='#':
    migisita[0]-=1
  else:
    break

a = dfs(hidariue,hidarisita)
b = dfs(hidariue,migiue)
c = dfs(hidariue,migisita)
d = dfs(hidarisita,migiue)
e = dfs(hidarisita,migisita)
f = dfs(migiue,migisita)
print(max(a,b,c,d,e,f))

Submission status: Wrong Answer

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

for i in range(H):
  row = []
  for j in range(W):
    count = 0
    if S[i][j] == '#':
      row.append(10)
    else:
      if i != 0 and S[i-1][j] == '.':
        count += 1
      if i != (H-1) and S[i+1][j] == '.':
        count += 1
      if j != 0 and S[i][j-1] == '.':
        count += 1
      if j != (W-1) and S[i][j+1] == '.':
        count += 1
      row.append(count)
  data.append(row)
min = min([flatten for inner in data for flatten in inner])
startList = []
for i in range(H):
  for j in range(W):
    if data[i][j] == min:
      startList.append([i, j])
import random
now = startList[0]
end = startList[-1]
turn = 0
while(now != end):
  min = 10
  i, j = now[0], now[1]
  if i != 0 and data[i-1][j] != 10 and data[i-1][j] < min:
    min = data[i-1][j]
    next = [i-1, j]
  if i != (H-1) and data[i+1][j] != 10 and data[i+1][j] < min:
    min = data[i+1][j]
    next = [i+1, j]
  if j != 0 and data[i][j-1] != 10 and data[i][j-1] < min:
    min = data[i][j-1] 
    next = [i, j-1]
  if j != (W-1) and data[i][j+1] != 10 and data[i][j+1] < min:
    min = data[i][j+1]
    next = [i, j+1]
  data[i][j] = 10
  now = next
  turn += 1
print(turn)

Submission status: Wrong Answer

Solution code:
h,w = list(map(int, input().split()))
s = []
move_time = 0
for _ in range(h):
    s.append(input())

def dfs(i, j, reccursive_time,i_map):
    if s[i][j] == "#" or i_map[i*w + j] == 1:
        return reccursive_time -1

    i_map[i*w + j] = 1
    tmp1 = 0
    tmp2 = 0
    tmp3 = 0
    tmp4 = 0

    if i != 0:
        tmp1 = dfs(i-1, j, reccursive_time+1,i_map)
    if i != h-1:
        tmp2 = dfs(i+1, j, reccursive_time+1,i_map)
    if j != 0:
        tmp3 = dfs(i, j-1, reccursive_time+1,i_map)
    if j != w-1:
        tmp4 = dfs(i-1, j, reccursive_time+1,i_map)

    return max(tmp1,tmp2,tmp3,tmp4,reccursive_time)



for i in range(h):
    for j in range(w):
        imap = [0]*w*h
        tmp = dfs(i ,j ,0 ,imap)
        if move_time < tmp:
            move_time = tmp

print(move_time)

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

    print(mx)

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

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
grid=[None]*H
# 仮のスタート
sx,sy=-1,-1
found=False
for i in range(H):
  grid[i]=input()
  if not found:
    for j in range(len(grid[i])):
      if grid[i][j]==".":
        sy=i
        sx=j
        found=True
        
from collections import deque
stack=deque()
# y,x,そこまでの距離
stack.append([sy,sx,0])
INF=10**9
seen=[[INF for j in range(W)] for i in range(H)]

while stack:
  node=stack.popleft()
  y=node[0]
  x=node[1]
  dist=node[2]
  if grid[y][x]=="#":
    continue
  if seen[y][x]<=dist:
    continue
  seen[y][x]=dist
  if y-1>=0:
    stack.append([y-1,x,dist+1])
  if y+1<H:
    stack.append([y+1,x,dist+1])
  if x-1>=0:
    stack.append([y,x-1,dist+1])
  if x+1<W:
    stack.append([y,x+1,dist+1])

longest=0
longestY=-1
longestX=-1
for i in range(H):
  for j in range(W):
    if grid[i][j]==".":
      if seen[i][j]>longest:
        longest=seen[i][j]
        longestY=i
        longestX=j
        
stack=deque()
stack.append([longestY,longestX,0])
seen=[[INF for j in range(W)] for i in range(H)]
while stack:
  node=stack.popleft()
  y=node[0]
  x=node[1]
  dist=node[2]
  if grid[y][x]=="#":
    continue
  if seen[y][x]<=dist:
    continue
  seen[y][x]=dist
  if y-1>=0:
    stack.append([y-1,x,dist+1])
  if y+1<H:
    stack.append([y+1,x,dist+1])
  if x-1>=0:
    stack.append([y,x-1,dist+1])
  if x+1<W:
    stack.append([y,x+1,dist+1])

ans=0
for i in range(H):
  for j in range(W):
    if grid[i][j]==".":
      if seen[i][j]>ans:
        ans=seen[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import copy

def sgmake(lst):
    for i in range(H):
        for j in range(W):
            if i != j:
                lst.append((i, j))

def bfs(s1,s2, g1, g2):
    cs = copy.deepcopy(s)
    cs[g1][g2] = 'g'
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    cs[s1][s2] = 0
    gx = 'Fail'
    gy = 'Fail'
    while queueX.empty() == False:
        x = queueX.get()
        y = queueY.get()

        for i in range(4):
            nextX = x + moveR[i]
            nextY = y + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and cs[nextX][nextY] != '#'\
                and cs[nextX][nextY] == '.':
                cs[nextX][nextY] = cs[x][y] + 1
                queueX.put(nextX)
                queueY.put(nextY)

            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and cs[nextX][nextY] == 'g':
                cs[nextX][nextY] = cs[x][y] + 1
                gx = nextX
                gy = nextY
                break

    if gx != False:
        return cs[gx][gy]
    else:
        return 0

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

moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]
ans = 0
slst = []
glst = []
sgmake(slst)
sgmake(glst)
for i in slst:
    for j in glst:
        if i != j:
            if s[i[0]][i[1]] != '#' and s[j[0]][j[1]] != '#':
                tmp = bfs(i[0], i[1], j[0], j[1])
                ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

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

maze = [list(input()) for _ in range(h)]
#print(maze)
ans = 0
def solve(sx, sy, gx, gy):
    reached = [[0 for _ in range(w)] for _ in range(h)]
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]    
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "#":
                continue
            if reached[next_x][next_y] != 0:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    return reached[gx][gy]

for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                if maze[i][j] == "." and maze[k][l] == ".":
                    res = solve(i, j, k, l)
                    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

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

def dfs(y, x, y0, x0, d=0):
    if y < 0 or y >= H or x < 0 or x >= W:
        return

    if seen[y][x]:
        return

    seen[y][x] = True

    if maze[y][x] == "#":
        return

    if d > dist[y0][x0]:
        dist[y0][x0] = d

    dfs(y, x+1, y0, x0, d+1)
    dfs(y+1, x, y0, x0, d+1)
    dfs(y, x-1, y0, x0, d+1)
    dfs(y-1, x, y0, x0, d+1)


dist = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        seen = [[False] * W for _ in range(H)]
        dfs(i, j, i, j)

ans = 0
for row in dist:
    for d in row:
        ans = max(ans, d)

print(ans)