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: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque
from itertools import product
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    queue = deque([root])
    grid[root] = 0
    while queue:
        x, y, d = queue.popleft()
        d += 1
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy, d))
                grid[y+dy, x+dx] = 0
    return d-1
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i, 0)))
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque
import numpy as np
inputs = open(0).readlines()
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, rows in zip(range(h), grid):
            for j, val in zip(range(w), rows):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, rows)) for rows in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val
h, w = map(int, inputs[0].split())
grid_origin = Grid(inputs[1:], function=lambda x: int(x == '.'))

def bfs(root):
    queue = deque([root])
    while queue:
        x, y, d = queue.popleft()
        d += 1
        grid[y, x] = 0
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            if grid.is_valid_xy(x+dx, y+dy) and grid[y+dy, x+dx]:
                queue.append((x+dx, y+dy, d))
                grid[y+dy, x+dx] = 0
    return d-1
    
ans = 0
for i, j in product(range(h), range(w)):
    if grid_origin[i, j]:
        grid = deepcopy(grid_origin)
        ans = max(ans, bfs((j, i, 0)))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def bfs(sy, sx):
    dist = [[-INF] * W for _ in range(H)]
    dist[sy][sx] = 0
    que = deque([(sy, sx)])
    popleft = que.popleft; append = que.append
    while que:
        y, x = popleft()
        cur = dist[y][x]
        for dy, dx in zip([0, 1, 0, -1], [1, 0, -1, 0]):            
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '#' and dist[ny][nx] == -INF:
                dist[ny][nx] = cur + 1
                append((ny, nx))
    ret = max(max(x for x in di)for di in dist)
    return ret

INF = 10 ** 3
H, W = lr()
grid = [sr() for _ in range(H)]
answer = max(max(bfs(i, j) for j in range(W) if grid[i][j] == '.') for i in range(H))
print(answer)
# 22

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
grid = [sr() for _ in range(H)]

def bfs(sy, sx):
    d = [[float('inf')] * W for _ in range(H)]
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    que = deque()
    que.append((sy, sx))
    d[sy][sx] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]                
            if 0 <= ny < H and 0 <= nx < W and \
                    grid[ny][nx] != '#' and d[ny][nx] == float('inf'):
                d[ny][nx] = d[p[0]][p[1]] + 1
                que.append((ny, nx))
    max = 0
    for row in d:
        for r in row:
            if r != float('inf') and r > max:
                max = r
    return max

answer = 0    
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        result = bfs(i, j)
        if result > answer:
            answer = result

print(answer)
# 49

Submission status: Runtime Error

Solution code:
import copy
import sys
sys.setrecursionlimit(10**8)

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

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

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0) ,walker)
    else:
        return None


candicate = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
        far=0
        for gx in range(W):
            for gy in range(H):
                if S[gy][gx]=='.':
                    if far <= temp_walker[gy][gx]:
                        far = temp_walker[gy][gx]

        #print(sx, sy, temp_walker, far)
        candicate.append(far)
print(max(candicate))

Submission status: Runtime Error

Solution code:
import copy
import sys
sys.setrecursionlimit(10**6)

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

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

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0),walker)
    else:
        return None


candicate=[]
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
        far=0
        for gx in range(W):
            for gy in range(H):
                if S[gy][gx]=='.':
                    if far <= temp_walker[gy][gx]:
                        far = temp_walker[gy][gx]

        #print(sx, sy, temp_walker, far)
        candicate.append(far)
print(max(candicate))

Submission status: Runtime Error

Solution code:
import copy


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

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

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0),walker)
    else:
        return None


candicate=[]
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
        far=0
        for gx in range(W):
            for gy in range(H):
                if S[gy][gx]=='.':
                    if far <= temp_walker[gy][gx]:
                        far = temp_walker[gy][gx]

        #print(sx, sy, temp_walker, far)
        candicate.append(far)
print(max(candicate))

Submission status: Runtime Error

Solution code:
import copy
import sys
sys.setrecursionlimit(400)

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

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

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0),walker)
    else:
        return None


candicate=[]
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
        far=0
        for gx in range(W):
            for gy in range(H):
                if S[gy][gx]=='.':
                    if far <= temp_walker[gy][gx]:
                        far = temp_walker[gy][gx]

        #print(sx, sy, temp_walker, far)
        candicate.append(far)
print(max(candicate))

Submission status: Runtime Error

Solution code:
from collections import deque
import math
maxloc = -10
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
for y in range(h):
    for x in range(w):
        if maze[y][x]=='.':
            maze[y][x]=1000000

for i in range(h):
  for j in range(w):
    sy = i
    sx = j
    if(maze[sy-1][sx-1] != '#'):
      maze[sy-1][sx-1]=0
      for k in range(h):
        for l in range(w):
          gy = k
          gx = l
          if(maze[gy-1][gx-1] != '#'):
            que = deque([[sy-1, sx-1]])
            while que:
              y, x = que.popleft()
              for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
                nexty, nextx = y+i, x+j
                dist = maze[nexty][nextx]
                if(dist != '#'):
                  if dist > maze[y][x]+1:
                    maze[nexty][nextx] = maze[y][x]+1
                    que.append([nexty, nextx])
            if(int(maze[gy-1][gx-1])>maxloc):
              maxloc = maze[gy-1][gx-1]
            
print(maxloc)

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#include <stdio.h>
#include <stdlib.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : (-1 * (a)))
#define rep(i, n) for ((i) = 0; (i) < (int)(n); (i)++)
#define rep2(i, s, e) for ((i) = (s); (i) < (int)(e); (i)++)

int path[25][25];
int map[25][25];
int x[500];
int y[500];
int x2[500];
int y2[500];

int main(void)
{

    int h, w, i, j, k, l, m, mx = 0;
    char buf[50];
    scanf("%d %d", &h, &w);
    rep(i, h)
    {
        scanf("%s", &buf);
        rep(j, w)
            map[i + 1][j + 1] = buf[j];
    }
    rep(i, h + 2) rep(j, w + 2) if (i == 0 || j == 0 || i == h + 1 || j == w + 1) map[i][j] = '#';

    rep(i, h + 2)
    {
        rep(j, w + 2)
        {
            if (map[i][j] == '#')
                continue;
            rep(k, h + 2) rep(l, w + 2) path[k][l] = 1000;
            int flg = 0;
            int lng = 0;
            int cue = 1;
            int cue2 = 0;
            x[0] = i;
            y[0] = j;
            path[i][j] = 0;
            while (cue != 0)
            {
                rep(k, cue)
                {
                    int c = path[x[k]][y[k]];
                    int u = path[x[k] - 1][y[k]];
                    int d = path[x[k] + 1][y[k]];
                    int l = path[x[k]][y[k] - 1];
                    int r = path[x[k]][y[k] + 1];
                    int mc = map[x[k]][y[k]];
                    int mu = map[x[k] - 1][y[k]];
                    int md = map[x[k] + 1][y[k]];
                    int ml = map[x[k]][y[k] - 1];
                    int mr = map[x[k]][y[k] + 1];
                    if (mu != '#')
                    {
                        if (c + 1 < u)
                        {
                            path[x[k] - 1][y[k]] = c + 1;
                            x2[cue2] = x[k] - 1;
                            y2[cue2] = y[k];
                            cue2++;
                        }
                    }
                    if (md != '#')
                    {
                        if (c + 1 < d)
                        {
                            path[x[k] + 1][y[k]] = c + 1;
                            x2[cue2] = x[k] + 1;
                            y2[cue2] = y[k];
                            cue2++;
                        }
                    }
                    if (ml != '#')
                    {
                        if (c + 1 < l)
                        {
                            path[x[k]][y[k] - 1] = c + 1;
                            x2[cue2] = x[k];
                            y2[cue2] = y[k] - 1;
                            cue2++;
                        }
                    }
                    if (mr != '#')
                    {
                        if (c + 1 < r)
                        {
                            path[x[k]][y[k] + 1] = c + 1;
                            x2[cue2] = x[k];
                            y2[cue2] = y[k] + 1;
                            cue2++;
                        }
                    }
                    /*printf("%d, %d, %d,[%d][%d]\n", i, j, k, x[k], y[k]);
                    rep(l, h + 2)
                    {
                        rep(m, w + 2)
                        {
                            printf("%d\t", path[l][m]);
                        }
                        printf("\n");
                    }*/
                }
                rep(k, cue2)
                {
                    x[k] = x2[k];
                    y[k] = y2[k];
                }
                cue = cue2;
                cue2 = 0;
            }
            rep(k, h + 2) rep(l, w + 2) mx = max(mx, path[k][l] * (map[k][l] == '.'));
        }
    }
    printf("%d", mx);

    return 0;
}

Submission status: Runtime Error

Solution code:
mport Queue
import copy

def main():
    H, W = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))


    def bfs(start, S2):
        q = Queue.Queue()
        q.put(start)
        candidates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        dist = [[0]*W for _ in range(H)]
        while not q.empty():
            i = q.get()
            x = i[0]
            y = i[1]
            S2[x][y] = "#"

            for candi in candidates:
                x_new = x + candi[0]
                y_new = y + candi[1]

                if x_new < H and x_new >= 0:
                    if y_new < W and y_new >=0:
                        if S2[x_new][y_new] == ".":
                            dist[x_new][y_new] = dist[x][y] + 1
                            q.put([x_new, y_new])

        ans = 0
        for i in range(H):
            ans = max(ans, max(dist[i]))

        return ans

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                S2 = copy.deepcopy(S)
                ans = max(ans, bfs([i, j], S2))

    print ans


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
meiro = []
INF = 10**9
meiro.append(["#"]*(W+2))
for _ in range(H):
    temp = list(input())
    temp.append("#")
    temp.insert(0,"#")
    meiro.append(temp)
meiro.append(["#"]*(W+2))

def bfs(i,j):
    INF = 10 ** 9
    dist = [[INF for i in range(W+2)] for j in range(H+2)]
    dist[i][j] = 0
    q = deque([[i,j]])
    while q:
        v = q.popleft()
        dv = dist[v[0]][v[1]]
        
        if meiro[v[0]-1][v[1]] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]-1][v[1]]:
                dist[v[0]-1][v[1]] = dist[v[0]][v[1]]+1
                q.append([v[0]-1,v[1]])
                
        if meiro[v[0]+1][v[1]] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]+1][v[1]]:
                dist[v[0]+1][v[1]] = dist[v[0]][v[1]]+1
                q.append([v[0]+1,v[1]])
        
        if meiro[v[0]][v[1]-1] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]][v[1]-1]:
                dist[v[0]][v[1]-1] = dist[v[0]][v[1]]+1
                q.append([v[0],v[1]-1])
        
        if meiro[v[0]][v[1]+1] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]][v[1]+1]:
                dist[v[0]][v[1]+1] = dist[v[0]][v[1]]+1
                q.append([v[0],v[1]+1])
    
    dist = [[0 if x == INF else x for x in inner] for inner in dist]
    return max(max(dist))

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

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float('inf')
ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]!='#':
            dp=[[inf for _ in range(w)] for _ in range(h)]
            dp[i][j]=0
            que=deque([(i,j)])
        while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                if 0<=ni<h and 0<=nj<w and S[ni][nj]!='#':
                    if dp[ni][nj]>dp[si][sj]+1:
                        dp[ni][nj]=dp[si][sj]+1
                        ans=max(ans,dp[si][sj]+1)
                        que.append((ni,nj))
print(ans)

Submission status: Runtime Error

Solution code:
import copy
import sys
input = sys.stdin.readline
H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            queue = [i,j,0]#最初の△
            maze = copy.deepcopy(input_maze)
            while True:
                if len(queue) ==0:
                    tem_ans = point[2]
                    break
                point=queue.pop(0)#queueの先頭座標+何回移動したかの取得
                maze[point[0]][point[1]] = point[2] 
                if point[0] > 0 and maze[point[0]-1][point[1]]==".":#上
                    queue.append([point[0]-1,point[1],point[2]+1])
                if point[0] < len(maze)-1 and maze[point[0]+1][point[1]]==".":#下
                    queue.append([point[0]+1,point[1],point[2]+1])
                if point[1] > 0 and maze[point[0]][point[1]-1]==".":#左
                    queue.append([point[0],point[1]-1,point[2]+1])
                if point[1] < len(maze[point[0]])-1 and maze[point[0]][point[1]+1]=="." :#右
                    queue.append([point[0],point[1]+1,point[2]+1])
                
            ans = max(ans,tem_ans)
print(ans)

Submission status: Runtime Error

Solution code:
import copy
import numpy
def move(maze):
    is_move = False
    cp_maze = copy.deepcopy(maze)
    for i in range(H):
        for j in range(W):
            if cp_maze[i][j]=="X":
                if i > 0 and cp_maze[i-1][j]==".":#上
                    maze[i-1][j] = "X"
                    is_move = True
                    #print("上")
                if i < len(cp_maze)-1 and cp_maze[i+1][j]==".":#下
                    maze[i+1][j] = "X"
                    is_move = True
                    #print("下")
                if j > 0 and cp_maze[i][j-1]==".":#左
                    maze[i][j-1] = "X"
                    is_move = True
                   # print("左")
                if j < len(cp_maze)-1 and cp_maze[i][j+1]=="." :#右
                    maze[i][j+1] = "X"
                    is_move = True
                    #print("右")
    return is_move


H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            dis = 0
            maze = copy.deepcopy(input_maze)
            maze[i][j]="X"
            while True:
                is_move = move(maze)
                if is_move:
                    dis += 1
                else:
                    ans = max(dis,ans)
                    break
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(grid, sy, sx, wall):
    queue = deque([])
    queue.append([sy, sx, 0])
    visited = {}
    visited[(sy,sx)] = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall or (y_,x_) in visited:
                continue
            queue.append([y_,x_,cnt+1])
            visited[(y_,x_)] = cnt+1
    return visited

h,w = map(int, input().split())
wall = '#'
edges = [wall] * (w+2)
grid = [edges]
start = []
for i in range(h):
    s = input()
    grid.append([wall] + list(s) + [wall])
    for j in range(1,w+1):
        if start == [] and grid[i][j] == '.':
            start = [i,j]
grid.append(edges)

visited = bfs(grid, start[0], start[1], wall)
mx = 0
pos = []
for k,v in visited.items():
    if v > mx:
        mx = v
        pos = k
# print(start, pos)
visited = bfs(grid, pos[0], pos[1], wall)
print(max(visited.values()))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
import os
f = open('input.txt', 'r')
sys.stdin = f
input = sys.stdin.readline
# 3.24の練習


# D maze master

h, w = map(int, input().split())

graph = {i: {} for i in range(1, h * w + 1)}

data = []
data.append([False for i in range(w + 2)])
for i in range(h):
    s = list(input())
    sub = [False]
    for i in range(w):
        if s[i] is "#":
            sub.append(False)
        else:
            sub.append(True)
    sub.append(False)
    data.append(sub)
data.append([False for i in range(2 + w)])

for i in range(1, h + 1):
    for j in range(1, w + 1):
        # now data[i][j]
        if data[i][j]:
            now = w * (i - 1) + j
            if data[i - 1][j]:
                node = w * (i - 1) + j
                graph[now][node]=1
                graph[node][now]=1
            if data[i][j + 1]:
                node = w* (i - 1) + j + 1
                graph[now][node]=1
                graph[node][now]=1
            if data[i][j - 1]:
                node = w * (i - 1) + j - 1
                graph[node][now]=1
                graph[now][node]=1
            if data[i + 1][j]:
                node = w * i + j
                graph[node][now]=1
                graph[now][node]=1

# graph=迷路のグラフデータ構造

import heapq
def dijkstra(s,graph,n):
    #ｓからのグラフの最短最短距離をまとめたデータを返す
    dist=[10**20 for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    #全ての接点を一度優先度付きキューに挿入する
    heapq.heappush(pq,(0,s))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for point in graph[node].keys():
            w=graph[node][point]
            #nodeからpointに対して伸びる辺の長さ
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen
    mea=0
    for i in range(1,n+1):
        if 0<dist[i]<10**20:
            mea=max(dist[i],mea)
    return mea

###############################################################
ans=0
for i in range(1,h*w+1):
    if graph[i]:
        ans=max(ans,dijkstra(i,graph,h*w))
print(ans)

Submission status: Runtime Error

Solution code:
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            if c == "#":
                a.append(9999)
        maze.append(a)
        #print(maze)
    return maze

def maxroot(maze, x, y, w, h):
    sn = 0
    maxx = 0
    if maze[y][x] == 9999:
        return 0

    maze = deepcopy(maze)
    maze[y][x] = 0
    que = deque()
    que.append((y, x))


    while que:
        xy = que.pop()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd

        for y, x in minlist:
            if maze[y][x] != 9999 and maze[y][x] > dd+2:
                que.append((y, x))
                sn += 1
            #print(sn)

    maxx = 0
    for line in maze:
        maxa = max([i for i in line if i < 1000])
        maxx = max(maxx, maxa)
    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 1
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    #print(maxroot(maze, 0, 2, W, H))


main()

Submission status: Runtime Error

Solution code:
%%time
import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
#             print(que)
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            if sh > 0 and sh < h - 1 and sw > 0 and sw < w - 1:
                if 0 + (ss[sh + 1][sw] == ".") + (ss[sh - 1][sw] == ".") + (ss[sh][sw + 1] == ".") + (ss[sh][sw - 1] == ".") >= 3:
                    continue
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)

Submission status: Runtime Error

Solution code:
%%time

import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.pop()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)