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:
h,w=map(int,input().split())
s=["."]*h
for i in range(h):
    s[i]=input()
ans=0    
n=[[100]*h]*w
def check(i,j):
   
    n[i][j]=0   
    if 1<=j:
        if s[i][j-1]=="." and n[i][j-1]==100:
            check2(i,j-1)
    if j<=w-2:
        if s[i][j+1]=="." and n[i][j+1]==100:
            check2(i,j+1)
    if 1<=i:
        if s[i-1][j]=="." and n[i-1][j]==100:
            check2(i-1,j)
    if i<=h-2:
        if s[i+1][j]=="." and n[i+1][j]==100:
            check2(i+1,j)
    for i in range(h):
        for j in range(w):
            if n[i][j]==100:n[i][j]=0
           
    return max(max(n))

def check2(i,j):
    if 1<=j:n[i][j]=min(n[i][j],n[i][j-1])+1
    if j<=w-2:n[i][j]=min(n[i][j],n[i][j+1])+1
    if 1<=i:n[i][j]=min(n[i][j],n[i-1][j])+1
    if i<=h-2:n[i][j]=min(n[i][j],n[i+1][j])+1 
    if 1<=j:
        if s[i][j-1]=="." and n[i][j-1]==100:
            check2(i,j-1)
    if j<=w-2:
        if s[i][j+1]=="." and n[i][j+1]==100:
            check2(i,j+1)
    if 1<=i:
        if s[i-1][j]=="." and n[i-1][j]==100:
            check2(i-1,j)
    if i<=h-2:
        if s[i+1][j]=="." and n[i+1][j]==100:
            check2(i+1,j)
    
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            a=check(i,j)
            ans=max(ans,a)
print(ans-1)

Submission status: Runtime Error

Solution code:
H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    s_list = list(str(input()))
    S.append(s_list)

from collections import deque
INF = 1000000
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(sx, sy, gx, gy):
    d = []
    for i in range(H):
        d.append([INF] * W)
    
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while len(que):
        p = que.popleft()
        if p == (gx, gy):
            break
        for i in range(4):
            nx = p[0] + dx[i]; ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] != '#' and d[nx][ny] == INF:
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

def ContCheck(x, y):
    route = 0
    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] != '#' and d[nx][ny] == INF:
            route += 1
    if route == 1:
        return False
    else:
        return True

ans = 0
checked = []
for _ in range(H * W):
    checked.append([0] * (H * W))
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        if ContCheck(i, j):
            continue
        for k in range(H):
            for l in range(W):
                if S[k][l] == '#':
                    continue
                if ContCheck(k, l):
                    continue
                if checked[i * W + j][k * W + l] == 1:
                    continue
                if i == k and j == l:
                    continue
                ans = max(bfs(i, j, k, l), ans)
                checked[i * W + j][k * W + l] = 1
                checked[k * W + l][i * W + j] = 1
print(ans)

Submission status: Runtime Error

Solution code:
import queue
import itertools
r,c=map(int,input().split())
s=[list(input()) for i in range(r)]
ans=0
for i1 in range(r):
    for i2 in range(c):
        p=0
        a=[[s[j][i] for i in range(c)] for j in range(r)]
        sy,sx=i1,i2
        if a[sy][sx]=="#":
            break
                #print(sy,sx,gy,gx)
        q = queue.Queue()
        d=[(-1,0),(1,0),(0,-1),(0,1)]
        a[sy][sx]=0
        for i in d:
            if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
                a[sy+i[0]][sx+i[1]]=1
                q.put((sy+i[0],sx+i[1]))
        while not q.empty():
            y,x=q.get()
            for i in d:
                if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                    p=a[y][x]+1
                    q.put((y+i[0],x+i[1]))
                ans=max(p,ans)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 12 21:32:04 2020

@author: maezawa
"""
import copy

h, w = list(map(int, input().split()))
board = [[] for _ in range(h+2)]

for i in range(1,h+1):
    s = input()
    board[i] = list('*'+s+'*')
board[0] = list('*'*(w+2))
board[h+1] = list('*'*(w+2))
last =  copy.deepcopy(board)   
#print(board)

def search(y,x,n):
    if board[y][x] == '*':
        return
    dirs = [[-1,0],[0,1],[1,0],[0,-1]]
    nextcells = []
    forwcells=[[y,x]]
    while forwcells:
        islast = True
        curcell = forwcells.pop()
        for di in dirs:
            nextcells.append([curcell[0]+di[0],curcell[0]+di[1]])
        n += 1
        for ncel in nextcells:
            if board[ncel[0]][ncel[1]] == '.':
                board[ncel[0]][ncel[1]] = n
                forwcells.append((ncel))
                islast = False
        if islast:
            last[curcell[0]][curcell[1]] = "@"                       
    
for i in range(1,h+1):
    for j in range(1,w+1):
        if board[i][j] == '.':
            board[i][j] = 0
            search(i,j,0)

candidates = [0]            
for i in range(1,h+1):
    for j in range(1,w+1):
        if last[i][j] == '@':
            candidates.append(board[i][j])
            
candidates.sort(reverse=True)
ans = candidates[0]+candidates[1]
print(ans)

Submission status: Runtime Error

Solution code:
import math
H, W = [int(i) for i in input().split()]
SSS = [[math.inf for i in range(W+2)]]
for i in range(H):
    buff = "#"+input()+"#"
    SSS.append([0 if i=="." else math.inf for i in buff])
SSS.append([math.inf for i in range(W+2)])

def routetable(x0,y0):
    table = [[10000000 for i in range(W+2)] for j in range(H+2)]
    for i in range(H+2):
        for j in range(W+2):
            if SSS[i][j]==math.inf:
                table[i][j]=SSS[i][j]
    table[x0][y0]=1

    
    while True:
        detector = 0
        for i in range(1,H+1):
            for j in range(1,W+1):
                if table[i][j]==10000000: detector += 1
                if table[i-1][j]!=math.inf: table[i-1][j]=min(table[i][j]+1,table[i-1][j])
                if table[i+1][j]!=math.inf: table[i+1][j]=min(table[i][j]+1,table[i+1][j])
                if table[i][j-1]!=math.inf: table[i][j-1]=min(table[i][j]+1,table[i][j-1])
                if table[i][j+1]!=math.inf: table[i][j+1]=min(table[i][j]+1,table[i][j+1])
        if detector==0:
            break
    """
    print("\n")
    for t in table:
        print(t)
    """
    maxroute = 0
    for i in range(H+2):
        for j in range(W+2):
            if table[i][j]!=math.inf:
                maxroute = max(maxroute,table[i][j])
    return(maxroute-1)


ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if SSS[i][j]!=math.inf:
            ans = max(ans,routetable(i,j))

print(ans)

Submission status: Runtime Error

Solution code:
import queue
# import sys
# input = sys.stdin.readline

vx = [0,1,0,-1];
vy = [1,0,-1,0];
q = queue.Queue()
 
h, w = map(int, input().split())
# print(hw)
# h = int(hw[0]);
# w = int(hw[1]);
s_s = [h-1, 0]
sy = int(s_s[0]);
sx = int(s_s[1]);
s_g = [0, w-1]
gy = int(s_g[0]);
gx = int(s_g[1]);
s = [ [0]*w for i in range(h)];
for i in range(h) :
	si = input();
	for j in range(w) :
		s[i][j] = si[j];
 
cont = 1;
q_a = [0]*2;
q_a[0] = sy;
q_a[1] = sx;
q.put(q_a);
s[sy][sx] = 0;
while not q.empty() :
	q_a = q.get();
	for i in range(4):
		ny = q_a[0] + x[i];
		nx = q_a[1] + vx[i];
		if s[ny][nx] == '.' :
			s[ny][nx] = s[q_a[0]][q_a[1]] + 1;
			q_b = [0]*2;
			q_b[0] = ny;
			q_b[1] = nx;
			q.put(q_b);
 
print(s[gy][gx]);

Submission status: Runtime Error

Solution code:
from collections import deque
R,C = map(int,input().split())
state = []
mx=0
for i in range(R):
    state.append(input())
for sy in range(R):
    for sx  in range(C):
        st=state[sy][sx]
        if st =="#":
            continue
        for gy  in range(R):
            for gx in range(C):
                gl = state[gy][gx]
                if gl =="#":
                    continue
                else:    
                    start = [sy,sx]
                    goal = [gy,gx]
                    step = []
                    for i in range(R):
                        step.append([float('inf') for i in range(C)])
                    step[start[0]][start[1]] = 0
                    Q = deque()
                    Q.append((start[0],start[1]))
                    while Q:
                        y,x = Q.pop()
                        if y+1 < R:
                            if step[y+1][x] == float('inf') and state[y+1][x] == '.':
                                step[y+1][x] = step[y][x]+1
                                Q.appendleft((y+1,x))
                        if x+1 < C:
                            if step[y][x+1] == float('inf') and state[y][x+1] == '.':
                                step[y][x+1] = step[y][x]+1
                                Q.appendleft((y,x+1))
                        if y-1 >= 0:
                            if step[y-1][x] == float('inf') and state[y-1][x] == '.':
                                step[y-1][x] = step[y][x]+1
                                Q.appendleft((y-1,x))
                        if x-1 >= 0:
                            if step[y][x-1] == float('inf') and state[y][x-1] == '.':
                                step[y][x-1] = step[y][x]+1
                                Q.appendleft((y,x-1))
                    print(step[goal[0]][goal[1]])
                    from collections import deque
                    R,C = map(int,input().split())
                    start = list(map(int,input().split()))
                    goal = list(map(int,input().split()))
                    start = [start[0]-1,start[1]-1]
                    goal = [goal[0]-1,goal[1]-1]
                    state = []
                    for i in range(R):
                        state.append(input())
                    step = []
                    for i in range(R):
                        step.append([float('inf') for i in range(C)])
                    step[start[0]][start[1]] = 0
                    Q = deque()
                    Q.append((start[0],start[1]))
                    while Q:
                        y,x = Q.pop()
                        if y+1 < R:
                            if step[y+1][x] == float('inf') and state[y+1][x] == '.':
                                step[y+1][x] = step[y][x]+1
                                Q.appendleft((y+1,x))
                        if x+1 < C:
                            if step[y][x+1] == float('inf') and state[y][x+1] == '.':
                                step[y][x+1] = step[y][x]+1
                                Q.appendleft((y,x+1))
                        if y-1 >= 0:
                            if step[y-1][x] == float('inf') and state[y-1][x] == '.':
                                step[y-1][x] = step[y][x]+1
                                Q.appendleft((y-1,x))
                        if x-1 >= 0:
                            if step[y][x-1] == float('inf') and state[y][x-1] == '.':
                                step[y][x-1] = step[y][x]+1
                                Q.appendleft((y,x-1))
                    if mx < step[goal[0]][goal[1]]:
                        mx =step[goal[0]][goal[1]]
print(mx)

Submission status: Runtime Error

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, g):
    M = copy.deepcopy(S)
    d = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    queue = deque([s])
    steps = [[np.max 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
        
    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)):
    for g in itertools.product(range(H), range(W)):
        if S[s[0]][s[1]] == '.' and S[g[0]][g[1]] == '.':
            # print(s, g)
            # print(solve(S, [s[0], s[1]], [g[0], g[1]]))
            maxStep = max(solve(S, [s[0], s[1]], [g[0], g[1]]), maxStep)

print(maxStep)

Submission status: Runtime Error

Solution code:
import queue


def up(y, x, d):
    return y-1, x, d


def down(y, x, d):
    return y+1, x, d


def left(y, x, d):
    return y, x-1, d


def right(y, x, d):
    return y, x+1, d


def put_all(q, y, x, d):
    q.put((up(y, x, d)))
    q.put((down(y, x, d)))
    q.put((left(y, x, d)))
    q.put((right(y, x, d)))
    return


def put_not_all(q, y, x, d, distances):
    if distances[y-1][x] != -1:
        q.put((y-1, x, d))
    if distances[y+1][x] != -1:
        q.put((y+1, x, d))
    if distances[y][x-1] != -1:
        q.put((y, x-1, d))
    if distances[y][x+1] != -1:
        q.put((y, x+1, d))


def solve(maze, init_y, init_x, distances, H, W):
    if maze[init_y][init_x] == "#":
        return 0

    distances[init_y][init_x] = 0

    q = queue.Queue()
    put_all(q, init_y, init_x, 1)

    farthest = [0, init_y, init_x]
    while not q.empty():
        y, x, d = q.get()
        # print(x, y)
        if x < 0 or x >= W or y < 0 or y >= H:
            # print("continue")
            continue
        if maze[y][x] == "#":
            distances[y][x] = 0
            continue
        distance = distances[y][x]
        if distance == -1:
            distances[y][x] = d
            put_all(q, y, x, d+1)
            if d > farthest[0]:
                farthest = [d, y, x]

    return farthest


def main():
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    flag = False
    y = 0
    x = 0
    for i in range(H):
        for j in range(W):
            initial_map = [[-1 for _ in range(W)] for _ in range(H)]
            distance, y, x = solve(maze, i, j, initial_map, H, W)
            if distance > 0:
                flag = True
                break
        if flag:
            break
    initial_map = [[-1 for _ in range(W)] for _ in range(H)]
    max_distance, y, x = solve(maze, y, x, initial_map, H, W)

    print(max_distance)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N, K = map(int,input().split())
A = sorted(list(map(int,input().split())))
mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range(2,N + 1):
    g1.append(( g1[-1] * i ) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

ans = 0
MIN = N-K+1
MAX = K-1
for i in range(MIN):#MINのインデックス
    for j in range(MAX,N):#MAXのインデックス
        if j-i+1 >= K:
            ans += (A[j]-A[i])*cmb((j-i+1)-2,K-2,mod)
print(ans%mod)

Submission status: Runtime Error

Solution code:
from collections import deque
import copy
import math

h,w = map(int,input().split())
s = []
wall = '#'
for i in range(h):
    s.append(input())
s = [list(i) for i in s]
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            s[i][j]=math.inf
    s[i] = [wall] + s[i] + [wall]
s = [[wall for i in range(w+2)]] + s + [[wall for i in range(w+2)]]
tmp = copy.deepcopy(s)
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        tmp[i][j] = 0
        que = deque([[i,j]])
        while que:
            y, x = que.popleft()
            for a,b in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + a
                nx = x + b
                dist = tmp[ny][nx]
                if dist != '#':
                    if dist > tmp[y][x] + 1:
                        tmp[ny][nx] = tmp[y][x]+1
                        que.append([ny,nx])
        for k in range(1,h+1):
            for l in range(1,w+1):
                if tmp[k][l] != '#':
                    ans = max(ans,tmp[k][l])
        tmp = copy.deepcopy(s)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
from queue import Queue
h,w=map(int,input().split())
S=[input() for _ in range(h)]

def bfs(q,memo):
  x,y,cnt=q.get()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])
    
ans=0
out=[]
def bbfs(x,y,ans):
  q=Queue()
  q.put([x,y,0])

  memo=[[-1]*w for _ in range(h)]
  while not q.empty():
    bfs(q,memo)
  if max(max(memo))>=ans:
    ans=max(max(memo))
    bbfs(x-1,y,ans)
    bbfs(x+1,y,ans)
    bbfs(x,y-1,ans)
    bbfs(x,y+1,ans)
    if ans!=None: out.append(ans)
    
bbfs(0,0,ans)
print(max(out))

Submission status: Runtime Error

Solution code:
from collections import deque

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

def cand_pos(i,j):
    neighbor = []
    if i==0:
        neighbor.append(maze[i+1][j])
    elif i==h-1:
        neighbor.append(maze[i-1][j])
    else:
        neighbor.append(maze[i+1][j])
        neighbor.append(maze[i-1][j])
    
    if j==0:
        neighbor.append(maze[i][j+1])
    elif j==w-1:
        neighbor.append(maze[i][j-1])
    else:
        neighbor.append(maze[i][j+1])
        neighbor.append(maze[i][j-1])
    
    if maze[i][j]!='#' and neighbor.count('.')==1:
        return True
    else:
        return False


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx,sy,gx,gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

pos_dic = {}
for i in range(h):
    for j in range(w):
        if cand_pos(i,j):
            pos_dic[i] = j
        else:
            continue

ans = 1000000

if len(pos_dic) == 0:
    ans = h+w-2
elif len(pos_dic) == 1:
    stx,sty = 0,0
    for k,v in pos_dic.items():
        glx, gly = k,v
    ans = bfs(stx, sty, glx, gly)
else:
    for k,v in pos_dic.items():
        stx, sty = k,v
        for kk, vv in pos_dic.items():
            glx, gly = kk, vv
            tmp = bfs(stx, sty, glx, gly)
            ans = min(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

def cand_pos(i,j):
    neighbor = []
    if i==0:
        neighbor.append(maze[i+1][j])
    elif i==h-1:
        neighbor.append(maze[i-1][j])
    else:
        neighbor.append(maze[i+1][j])
        neighbor.append(maze[i-1][j])
    
    if j==0:
        neighbor.append(maze[i][j+1])
    elif j==w-1:
        neighbor.append(maze[i][j-1])
    else:
        neighbor.append(maze[i][j+1])
        neighbor.append(maze[i][j-1])
    
    if maze[i][j]!='#' and neighbor.count('.')==1:
        return True
    else:
        return False


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx,sy,gx,gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

pos_dic = {}
for i in range(h):
    for j in range(w):
        if cand_pos(i,j):
            pos_dic[i] = j
        else:
            continue

ans = 0

if len(pos_dic) == 0:
    ans = h+w-2
elif len(pos_dic) == 1:
    stx,sty = 0,0
    for k,v in pos_dic.items():
        glx, gly = k,v
    ans = bfs(stx, sty, glx, gly)
else:
    for k,v in pos_dic.items():
        stx, sty = k,v
        for kk, vv in pos_dic.items():
            glx, gly = kk, vv
            tmp = bfs(stx, sty, glx, gly)
            ans = min(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def dfs(B,si,sj, H, W):
    R = [-1]*(H*W)
    R[si*W+sj] = 0
    d = deque([si*W+sj])
    while d:
        p = d.popleft()
        x = p//W
        y = p%W
        t = R[x*W+y]

        if x > 0:
            if B[(x-1)*W+y] == 0:
                if R[(x-1)*W+y] == -1:
                    R[(x-1)*W+y] = t+1
                    d.append((x-1)*W+y)

        if x < H-1:
            if B[(x+1)*W+y] == 0:
                if R[(x+1)*W+y] == -1:
                    R[(x+1)*W+y] = t+1
                    d.append((x+1)*W+y)
        if y > 0:
            if B[x*W+y-1] == 0:
                if R[x*W+y-1] == -1:
                    R[x*W+y-1] = t+1
                    d.append(x*W+y-1)
        if y < W-1:
            if B[x*W+y+1] == 0:
                if R[x*W+y+1] == -1:
                    R[x*W+y+1] = t+1
                    d.append(x*W+y+1)

    return max(R)
    

def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    B = [0]*(H*W)
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                B[i*W+j] = 1
    ans = 0
#    print(dfs(B,i,j,H,W))

    for i in range(H):
        for j in range(W):
            if B[i*W+j] == 1:
                continue
            t = dfs(B, i, j, H, W)
            if t > ans:
                ans = t
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
import math

N, K = map(int, input().split())
nums = list(map(int, input().split()))

total = 0
nums.sort()


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


#i = 0

# K >= 2
#if K == 1:
    
#else:
for i in range(0, len(nums) - K + 1):
    for k in range(i + K - 1, len(nums)):
            #print("i, k", nums[i], nums[k])
        count = nums[k] - nums[i]
        diff = k - 1 - i
            #print("diff:", diff, K - 2)
            #print("conb:", combinations_count(diff, K - 2))
        total += 1#combinations_count(diff, K - 2) * count
        #print("total", total)
print(total)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def dfs(B,si,sj, H, W):
    R = [-1]*(H*W)
    R[si*W+sj] = 0
    d = deque([si*W+sj])
    while d:
        p = d.popleft()
        x = p//W
        y = p%W
        t = R[x*W+y]

        if x > 0:
            if B[(x-1)*W+y] == 0:
                if R[(x-1)*W+y] == -1:
                    R[(x-1)*W+y] = t+1
                    d.append((x-1)*W+y)
                elif R[(x-1)*W+y] > t+1:
                    R[(x-1)*W+y] = t+1
                    d.append((x-1)*W+y)
        if x < H-1:
            if B[(x+1)*W+y] == 0:
                if R[(x+1)*W+y] == -1:
                    R[(x+1)*W+y] = t+1
                    d.append((x+1)*W+y)
                elif R[(x+1)*W+y] > t+1:
                    R[(x+1)*W+y] = t+1
                d.append((x+1)*W+y)
        if y > 0:
            if B[x*W+y-1] == 0:
                if R[x*W+y-1] == -1:
                    R[x*W+y-1] = t+1
                    d.append(x*W+y-1)
                elif R[x*W+y-1] > t+1:
                    R[x*W+y-1] = t+1
                    d.append(x*W+y-1)
        if y < W-1:
            if B[x*W+y+1] == 0:
                if R[x*W+y+1] == -1:
                    R[x*W+y+1] = t+1
                    d.append(x*W+y+1)
                elif R[x*W+y+1] > t+1:
                    R[x*W+y+1] = t+1
                    d.append(x*W+y+1)

    return max(R)
    

def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    B = [0]*(H*W)
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                B[i*W+j] = 1
    ans = 0
#    print(dfs(B,i,j,H,W))

    for i in range(H):
        for j in range(W):
            if B[i*W+j] == 1:
                continue
            t = dfs(B, i, j, H, W)
            if t > ans:
                ans = t
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np

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

v_id_dict = {}
dista = np.ones((20, 20)) * np.inf

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            v_id_dict[i, j] = len(v_id_dict)

            if (i > 0) and (S[i - 1][j] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i - 1, j)]] = 1

            if (j > 0) and (S[i][j - 1] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i, j - 1)]] = 1

dist_mat = dijkstra(
    csgraph_from_dense(dista[: len(v_id_dict), : len(v_id_dict)]),
    directed=False,
    unweighted=False,
)

print(int(dist_mat.max()))

Submission status: Runtime Error

Solution code:
import queue
import copy

vx = [0,1,0,-1];
vy = [1,0,-1,0];
q = queue.Queue()

hw = input().split(' ');
h = int(hw[0]);
w = int(hw[1]);
s = [ [0]*w for i in range(h)];
for i in range(h) :
	si = input();
	for j in range(w) :
		s[i][j] = si[j];

s_alt = copy.deepcopy(s);
ans = 0;
for sy in range(h) :
	for sx in range(w) :
		s = copy.deepcopy(s_alt);
		q_a = [0]*2;
		q_a[0] = sy;
		q_a[1] = sx;
		q.put(q_a);
		s[sy][sx] = 0;
		while not q.empty() :
			q_a = q.get();
			for i in range(4):
				ny = q_a[0] + vy[i];
				nx = q_a[1] + vx[i];
				if ny >= 0 and ny < h and nx >= 0 and nx < w and s[ny][nx] == '.':
					s[ny][nx] = s[q_a[0]][q_a[1]] + 1;
					q_b = [0]*2;
					q_b[0] = ny;
					q_b[1] = nx;
					q.put(q_b);
		max_path = 0;
		for i in range(h) :
			for j in range(w) :
				if s[i][j] == '#' :
					continue;
				elif s[i][j] > max_path :
					max_path = s[i][j];
		if max_path > ans :
			ans = max_path;

print(ans);

Submission status: Runtime Error

Solution code:
# 2020/01/12

from copy import deepcopy

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)]

# visited=[list([1]*(w+2))]
# for _ in range(h):
#     visited+=[[1]+list([0]*w)+[1]]
# visited+=[list([1]*(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
            maze[nx][ny]=maze[x][y]+1
            que.append((nx,ny))
            res=max(res,maze[nx][ny])
    return res


def find(mz):
    maze=deepcopy(mz)
    ret=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if maze[i][j]!='@':continue
            res=bfs(i,j,maze)
            ret=max(res,ret)
            maze=deepcopy(mz)

    return ret


def mk_maze(sx,sy,maze):
    x,y=sx,sy
    maze[x][y]='@'
    que=deque()
    que.append((x,y))

    while que:
        x,y=que.popleft()
        g[x][y]='#'
        for dx,dy in dr:
            nx=dx+x
            ny=dy+y
            if g[nx][ny]=='#':continue
            maze[nx][ny]='@'
            que.append((nx,ny))
    return maze

maze=[[0]*(w+2) for _ in range(h+2)]
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if g[i][j]=='#':continue
        mz=mk_maze(i,j,maze)
        res=find(mz)
        ans=max(res,ans)
print(res)