Submission #9476488

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math
import sys
m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF = 10 ** 2 
(H, W) = list(map(int,input().split()))
# print(H,W)
S = []
N = H * W
c = [[INF for j in range(N)] for u in range(N)]
d = [[INF for j in range(H*W)] for u in range(H*W)]
for k in range(N):
    c[k][k] = 0
    d[k][k] = 0
for i in range(H):
    S.append(input())
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF = 10 ** 2 
(H, W) = list(map(int,input().split()))
# print(H,W)

S = []
N = H * W
c = [[INF for j in range(N)] for u in range(N)]
d = [[INF for j in range(H*W)] for u in range(H*W)]

for k in range(N):
    c[k][k] = 0
    d[k][k] = 0

for i in range(H):
    S.append(input())

#print(S)

def vindex(i,j):
    global W
    return W * (i-1) + j -1

# print(vindex(H,W))
for i in range(1,H+1):
    for j in range(1,W+1):
        index = vindex(i,j)
        s = S[i-1][j-1]
        # print(index,s)
        if i != 1:
            index_t = vindex(i-1,j)
            sup = S[i-2][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
                
        if i != H:
            index_t = vindex(i+1,j)
            sup = S[i][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != 1:
            index_t = vindex(i,j-1)
            sup = S[i-1][j-2]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != W:
            index_t = vindex(i,j+1)
            sup = S[i-1][j]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1

#print("D",d)


for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j] , d[i][k]+d[k][j])
    #print(k,d)

ans = 0 
for i in range(N):
    for j in range(N):

        if (d[i][j] != INF and d[i][j] > ans):
            ans = d[i][j]

print(ans)

Submission Info

Judge Result