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 collections import deque


def dfs(maze, start):
    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([0, start])
    dist = [[-1] * w for _ in range(h)]

    depth, i, j = -1, -1, -1

    while q:
        depth, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = depth
        for di, dj in move:
            ni, nj = i + di, j + dj

            outside = not 0 <= ni < h or not 0 <= nj < w
            is_wall = maze[ni][nj] == "#"
            visited = dist[ni][nj] != -1

            if outside or is_wall or visited:
                continue

            q.append((depth + 1, (ni, nj)))

    return depth, i, j


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

maze = []

for _ in range(h):
    maze.append(input())

answer = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            depth, i, j = dfs(maze, (i, j))
            answer = max(answer, depth)

print(answer)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<ll> vll;
const int MN = 21, MOD=1e9+7;
ll lcm (ll a, ll b) {return a*b/__gcd(a,b);}
ll multiplyMod(ll a, ll b) { return (a % MOD * b % MOD) % MOD; }
ll addMod(ll a, ll b) { return (a % MOD + b % MOD) % MOD; }
ll subMod(ll a, ll b) { return (a % MOD - b % MOD) % MOD; }
ll fpow(ll b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
//remember to pop from your queues idot
int dist[MN][MN][MN][MN];
int grid[MN][MN];
int h, w;
char temp;
vpii dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void traverse(int sx, int sy) {
    queue<pii> q;
    q.push({sx, sy});
    dist[sx][sy][sx][sy] = 0;
    while (!q.empty()) {
        int x = q.front().f, y = q.front().s;
        q.pop();
        for (pii moves : dirs) {
            int a = moves.f, b = moves.s;
            int nx = a + x, ny = y + b;
            if (nx > h || nx == 0 || ny > w || ny == 0 || grid[nx][ny]) {
                continue;
            }
            if (dist[sx][sy][x][y] + 1 < dist[sx][sy][nx][ny]) {
                dist[sx][sy][nx][ny] = 1 + dist[sx][sy][x][y];
                q.push({nx, ny});
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> h >> w;
    for (int i = 1; i<=h;i++) {
        for (int j = 1; j<=w;j++) {
            cin >> temp;
            grid[i][j] = (temp == '#');
        }
    }
    for (int i = 1; i<=h;i++) {
        for (int j = 1; j<=w;j++) {
            for (int k = 1; k<=h;k++) {
                for (int l = 1; l<=w;l++) {
                    dist[i][j][k][l] = INT_MAX;
                }
            }
        }
    }
    for (int i = 1; i<=h;i++) {
        for (int j = 1; j <= w; j++) {
            if (grid[i][j]) { continue; }
            traverse(i, j);
        }
    }
    int res = 0;
    for (int i = 1; i<=h;i++) {
        for (int j = 1; j<=w;j++) {
            for (int k = 1; k<=h;k++) {
                for (int l = 1; l<=h;l++) {
                    if (dist[i][j][k][l] == INT_MAX) {
                        continue;
                    }
                    res = max(res, dist[i][j][k][l]);
                }
            }
        }
    }
    cout << res << "\n";

    return 0;
}
//lol

Submission status: Runtime Error

Solution code:
m = 10 ** 9 + 7
f = [1]

for i in range(10 ** 5 + 5):
    f.append(f[-1] * (i + 1) % m)

def nCr(n,r,mod = m):
    return f[n] * pow(f[r],m - 2,m) * pow(f[n-r],m - 2,m) % m

n,k = map(int,input().split())

a = list(map(int,input().split()))

a.sort()

ans = 0
for i in range(n - k + 1):
    ans += (a[-1-i] - a[i]) * nCr(n - 1 - i,k - 1)
    ans %= m

print(ans)

Submission status: Runtime Error

Solution code:
from collection import deque

def bfs(loc):
    global tem_ans
    d = [[float('inf')] * w for i in range(h)]

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

    que = deque([])
    que.append(loc)
    d[loc[0]][loc[1]] = 0

    while que:
        p = popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.append([nx,ny])

                if tem_ans < d[nx][ny]:
                    tem_ans = d[nx][ny]
    return tem_ans

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

loc = []
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            loc = [i,j]
        else:
            continue
        ans = max(ans,bfs(loc))

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

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

maze = []
for h in range(H):
  s = input()
  maze.append(s)

def BFS(i,j):
  place = np.zeros((H,W))
  dist = 0
  queue = deque()
  queue.append((i,j,0))
  while queue:
    i,j,d = queue.popleft()
    if not place[i][j]:
      dist = max(dist,d)
      place[i][j] = 1
      for di,dj in [(1,0),(-1,0),(0,1),(0,-1)]:
        if (0 =< i+di and i+di < H and 0 =< j+dj and j+dj < W):
          if maze[i+di][j+dj] == '.' and place[i+di][j+dj] == 0:
            queue.append((i+di,j+dj,d+1))
  return dist

ans = 0
for h in range(H):
  for w in range(W):
    if maze[h][w] == '.':
      ans = max(ans,BFS(h,w))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

H,W=[int(i) for i in input().split()]
# c=[[i for i in input().split()] for _ in range(h)]
C=list(input() for _ in range(H))
C=list(list(i) for i in C) #visited_listを用いずに壁にしていく方法ではリスト化が必要

def bfs(maze,s1,s2,g1,g2):
    for y in range(H):
        for x in range(W):
            if maze[y][x]!='#':
                maze[y][x]=10**9

    maze[s1][s2]=0
    que=deque([[s1,s2]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if nexty >= 0 and nexty < H and nextx >= 0 and nextx < W:
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    return maze[g1][g2]

ans=0
for s1,c_w in enumerate(C):
    for s2,c in enumerate(c_w):
        if C[s1][s2]="#":
            break
        else:
            for g1,c_w in enumerate(C):
                for g2,c in enumerate(c_w):
                    if C[g1][g2]="#":
                        break
                    else:
                        temp=bfs(C,s1,s2,g1,g2)
                        ans=max(temp,ans)
print(ans)

Submission status: Runtime Error

Solution code:
#151-D:BFS
from collections import deque
#スタート地点loc=(sx,sy)を決めたときのゴールをbfsで求める
def bfs(loc):
    global tem_ans
    d=[[float('inf')]*w for i in range(h)]

    #進む方向を決める
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

    que=deque([])
    que.append(loc)
    d[loc[0]][loc[1]]=0

    #遷移していってこれ以上遷移できない状態まで埋める
    while que:
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            #遷移可能かどうか調べる
            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and d[nx][ny]==float('inf'):
                #移動後の距離を保存
                d[nx][ny]=d[p[0]][p[1]]+1
                que.append([nx,ny])

                if tem_ans<d[nx][ny]:
                    tem_ans=d[nx][ny]
    return tem_ans



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

loc=[]
for i in range(h):
    for j in range(w):
        #通路をスタート地点に設定する
        if maze[i][j]!='#':
            loc=[i,j]

        ans=max(ans,bfs(loc))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import math

H,W=[int(i) for i in input().split()]
# c=[[i for i in input().split()] for _ in range(h)]
C=list(input() for _ in range(H))
C=list(list(i) for i in C) #visited_listを用いずに壁にしていく方法ではリスト化が必要

def bfs(maze,s1,s2,g1,g2):
    for y in range(H):
        for x in range(W):
            if maze[y][x]!='#':
                maze[y][x]=math.inf

    maze[s1][s2]=0
    que=deque([[s1,s2]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if nexty >= 0 and nexty < H and nextx >= 0 and nextx < W:
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    return maze[g1][g2]

ans=0
for s1,c_w in enumerate(C):
    for s2,c in enumerate(c_w):
        if C[s1][s2]!="#":
            for g1,c_w in enumerate(C):
                for g2,c in enumerate(c_w):
                    if C[g1][g2]!="#":
                        temp=bfs(C,s1,s2,g1,g2)
                        ans=max(temp,ans)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVETSE(c) reverse((c).begin(),(c).end())
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define ALL(a)  (a).begin(),(a).end()
// int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> T maxt(T x,T y) {
    if (x>y) return x;
    else return y;
}
template<class T> T mint(T x,T y) {
    if (x>y) return y;
    else return x;
}
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

long long m = 1e9+7, mod = 1e9+7;
//逆元　a/b の modをとるとき -> a*modinv(b)%mod
long long modinv(long long a, long long m = 1e9+7) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

/* //約数列挙
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}*/


int main() {
  int H,W;
  string s;
  cin >> H >> W;
  const int INF = 1000000;

  vector<string> S(1,string(W+2,'#'));
  vector<Vi> v(H*W, Vi(H*W,INF));
  REP(i,H) {
    cin >> s;
    s = '#' + s + '#';
    S.push_back(s);
  }
  S.push_back(string(W+2,'#'));

  FOR(i,1,H+1){
    FOR(j,1,W+1) {
      // cout << S[i][j]<< endl;
      if (S[i][j] == '.' && S[i][j+1] == '.') v[(i-1)*H+j-1][(i-1)*H+j] = v[(i-1)*H+j][(i-1)*H+j-1] = 1;
      if (S[i][j] == '.' && S[i+1][j] == '.') v[(i-1)*H+j-1][(i)*H+j-1] = v[(i)*H+j-1][(i-1)*H+j-1] = 1;
      v[(i-1)*H+j-1][(i-1)*H+j-1] = 0;
    }
  }

REP(k,H*W){
  REP(i,H*W) {
    REP(j,H*W) {
      v[i][j] = min(v[i][j],v[i][k]+v[k][j]);
      }
  }
}
int ans=0;
REP(i,H*W) {
  REP(j,H*W) {
    if (v[i][j] > ans && v[i][j] < INF) ans = v[i][j];
  }
}
  
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
from collections import deque

d=[(1,0),(0,1),(-1,0),(0,-1)]
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
def BFS(i,j):
    q = deque()
    dist = [[-1]*W for _ in range(H)]
    if M[i][j] == '.':

        #前処理
        Ma = 0
        q.append((i, j))#スタート地点挿入
        dist[i][j] = 0
        while q:
            cx,cy = q.popleft()
            for nx,ny in d:
                x ,y= cx+nx,cy+ny
                if 0<= x < H and 0<= y < W and M[x][y] == "." and dist[x][y]==-1:
                    dist[x][y]=dist[cx][cy]+1
                    Ma = max(Ma,dist[x][y])
                    q.append((x,y))
        return Ma
for i in range(H):#全部の地点でBFSをためす
    for j in range(W):
        Max_list.append(BFS(i,j))

print(max(Max_list))

Submission status: Runtime Error

Solution code:
from collections import deque

d=[(1,0),(0,1),(-1,0),(0,-1)]
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
def BFS(i,j):
    q = deque()
    dist = [[-1]*W for _ in range(H)]
    if M[i][j] == '.':

        #前処理
        Ma = 0
        q.append((i, j))#スタート地点挿入
        dist[i][j] = 0
        while q:
            cx,cy = q.popleft()
            for nx,ny in d:
                x ,y= cx+nx,cy+ny
                if 0<= x < H and 0<= y < W and M[x][y] == "." and dist[x][y]==-1:
                    dist[x][y]=dist[cx][cy]+1
                    Ma = max(Ma,dist[x][y])
                    q.append((x,y))
        return Ma
for i in range(H):#全部の地点でBFSをためす
    for j in range(W):
        Max_list.append(BFS)

print(max(Max_list))

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
s=[input() for _  in range(H)]
G=[["#"]*(W+2) for _ in range(H+2)]

for i in range(H):
    for j in range(W):
        G[i+1][j+1]=s[i][j]

def search(y,x):
    q=[(y,x)]
    d=[[-1]*(W+2) for _ in range(H+2)]
    d[y][x]=0
    while q:
        y1,x1=q.pop()
        for y2,x2 in ((y1+1,x1),(y1,x1+1),(y1-1,x1),(y1,x1-1)):
            if G[y2][x2]=="." and d[y2][x2]==-1:
                d[y2][x2]=d[y1][x1]+1
                q.append((y2,x2))
    return max(max(_) for _ in d)


for i in range(H):
    for j in range(W):
        if G[i+1][j+1]==".":
            ans=max(search(i+1,j+1),ans)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque((i,j))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
f=H*W
d=[[0]*f for _ in range(f)]


s=[input() for _  in range(H)]
    
for i in range(H):
    for j in range(W-1): 
        cnt=W*i+j
        d[cnt+1][cnt]=s[i][j]==s[i][j+1]=="."
        d[cnt][cnt+1]=s[i][j]==s[i][j+1]=="."
       
for i in range(H-1):
    for j in range(W): 
        cnt=W*i+j
        d[cnt][cnt+W]=s[i][j]==s[i+1][j]=="."
        d[cnt+W][cnt]=s[i][j]==s[i+1][j]=="."
        
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
csr=np.array(d)


ans=-1
for i in range(H):
    for j in range(W): 
        cnt=W*i+j
        k=shortest_path(csr, indices=cnt)
        for q in range(f):
            if k[q]>=f+1:k[q]=-1
        ans=max(ans,max(k))

print(int(ans))

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
f=H*W
d=[[0]*f for _ in range(f)]


s=[input() for _  in range(H)]
    
for i in range(H):
    for j in range(W-1): 
        cnt=W*i+j
        d[cnt+1][cnt]=s[i][j]==s[i][j+1]=="."
        d[cnt][cnt+1]=s[i][j]==s[i][j+1]=="."
       
for i in range(H-1):
    for j in range(W): 
        cnt=W*i+j
        d[cnt][cnt+W]=s[i][j]==s[i+1][j]=="."
        d[cnt+W][cnt]=s[i][j]==s[i+1][j]=="."
        
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
csr=np.array(d)


ans=-1
for i in range(H):
    for j in range(W): 
        cnt=W*i+j
        k=shortest_path(csr, indices=cnt)
        for q in range(f):
            if k[q]>=f+1:k[q]=-1
        ans=max(ans,max(k))

print(int(ans)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
f=H*W
d=[[0]*f for _ in range(f)]


s=[input() for _  in range(H)]
    
for i in range(H):
    for j in range(W-1): 
        cnt=W*i+j
        d[cnt+1][cnt]=s[i][j]==s[i][j+1]=="."
        d[cnt][cnt+1]=s[i][j]==s[i][j+1]=="."
       
for i in range(H-1):
    for j in range(W): 
        cnt=W*i+j
        d[cnt][cnt+W]=s[i][j]==s[i+1][j]=="."
        d[cnt+W][cnt]=s[i][j]==s[i+1][j]=="."
        
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
csr=np.array(d)


ans=-1
for i in range(H):
    for j in range(W): 
        cnt=W*i+j
        ans=max(ans,max(shortest_path(csr, indices=cnt)))

print(int(ans))

Submission status: Runtime Error

Solution code:
from collections import deque
 
H,W = map(int,readline().split())
H += 2; W += 2
grid = '#' * W
for _ in range(H-2):
    grid += '#' + readline().rstrip().decode() + '#'
grid += '#' * W
 
def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '#':
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return max(x for x in dist if x < INF)
 
answer = max(bfs(v) for v in range(H*W) if grid[v] != '#')
print(answer)

Submission status: Runtime Error

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

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

def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == -1:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, s))

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

Submission status: Runtime Error

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

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

def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == -1:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(max(distance))

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

Submission status: Runtime Error

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

def BFS(a,b):
  times = 0
  queue = [[a, b]]
  old_queue = []
  while True:
    new_queue = []
    changed = False
    for x, y in queue:
      if x+1 < H and atlas[x+1][y] != "#" and not [x+1, y] in old_queue:
        new_queue.append([x+1, y])
        old_queue.append([x+1, y])
        changed = True
      if x-1 >= 0 and atlas[x-1][y] != "#" and not [x-1, y] in old_queue:
        new_queue.append([x-1, y])
        old_queue.append([x-1, y])
        changed = True
      if y+1 < W and atlas[x][y+1] != "#" and not [x, y+1] in old_queue:
        new_queue.append([x, y+1])
        old_queue.append([x, y+1])
        changed = True
      if y-1 >= 0 and atlas[x][y-1] != "#" and not [x, y-1] in old_queue:
        new_queue.append([x, y-1])
        old_queue.append([x, y-1])
        changed = True
    queue = new_queue
    if not changed:
      break
    times += 1
  return times

TIMES = 0
for j in range(H):
  for k in range(W):
    if atlas[j][k] == "#":
      break
    new_TIMES = BFS(j, k)
    if new_TIMES > TIMES:
      TIMES = new_TIMES
      
print(TIMES)

Submission status: Runtime Error

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

Q =deque()

M = []
M.append("#" * (W+2)) 
for i in range(H):
  M.append("#" + input() + "#")
  if M[i+1].find("."):
    x, y = i+1, M[i+1].find(".") + 2
M.append("#" * (W+2))
N = np.zeros((H+2,W+2))
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
Q.append((x,y))
while Q:
  (x,y) = Q.pop()
  for a, b in dirs:
    if M[x+a][y+b] == "." and N[x+a][y+b] == 0 or N[x+a][y+b] > N[x][y]+1:
      N[x+a][y+b] = N[x][y] + 1
      Q.append((x+a, y+b))

idx = np.unravel_index(np.argmax(N), N.shape)
Q.append(idx)
N = np.zeros((H+2,W+2))
while Q:
  (x,y) = Q.pop()
  for a, b in dirs:
    if M[x+a][y+b] == "." and N[x+a][y+b] == 0 or N[x+a][y+b] > N[x][y]+1:
      N[x+a][y+b] = N[x][y] + 1
      Q.append((x+a, y+b))
print (int(np.max(N)))

Submission status: Runtime Error

Solution code:
#import math
#INF = math.inf
h,w = map(int,input().split())
n = h*w

field = []
for i in range(h):
    field.append(input())

dist = [[INF] * n for _ in range(n)]

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        if j + 1 < w and field[i][j+1] != "#":
            dist[i * w + j][i * w + j + 1] = 1
            dist[i * w + j + 1][i * w + j] = 1
        if i + 1 < h and field[i+1][j] != "#":
            dist[i * w + j][(i+1) * w + j] = 1
            dist[(i+1) * w + j][i * w + j] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k])

ans = 0
for i in range(n):
    for j in range(n):
        if(i==j):continue
        if(dist[i][j]==INF):continue
        ans = max(ans,dist[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
import math
INF = math.inf
h,w = map(int,input().split())
n = h*w

field = []
for i in range(h):
    field.append(input())

dist = [[INF] * n for _ in range(n)]

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        if j + 1 < w and field[i][j+1] != "#":
            dist[i * w + j][i * w + j + 1] = 1
            dist[i * w + j + 1][i * w + j] = 1
        if i + 1 < h and field[i+1][j] != "#":
            dist[i * w + j][(i+1) * w + j] = 1
            dist[(i+1) * w + j][i * w + j] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k])

ans = 0
for i in range(n):
    for j in range(n):
        if(i==j):continue
        if(dist[i][j]==INF):continue
        ans = max(ans,dist[i][j])

print(ans)

Submission status: Runtime Error

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

field = []
for i in range(h):
    field.append(input())

dist = [[INF] * n for _ in range(n)]

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        if j + 1 < w and field[i][j+1] != "#":
            dist[i * w + j][i * w + j + 1] = 1
            dist[i * w + j + 1][i * w + j] = 1
        if i + 1 < h and field[i+1][j] != "#":
            dist[i * w + j][(i+1) * w + j] = 1
            dist[(i+1) * w + j][i * w + j] = 1

for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k] = min(dist[j][k],dist[j][i],dist[i][k])

ans = 0
for i in range(n):
    for j in range(n):
        if(i==j):continue
        if(dist[i][j]==INF):continue
        ans = max(ans,dist[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for s_x, s_y in  [(i, j) for i in range(h) for j in range(w)]:
    if g[s_x][s_y] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = (-1, -1)
    cur = (s_x, s_y)
    cnt = 0
    queue = deque([(cur, pre, cnt)])
    queue_pop = queue.pop
    queue_append = queue.append
    while queue:
        cur, pre, cnt = queue_pop()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        dp_cnt = dp[c_x][c_y]
        if not dp_cnt or dp_cnt > cnt:
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = (cur[0] + x, cur[1] + y)
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue_append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for start in  [[i, j] for i in range(h) for j in range(w)]:
    if g[start[0]][start[1]] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = [-1, -1]
    cur = start
    cnt = 0
    queue = deque([[cur, pre, cnt]])
    while stack:
        cur, pre, cnt = queue.popleft()
        c_x, c_y = cur
        if not dp[c_x][c_y] or (dp[c_x][c_y] and dp[c_x][c_y] > cnt):
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = [cur[0] + x, cur[1] + y]
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue.append([next, cur, cnt + 1])

    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

INF = 10000000000

h, w = map(int, input().split())
s = [] * w

for i in range(h):
    lateral = input()
    s.append(lateral)

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


def bfs(start_x, start_y):
    que = deque()
    d = [[INF for _ in range(w)] for _ in range(h)]
    que.append([start_x, start_y])
    d[start_y][start_x] = 0

    while len(que) > 0:
        p = que.popleft()
        for i in range(4):
            next_x = p[0] + dx[i]
            next_y = p[1] + dy[i]

            if 0 <= next_x < w and 0 <= next_y < h and s[next_y][next_x] != "#" and d[next_y][next_x] == INF:
                que.append([next_x, next_y])
                d[next_y][next_x] = d[p[0]][p[1]] + 1
    print(max(d))
    return max(d)

ans = 0

for y in range(h):
    for x in range(w):
        ans = max(ans, bfs(x, y))

print(ans)

Submission status: Runtime Error

Solution code:
h, w = list(map(int, input().sprit()))
root = [[""] * w] * h
for i in range(h):
  root[i] = input.sprit()
max_h = h - 1
max_w = w - 1

Submission status: Runtime Error

Solution code:
import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
  return ma
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        c[sx,sy]=1
        BFS((sx,sy),c,d)
        ma=max(np.max(d),ma)
  print(ma)

main()