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: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
    
from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 最大の地点を
def dfs(sx, sy, gx, gy):
    que = deque()
    # 各点までの最長距離の配列
    d = [[-1 for _ in range(W)] for _ in range(H)]
    que.append([sx, sy])
    d[sx][sy] = 0
    
    while(len(que) != 0):
        front = que.popleft()
        if (front[0] == gx and front[1] == gy):
            break
        for i in range(4):
            nx = front[0] + dx[i]
            ny = front[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W):
                if maze[nx][ny] != "#" and d[nx][ny] == -1:
                    que.append([nx, ny])
                    d[nx][ny] = d[front[0]][front[1]] + 1
                else:
                    continue
            else:
                continue
    return d[gx][gy]

import itertools

ans = []
l1 = [(s1, s2) for s1 in range(H) for s2 in range(W)]
p = itertools.product(l1, l1)

for v in p:
    if v[0][0] == v[1][0] and v[0][1] == v[1][1]:
        continue
    if maze[v[0][0]][v[0][1]] == "#" or maze[v[1][0]][v[1][1]] == "#":
        continue
    ans.append(dfs(v[0][0], v[0][1], v[1][0], v[1][1]))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
    
from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 最大の地点を
def dfs(sx, sy, gx, gy):
    que = deque()
    # 各点までの最長距離の配列
    d = [[-1 for _ in range(W)] for _ in range(H)]
    que.append([sx, sy])
    d[sx][sy] = 0
    
    while(len(que) != 0):
        front = que.popleft()
        if (front[0] == gx and front[1] == gy):
            break
        for i in range(4):
            nx = front[0] + dx[i]
            ny = front[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W):
                if maze[nx][ny] != "#" and d[nx][ny] == -1:
                    que.append([nx, ny])
                    d[nx][ny] = d[front[0]][front[1]] + 1
                else:
                    continue
            else:
                continue
    return d[gx][gy]

import itertools

ans = []
l1 = [(s1, s2) for s1 in range(H) for s2 in range(W)]
p = itertools.product(l1, l1)

for v in p:
    if maze[v[0][0]][v[0][1]] == "#" or maze[v[1][0]][v[1][1]] == "#":
        continue
    ans.append(dfs(v[0][0], v[0][1], v[1][0], v[1][1]))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
 
s = []
for i in range(h):
    line = input()
    s.append(line)
 
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[1<<10 for x in range(w)] for y in range(h)]
 
        stack = []
        stack.append((i, j))
        d[i][j] = 0
        while stack:
            y, x = stack.pop()
            if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                d[y-1][x] = d[y][x] + 1
                stack.append((y-1, x))
            if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                d[y][x+1] = d[y][x] + 1
                stack.append((y, x+1))
            if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                d[y+1][x] = d[y][x] + 1
                stack.append((y+1, x))
            if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                d[y][x-1] = d[y][x] + 1
                stack.append((y, x-1))
        ma = 0
        for y in range(h):
            for x in range(w):
                if d[y][x] != 1024 and d[y][x] > ma:
                    ma = d[y][x]

        ans.append(ma)
ans.sort()
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def a():
    H,W = map(int,input().split())
    S = ["" for _ in range(H)]
    for _ in range(H):
        S[_] = input()
    b = lambda n:S[n//W][n%W] == '.'
    u = map(lambda n:(n%W,n//W),filter(b,range(H*W)))

    def bfs(root):
        depth = [[-1]*W for _ in range(H)]
        q = deque()
        q.append((root,0))
        while q:
            r,d = q.popleft()
            x,y = r
            depth[y][x] = d
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                dx += x
                dy += y
                if 0 <= dx < W and 0 <= dy < H and depth[dy][dx] == -1 and S[dy][dx] == ".":
                    q.append(((dx,dy),d+1))
        return depth
    
    p = []
    for x in map(bfs,u):
        o = []
        for y in x:
            o.append(max(y))
        p.append(max(o))
    print(max(p))


a()

Submission status: Time Limit Exceeded

Solution code:
import collections


def search(data, w, h, start, end):
    maps = [[0] * w for i in range(h)]
    move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    que = collections.deque([(start[1], start[0])])
    maps[start[1]][start[0]] = 0
    while que:
        y, x = que.popleft()
        num = maps[y][x]
        for m in move:
            if 0 <= y+m[0] < h and 0 <= x+m[1] < w:
                if maps[y+m[0]][x+m[1]] != 0:
                    continue
                if data[y+m[0]][x+m[1]] == '#':
                    continue
                elif data[y+m[0]][x+m[1]] == '.':
                    maps[y+m[0]][x+m[1]] = num+1
                    que.append((y+m[0], x+m[1]))
    return maps[end[1]][end[0]]


def main():
    h, w = map(int, input().split())
    data = []
    for i in range(h):
        tmp = input()
        data.append([j for j in tmp])

    ans = 0
    for i in range(h*w-1):
        for j in range(i+1, h*w):
            if data[i//w][i % w] == '.' and data[j//w][j % w] == '.':
                ans = max(search(data, w, h, (i % w, i//w), (j % w, j//w)), ans)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def bfs(s1,s2):
    global ans
    cs = copy.deepcopy(s)
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    cs[s1][s2] = 0
    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
                ans = max(ans, cs[nextX][nextY])
                queueX.put(nextX)
                queueY.put(nextY)

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
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            bfs(i, j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
S = np.array([list(readline().decode('utf-8').rstrip()) for _ in range(H)])


def adjacent_4(h, w):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw

        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def bfs(S, visited, h, w, cnt):

    que = deque()
    for adj in adjacent_4(h, w):
        que.append([adj, cnt])

    while len(que) != 0:
        target, cnt_ = que.popleft()
        if (visited[target[0]][target[1]] !=
                -1) | (S[target[0]][target[1]] == '#'):
            continue
        visited[target[0]][target[1]] = cnt_
        for adj in adjacent_4(target[0], target[1]):
            que.append([adj, cnt_ + 1])


ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        visited = np.full(S.shape, -1)
        visited[h][w] = 0
        bfs(S, visited, h, w, 1)
        ans = max(ans, visited.max())

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
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)
ans = 0
inf = 400
for i in range(h):
    for j in range(w):
        graph = [[inf for _ in range(w)] for _ in range(h)]
        bfs(j,i,0)
        for p in range(h):
            for q in range(w):
                if graph[p][q] < inf:
                    ans = max(ans, graph[p][q])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)
ans = 1
inf = 1000000000
for i in range(h):
    for j in range(w):
        graph = [[inf for _ in range(w)] for l in range(h)]
        bfs(j,i,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: Time Limit Exceeded

Solution code:
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)
ans = 0
inf = 4000
for i in range(h):
    for j in range(w):
        graph = [[inf for _ in range(w)] for _ in range(h)]
        bfs(j,i,0)
        for p in range(h):
            for q in range(w):
                if graph[p][q] < inf:
                    ans = max(ans, graph[p][q])
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0

d = ([0, 1], [0, -1], [1, 0], [-1, 0])


def bfs(x, y):
    m = [[-1] * W for _ in range(H)]

    q = deque()
    q.append([y, x, 0])
    maximus = 0

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                q.append([dj, di, v+1])
                if maximus < v+1:
                    maximus = v+1

    return maximus


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2020/01/12

from copy import deepcopy
import sys
from collections import deque

sys.setrecursionlimit(10**7)


def main():
    dr=[(-1,0),(0,-1),(0,1),(1,0)]

    h,w=map(int,input().split())
    g=[list('#')*(w+2)]
    for _ in range(h):
        g+=[['#']+list(input())+['#']]
    g+=[list('#')*(w+2)]


    def bfs(sx,sy,maze):
        res=0
        x,y=sx,sy
        maze[x][y]=0
        que=deque()
        que.append((x,y))

        while que:
            x,y=que.popleft()
            for dx,dy in dr:
                nx=dx+x
                ny=dy+y
                if maze[nx][ny]=='#':continue
                if maze[nx][ny]!='.' and maze[nx][ny]<=maze[x][y]:continue
                maze[nx][ny]=maze[x][y]+1
                que.append((nx,ny))
                res=max(res,maze[nx][ny])
        return res


    ans=0
    maze=deepcopy(g)

    for i in range(1,h+1):
        for j in range(1,w+1):
            if g[i][j]=='#':continue
            res=bfs(i,j,maze)
            ans=max(res,ans)
            maze=deepcopy(g)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    max_way = []
    for start_i in range(len(points) - 1):
        for goal_i in range(start_i + 1, len(points)):
            if points[start_i] in max_way and points[goal_i] in max_way:
                continue
            step, way = count_step(MAP, points[start_i], points[goal_i])
            if step > max_step:
                max_step = step
                max_way = way

    print(max_step)


MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def count_step(MAP, start, goal):
    candidates = [(start, get_distance(start, goal), 0, [start])]

    checked = {}
    while True:
        pos, _, step, way = candidates.pop(0)
        for m in MOVES:
            next_pos = (pos[0] + m[0], pos[1] + m[1])
            if next_pos in checked:
                continue
            if not is_valid(MAP, next_pos):
                continue
            checked[next_pos] = True
            new_way = list(way)
            new_way.append(next_pos)
            distance = get_distance(next_pos, goal)
            if distance == 0:
                return step + 1, new_way
            candidates.append((next_pos, distance, step + 1, new_way))
        candidates.sort(key=lambda x: x[1] + x[2])


def get_distance(p, goal):
    return abs(p[0] - goal[0]) + abs(p[1] - goal[1])


def is_valid(MAP, pos):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= len(MAP) or pos[1] >= len(MAP[0]):
        return False

    if MAP[pos[0]][pos[1]] == '#':
        return False
    return True


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020/01/12

from copy import deepcopy
import sys
from collections import deque

sys.setrecursionlimit(10**7)


def main():
    dr=[(-1,0),(0,-1),(0,1),(1,0)]

    h,w=map(int,input().split())
    g=[list('#')*(w+2)]
    for _ in range(h):
        g+=[['#']+list(input())+['#']]
    g+=[list('#')*(w+2)]


    def bfs(sx,sy,maze):
        res=0
        x,y=sx,sy
        maze[x][y]=0
        que=deque()
        que.append((x,y))

        while que:
            x,y=que.popleft()
            for dx,dy in dr:
                nx=dx+x
                ny=dy+y
                if maze[nx][ny]=='#':continue
                if maze[nx][ny]!='.' and maze[nx][ny]<maze[x][y]:continue
                maze[nx][ny]=maze[x][y]+1
                que.append((nx,ny))
                res=max(res,maze[nx][ny])
        return res


    ans=0
    maze=deepcopy(g)

    for i in range(1,h+1):
        for j in range(1,w+1):
            if g[i][j]=='#':continue
            res=bfs(i,j,maze)
            ans=max(res,ans)
            maze=deepcopy(g)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = ['#'*(w+2)]
for i in range(h):
  s.append('#'+input()+'#')
s.append('#'*(w+2))

from collections import deque

def search(x, y):
  p = [[-1]*(w+2) for _ in range(h+2)]
  q = deque()
  q.append([x,y,0])
  p[x][y] = 0
  
  while len(q)>0:
    i,j,t = q.popleft()
    p[i][j] = t
    if s[i-1][j] != '#' and p[i-1][j] == -1:
        q.append([i-1,j,t+1])
    if s[i+1][j] != '#' and p[i+1][j] == -1:
        q.append([i+1,j,t+1])
    if s[i][j-1] != '#' and p[i][j-1] == -1:
        q.append([i,j-1,t+1])
    if s[i][j+1] != '#' and p[i][j+1] == -1:
        q.append([i,j+1,t+1])
  return max([max(p[_]) for _ in range(len(p))])
    
  
ans = 0
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j] == '.':
      v = search(i,j)
      ans = max(ans, v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def ind(i, j):
    return  i * w + j

def sij(i, j):
    return ss[ind(i, j)]

def pdist(d):
    for i in range(len(d)):
        print(d[i])

def froyd(n, d):
    for k in range(n):
        for s in range(n):
            for t in range(n):
                d[s][t] = min(d[s][t], d[s][k] + d[k][t])

h, w = [int(x) for x in input().split()]
n = h * w
ss = ""
for i in range(h):
    ss += input()

INF = float("inf")
d = [[] for _ in range(n)]
for i in range(n):
    d[i] = [INF] * n
    d[i][i] = 0

# pdist(d)

# d[s][t]にsからtへのコストを入れる
for i in range(h):
    for j in range(w):
        if sij(i, j) != ".": continue
        if i > 0 and sij(i - 1, j) == ".":
            d[ind(i - 1, j)][ind(i, j)] = 1
        if i < h - 1 and sij(i + 1, j) == ".":
            d[ind(i + 1, j)][ind(i, j)] = 1
        if j > 0 and sij(i, j - 1) == ".":
            d[ind(i, j - 1)][ind(i, j)] = 1
        if j < w - 1 and sij(i, j + 1) == ".":
            d[ind(i, j + 1)][ind(i, j)] = 1

# pdist(d)

froyd(n, d)

"""
for i in range(h):
    for j in range(w):
        print(max([x for x in d[ind(i, j)] if x < INF]), end = " ")
    print()
"""

print(max([x for x in reduce(lambda a, b: a + b, d) if x < INF]))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = ['#'*(w+2)]
for i in range(h):
  s.append('#'+input()+'#')
s.append('#'*(w+2))

from collections import deque

def search(x, y):
  p = [[-1]*(w+2) for _ in range(h+2)]
  q = deque()
  q.append([x,y,0])
  p[x][y] = 0
  
  while len(q)>0:
    ijt = q.popleft()
    i = ijt[0]
    j = ijt[1]
    t = ijt[2]
    p[i][j] = t
    if s[i-1][j] != '#' and p[i-1][j] == -1:
        q.append([i-1,j,t+1])
    if s[i+1][j] != '#' and p[i+1][j] == -1:
        q.append([i+1,j,t+1])
    if s[i][j-1] != '#' and p[i][j-1] == -1:
        q.append([i,j-1,t+1])
    if s[i][j+1] != '#' and p[i][j+1] == -1:
        q.append([i,j+1,t+1])
  return max([max(p[_]) for _ in range(len(p))])
    
  
ans = 0
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j] == '.':
      v = search(i,j)
      ans = max(ans, v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())

maze = []

for i in range(h):
  a  = list(input())
  maze.append(a)

#print(maze)

max = 0

import numpy as np

mcount = np.ones((h, w), dtype = int) * -999

for i in range(len(maze)):
  for j in range(len(maze[0])):
    if maze[i][j] == ".":
      mcount[i,j] = 0
      changed = True
      while changed:
        changed = False
        for k in range(len(maze)):
          for l in range(len(maze[0])):
            if k != 0:
              if maze[k-1][l] != "#" and mcount[k-1,l] ==-999 and mcount[k,l] != -999:
                mcount[k-1, l] = mcount[k,l] + 1
                changed = True
            if k != h-1:
              if maze[k+1][l] != "#" and mcount[k+1, l] ==-999 and mcount[k,l] != -999:
                mcount[k+1, l] = mcount[k,l] + 1
                changed = True
            if l != 0:
              if maze[k][l-1] != "#" and mcount[k,l-1] ==-999 and mcount[k,l] != -999:
                mcount[k, l-1] = mcount[k,l] + 1
                changed = True
            if l != w-1:
              if maze[k][l+1] != "#" and mcount[k,l+1] ==-999 and mcount[k,l] != -999:
                mcount[k, l+1] = mcount[k,l] + 1
                changed = True
            #print(mcount)
      if np.max(mcount) > max:
        max = np.max(mcount)
      mcount[:,:] = -999

print(max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

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

def bfs(sy, sx, gy, gx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            # print(visited)
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return visited[gy][gx]

            
ans = 0
for sy in range(h):
    for sx in range(w):
        for gy in range(h):
            for gx in range(w):
                if sy == gy and sx == gx or SHWs[sy][sx] == '#' or SHWs[gy][gx] == '#':
                    continue
                count = bfs(sy=sy, sx=sx, gy=gy, gx=gx) 
                if count > ans:
                    ans = count


print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0
for y1 in range(H):
  for x1 in range(W):
    for y2 in range(H):
      for x2 in range(W):
        if grid[y2][x2]=="#" or grid[y1][x1]=="#":
          continue
        q=deque()
        q.append([y1,x1,0])
        seen=[[False for j in range(W)] for i in range(H)]
        while q:
          node=q.popleft()
          y=node[0]
          x=node[1]
          dist=node[2]
          if seen[y][x]:
            continue
          if grid[y][x]=="#":
            continue
          if y==y2 and x==x2:
            if ans<dist:
              ans=dist
          seen[y][x]=True
          if y-1>=0:
            q.append([y-1,x,dist+1])
          if y+1<H:
            q.append([y+1,x,dist+1])
          if x-1>=0:
            q.append([y,x-1,dist+1])
          if x+1<W:
            q.append([y,x+1,dist+1])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def solve(h, w, a):
    dp = [[-1] * (h * w) for _ in range(h * w)]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    def bfs(x1, y1, x2, y2):
        s = y1 * w + x1
        t = y2 * w + x2
        visited = [[False] * w for _ in range(h)]
        cur = []
        visited[y1][x1] = True
        cur.append((x1, y1))
        cnt = 1
        while True:
            nex = []
            for x, y in cur:
                for i in range(4):
                    tx = x + dx[i]
                    ty = y + dy[i]
                    if 0 <= tx < w and 0 <= ty < h and a[ty][tx] != '#' and not visited[ty][tx]:
                        visited[ty][tx] = True
                        dp[s][ty * w + tx] = cnt
                        dp[ty * w + tx][s] = cnt
                        if tx == x2 and ty == y2:
                            return cnt
                        nex.append((tx, ty))
            if len(nex) > 0:
                cur = nex
            else:
                break
            cnt += 1
        return -1

    ret = -1
    for i in range(h):
        for j in range(w):
            for i2 in range(h):
                for j2 in range(w):
                    if (i == i2 and j == j2):
                        dp[w * i + j][w * i2 + j2] = 0
                        dp[w * i2 + j2][w * i + j] = 0
                    elif a[i][j] == '.' and a[i2][j2] == '.' and dp[w * i + j][w * i2 + j2] < 0:
                        tmp = bfs(j, i, j2, i2)
                        ret = max(ret, tmp)
                        #dp[w * i + j][w * i2 + j2] = tmp
                        #dp[w * i2 + j2][w * i + j] = tmp
                        #print(i, j, i2, j2)
                        #print(tmp)
    print(ret)
    return

def main():
    h, w = map(int, input().split())
    a = []
    for i in range(h):
        a.append(input())
    solve(h, w, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
import copy
import numpy as np

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

def solve(S, s):
    M = copy.deepcopy(S)
    d = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    # steps = [[np.max for _ in range(W)] for _ in range(H)]
    # steps = [[H*W+1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        # if cy == g[0] and cx == g[1]:
        #     return steps[cy][cx]
        # else:
        M[cy][cx] = '#'
        for i in d:
            next = [cy+i[0], cx+i[1]]
            # はみ出さないかつ通ってない
            if (0<=next[0]<H and 0<=next[1]<W) and M[next[0]][next[1]]!='#':
                queue.append(next)
                steps[next[0]][next[1]] = steps[cy][cx] + 1
    # print(steps)
    # [i. for i in steps]
    # print(steps)
        
    return max([max(i) for i in steps])
# print(solve(S, [0, 0], [0, 1]))
# print(solve(S, [2, 0], [0, 4]))
# print(S)
maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        # print(s, g)
        # print(solve(S, [s[0], s[1]], [g[0], g[1]]))
        maxStep = max(solve(S, [s[0], s[1]]), maxStep)

print(maxStep)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = []
for i in range(h):
  a = input()
  k = []
  for j in range(w):
    k.append(a[j])
  maze.append(k)
  
def clear_maze(sx, sy, gx, gy, maze):


    INF = 100000000

    field_x_length = h
    field_y_length = w
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

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

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length):
                    if (maze[nx][ny] != '#' and distance[nx][ny] == INF):
                      queue.insert(0, (nx, ny))
                      distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()
ans = 0  
for i in range(h):
  for j in range(w):
    for u in range(h):
      for v in range(w):
        if maze[i][j] == "." and maze[u][v] == ".":
          a = clear_maze(i, j, u, v, maze)
          ans = max(ans, a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = ['#'*(w+2)]
for i in range(h):
  s.append('#'+input()+'#')
s.append(['#'*(w+2)])

from collections import deque

def search(x, y):
  p = [[-1]*(w+2) for _ in range(h+2)]
  q = deque()
  q.append([x,y,0])
  p[x][y] = 0
  
  while len(q)>0:
    ijt = q.popleft()
    i = ijt[0]
    j = ijt[1]
    t = ijt[2]
    p[i][j] = t
    if i != 1:
      if s[i-1][j] != '#' and p[i-1][j] == -1:
        q.append([i-1,j,t+1])
    if i != h:
      if s[i+1][j] != '#' and p[i+1][j] == -1:
        q.append([i+1,j,t+1])
    if j != 1:
      if s[i][j-1] != '#' and p[i][j-1] == -1:
        q.append([i,j-1,t+1])
    if j != w:
      if s[i][j+1] != '#' and p[i][j+1] == -1:
        q.append([i,j+1,t+1])
  v = max([max(p[_]) for _ in range(len(p))])
  return v
    
  
ans = 0
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j] == '.':
      v = search(i,j)
      ans = max(ans, v)
print(ans)

Submission status: Time Limit Exceeded

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

def Maze_Master(y, x, c):
    if y < 0 or y > h-1 or x < 0 or x > w-1 or m[y][x] != 0 and m[y][x] < c or s[y][x] == "#":
        pass
    else:
        m[y][x] = c
        c += 1
        Maze_Master(y+1, x, c)
        Maze_Master(y-1, x, c)
        Maze_Master(y, x+1, c)
        Maze_Master(y, x-1, c)
    return m
    
l = []
for y in range(h):
    for x in range(w):
        m = [[0]*w for _ in range(h)]
        ans = Maze_Master(y, x, 1)
        for i in ans:
            for j in i:
                l.append(j)

print(max(l) - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
    ans = 0
    for i in range(len(S)):
      for j in range(i+1, len(G)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!='#':
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                if nexty == G[j][0] and nextx == G[j][1]:
                  break
                que.append([nexty,nextx])
        ans = max(ans, maze1[G[j][0]][G[j][1]])
    print(ans)
bfs()