Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys
input = sys.stdin.buffer.readline

def main():
    N,M,R = map(int,input().split())
    r = list(map(int,input().split()))
    INF = 10**6
    root = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        root[i][i] = 0
    for i in range(M):
        A,B,C = map(int,input().split())
        root[A-1][B-1] = C
        root[B-1][A-1] = C
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                root[j][k] = min(root[j][k],root[j][i]+root[i][k])
                
    ans = INF
    for i in itertools.permutations(r):
        L = 0
        for j in range(R-1):
            L += root[i[j]-1][i[j+1]-1]
        ans = min(ans,L)
                
    print(ans)
    
if __name__ == "__main__":
    main()

Fixed submission:
import itertools
import numpy as np
import sys
input = sys.stdin.buffer.readline

def main():
    N,M,R = map(int,input().split())
    r = list(map(int,input().split()))
    INF = float('INF')
    root = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        root[i][i] = 0
    for i in range(M):
        A,B,C = map(int,input().split())
        root[A-1][B-1] = C
        root[B-1][A-1] = C
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if root[j][k] > root[j][i]+root[i][k]:
                    root[j][k] = root[j][i]+root[i][k]
                
    ans = INF
    for i in itertools.permutations(r):
        L = 0
        for j in range(R-1):
            L += root[i[j]-1][i[j+1]-1]
        ans = min(ans,L)
                
    print(ans)
    
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Q,K = map(int,input().split())
    Y = [list(map(int,input().split())) for _ in range(Q)]

    tree = [[] for _ in range(N)]
    dif = [10**15 for _ in range(N)]
    dif[K-1] = 0
    for i in range(N-1):
        tree[X[i][0]-1].append(X[i][1])
        tree[X[i][1]-1].append(X[i][0])

    queue = [K]
    while queue:
        a = queue.pop()
        for i in range(N-1):
            if X[i][0] == a:
                dif[X[i][1]-1] = min(dif[X[i][1]-1],dif[a-1]+X[i][2])
                tree[X[i][1]-1].remove(a)
                queue[0:0] = tree[a-1]
            if X[i][1] == a:
                dif[X[i][0]-1] = min(dif[X[i][0]-1],dif[a-1]+X[i][2])
                tree[X[i][0]-1].remove(a)
                queue[0:0] = tree[a-1]
        queue = list(set(queue))

    for i in range(Q):
        print(dif[Y[i][0]-1]+dif[Y[i][1]-1])

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Q,K = map(int,input().split())
    Y = [list(map(int,input().split())) for _ in range(Q)]

    tree = [[] for _ in range(N)]
    dif = [10**15 for _ in range(N)]
    dif[K-1] = 0
    for i in range(N-1):
        tree[X[i][0]-1].append((X[i][1]-1,X[i][2]))
        tree[X[i][1]-1].append((X[i][0]-1,X[i][2]))

    queue = [K-1]
    while queue:
        a = queue.pop()
        for i in tree[a]:
            s,t = i[0],i[1]
            if dif[s] == 10**15:
                dif[s] = dif[a]+t
                queue.append(s)

    for i in range(Q):
        print(dif[Y[i][0]-1]+dif[Y[i][1]-1])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
from scipy.sparse.csgraph import dijkstra

def main():
    N = int(input())
    INF = float('inf')
    dist = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        x,y = map(int,input().split())
        dist[x-1][y-1] = 1
        dist[y-1][x-1] = 1
        
    fen = dijkstra(dist,indices = 0)
    snu = dijkstra(dist,indices = N-1)
    fg = sg = 0
    for i in range(N):
        if fen[i] <= snu[i]:
            fg += 1
        else:
            sg += 1
            
    print("Fennec" if fg > sg else "Snuke")
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N = int(input())
    dist = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        dist[a-1].append(b-1)
        dist[b-1].append(a-1)

    def root(x):
        go = [False for _ in range(N)]
        d = [0 for _ in range(N)]
        go[x] = True
        q = deque([x])
        while q:
            now = q.pop()
            for fol in dist[now]:
                if go[fol]:
                    continue
                else:
                    d[fol] = d[now] + 1
                    go[fol] = True
                    q.append(fol)
        return d
    
    fen = root(0)
    snu = root(N-1)
    fg = sg = 0
    for i in range(N):
        if fen[i] <= snu[i]:
            fg += 1
        else:
            sg += 1
            
    print("Fennec" if fg > sg else "Snuke")

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(N)]
    dp = [0 for _ in range(M+1)]
    for i in range(N):
        for j in range(M-X[i][0]+1)[::-1]:
            dp[j+X[i][0]] = max(dp[j+X[i][0]],dp[j]+X[i][1])

    print(max(dp))

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N,W = map(int,input().split())
    use = [[] for _ in range(4)]
    wc,v = map(int,input().split())
    use[0].append(v)
    for _ in range(N-1):
        w,v = map(int,input().split())
        use[w-wc].append(v)

    for i in range(4):
        use[i].sort(reverse = True)
        use[i] = [0]+use[i]
        l = len(use[i])
        for x in range(l-1):
            use[i][x+1] += use[i][x]

    ans = 0
    for i in range(min(len(use[3]),W//(wc+3)+1)):
        Wa = W-(wc+3)*i
        for j in range(min(len(use[2]),Wa//(wc+2)+1)):
            Wb = Wa-(wc+2)*j
            for k in range(min(len(use[1]),Wb//(wc+1)+1)):
                Wc = Wb-(wc+1)*k
                l = min(len(use[0])-1,Wc//wc)
                point = use[0][l]+use[1][k]+use[2][j]+use[3][i]
                ans = max(point,ans)
                
    print(ans)
    
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort(reverse=True)
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 1
	sum(a) = A
	for i in range(N):
		if (A-sum_list[i])*2 >= a[i]:
			count += 1
		else:
			break

	print(count)

if __name__ == "__main__":
	main()


Fixed submission:
import sys
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort()
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 0
	for i in range(N-1):
		if 2*sum_list[i] < a[i+1]:
			count = i+1

	print(N-count)

if __name__ == "__main__":
	main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort(reverse=True)
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 1
	for i in range(N):
		if (sum(a)-sum_list[i])*2 >= a[i]:
			count += 1
		else:
			break

	print(count)

if __name__ == "__main__":
	main()

Fixed submission:
import sys
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort()
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 0
	for i in range(N-1):
		if 2*sum_list[i] < a[i+1]:
			count = i+1

	print(N-count)

if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def main():
    N = int(input())
    re = [[] for _ in range(N)]
    for i in range(N-1):
        p = int(input())
        re[p-1].append(i+1)

    def dep(x):
        if re[x] == []:
            return 0
        else:
            cl = []
            for ch in re[x]:
                cl.append(dep(ch))
                cl.sort(reverse = True)
            l = len(cl)
            return max(cl[i]+i+1 for i in range(l))
    
    print(dep(0))
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def main():
    N = int(input())
    re = [[] for _ in range(N)]
    for i in range(N-1):
        p = int(input())
        re[p-1].append(i+1)

    def dep(x):
        if re[x] == []:
            return 0
        else:
            cl = []
            for ch in re[x]:
                cl.append(dep(ch))
            cl.sort(reverse = True)
            l = len(cl)
            return max(cl[i]+i+1 for i in range(l))
    
    print(dep(0))
    
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    def point(x):
        use = a[:x]+a[x+K:]
        borf = a[x:x+K]
        score = 0
        for num in use:
            if num > 0:
                score += num
        if sum(borf) > 0:
            score += sum(borf)
        return(score)
        
    ans = 0
    for i in range(N-K+1):
        ans = max(ans,point(i))
        
    print(ans)
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    cum = [0]
    pluscum = [0]
    
    for i in range(N):
        cum.append(cum[-1]+a[i])
        if a[i] > 0:
            pluscum.append(pluscum[-1]+a[i])
        else:
            pluscum.append(pluscum[-1])

    ans = -(10**15)
    for i in range(N-K+1):
        ret = pluscum[i]+(pluscum[-1]-pluscum[i+K])+max((cum[i+K]-cum[i]),0)
        ans = max(ans,ret)
    
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
#import sys
#input = sys.stdin.buffer.readline

def main():
    S = str(input())
    five = ["dream","erase"]
    def dream(s):
        if len(s) == 0:
            return True
        elif len(s) < 5:
            return False
        else:
            if s[:5] not in five:
                return False
            else:
                if s[:5] == "dream":
                    sf = s[5:]
                    if s[:7] == "dreamer":
                        se = s[7:]
                        return (dream(sf) or dream(se))
                    else:
                        return dream(sf)
                if s[:5] == "erase":
                    sf = s[5:]
                    if s[:6] == "eraser":
                        ss = s[6:]
                        return (dream(sf) or dream(ss))
                    else:
                        return dream(sf)
                
    if dream(S):
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    main()

Fixed submission:
import sys
#input = sys.stdin.buffer.readline
sys.setrecursionlimit(20000+1)

def main():
    s = "".join(list(reversed(str(input()))))
    b = True
    
    while len(s) != 0:
        if len(s) >= 5:
            use = ["maerd","esare"]
            if s[:5] in use:
                s = s[5:]
            elif (len(s) >= 6 and s[:6] == "resare"):
                s = s[6:]
            elif (len(s) >= 7 and s[:7] == "remaerd"):
                s = s[7:]
            else:
                b = False
                break
        else:
            b = False
            break
            
    if b:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))
    b = a.copy()
    
    ans = 10**15
    for i in range(N):
        time = i*x+sum(b)
        ans = min(ans,time)
        for now in range(N):
            b[now] = min(b[now],a[(now-i-1+N)%N])

    print(ans)

if __name__ == "__main__":
    main()
    


Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))
    b = a.copy()
    
    ans = 10**15
    for i in range(N):
        time = i*x+sum(b)
        ans = min(ans,time)
        for now in range(N):
            b[now] = min(b[now],a[(now-i-1+N)%N])

    print(ans)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

def main():
    N,x = map(int,input().split())
    count = N
    N *= 2
    a = list(map(int,input().split()))
    ans = sum(a)
    a += a
    
    def segfunc(x,y):
        return min(x,y)
        
    def init(init_val):
        for i in range(N):
            seg[i+num-1] = init_val[i]
        for i in range(num-2,-1,-1):
            seg[i] = segfunc(seg[2*i+1],seg[2*i+2])
                
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p > 1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 10**15
    num = 2**(N-1).bit_length()
    seg = [ide_ele]*2*num
    init(a)
    
    for i in range(count-1):
        i += 1
        time = i*x
        for now in range(count):
            ret = query(now+count-i,now+count+1)
            time += ret
        ans = min(ans,time)
        
    print(ans)

if __name__ == "__main__":
    main()
    


Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))
    b = a.copy()
    
    ans = 10**15
    for i in range(N):
        time = i*x+sum(b)
        ans = min(ans,time)
        for now in range(N):
            b[now] = min(b[now],a[(now-i-1+N)%N])

    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
	N,A = map(int,input().split())
	x = list(map(int,input().split()))
	for i in range(N):
		x[i] -= A

	base = 50*50
	dp = np.zeros(base*2+1,dtype=int)
	dp[base] = 1
	for num in x:
		if num == 0:
			use = dp.copy()
			dp += use
		elif num > 0:
			use = dp[:-num].copy()
			dp[num:] += use
		else:
			use = dp[-num:].copy()
			dp[:num] += use

	print(dp[base]-1)

if __name__ == "__main__":
	main()

Fixed submission:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
	N,A = map(int,input().split())
	x = list(map(int,input().split()))
	for i in range(N):
		x[i] -= A

	base = 50*50
	dp = np.zeros(base*2+1,dtype=int)
	dp[base] = 1
	for num in x:
		if num == 0:
			use = dp.copy()
			dp += use
		elif num > 0:
			use = dp[:-num].copy()
			dp[num:] += use
		else:
			use = dp[-num:].copy()
			dp[:num] += use

	print(dp[base]-1)

if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
mod=998244353
def mod_pow(x,n):
    res=1
    while n>0:
        if n&1:
            res=res*x%mod
        x=x*x%mod
        n>>=1
    return res
def inverse_element(t):
    return mod_pow(t,mod-2)

n,m,k=map(int,input().split())
ans=0
p1=m*mod_pow(m-1,n-1)%mod
p2=1
for i in range(0,k+1):
    ans+=p1*p2%mod
    ans%=mod
    p1*=inverse_element(m-1)
    p2*=(n-i-1)
    p2*=inverse_element(i+1)
    p1%=mod
    p2%=mod
print(ans)

Fixed submission:
mod=998244353
def mod_pow(x,n):
    res=1
    while n>0:
        if n&1:
            res=res*x%mod
        x=x*x%mod
        n>>=1
    return res
def inverse_element(t):
    return mod_pow(t,mod-2)

n,m,k=map(int,input().split())
if m==1:
    if k==n-1:
        print(m)
    else:
        print(0)
    exit(0)
ans=0
p1=m*mod_pow(m-1,n-1)%mod
p2=1
for i in range(0,k+1):
    ans+=p1*p2%mod
    ans%=mod
    p1*=inverse_element(m-1)
    p2*=(n-i-1)
    p2*=inverse_element(i+1)
    p1%=mod
    p2%=mod
print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import sys

N, X, Y = map(int, input().split())
a = [[] for i in range(N)]
a[X - 1].append(Y - 1)
a[Y - 1].append(X - 1)
for i in range(N - 1):
	a[i].append(i + 1)
	a[i + 1].append(i)
ans = [0] * (N - 1)
for i in range(N - 1):
	b = [[0, i]]
	c = [False] * N
	d = [sys.maxsize] * N
	d[i] = 0
	while len(b):
		e = heapq.heappop(b)
		c[e[1]] = True
		for j in a[e[1]]:
			if c[j]:
				continue
			if e[0] + 1 < d[j]:
				d[j] = e[0] + 1
				heapq.heappush(b, [d[j], j])
	j = i + 1
	while j < N:
		ans[d[j] - 1] += 1
		j += 1
for i in ans:
	print(i)

Fixed submission:
import heapq
import sys

N, X, Y = map(int, input().split())
a = [[] for i in range(N)]
a[X - 1].append(Y - 1)
a[Y - 1].append(X - 1)
for i in range(N - 1):
	a[i].append(i + 1)
	a[i + 1].append(i)
ans = [0] * (N - 1)
for i in range(N - 1):
	b = [[0, i]]
	c = [False] * N
	d = [sys.maxsize] * N
	d[i] = 0
	while len(b):
		e = heapq.heappop(b)
		c[e[1]] = True
		for j in a[e[1]]:
			if c[j]:
				continue
			if e[0] + 1 < d[j]:
				d[j] = e[0] + 1
				heapq.heappush(b, [d[j], j])
	j = i + 1
	while j < N:
		ans[d[j] - 1] += 1
		j += 1
for i in ans:
	print(i)
Buggy python submission (verdict: Runtime Error):
import math

A, B = map(int, input().split())
c = math.gcd(A, B)
d = set()
i = 2
while i * i <= c:
	while c % i == 0:
		c /= i
		d.add(i)
	i += 1
if c != 1:
	d.add(c)
print(len(d) + 1)

Fixed submission:
def gcd(a, b):
	return gcd(b, a % b) if b else a

A, B = map(int, input().split())
c = gcd(A, B)
d = set()
i = 2
while i * i <= c:
	while c % i == 0:
		c /= i
		d.add(i)
	i += 1
if c != 1:
	d.add(c)
print(len(d) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
r.sort()
a = [[sys.maxsize] * N for i in range(N)]
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	a[i][i] = 0
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
ans = sys.maxsize
for i in itertools.permutations(r):
	b, j = 0, 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Fixed submission:
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
a = [[sys.maxsize for i in range(N)] for i in range(N)]
for i in range(N):
	a[i][i] = 0
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
r.sort()
ans = sys.maxsize
for i in itertools.permutations(r):
	b = 0
	j = 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
a = [[sys.maxsize for i in range(N)] for i in range(N)]
for i in range(N):
	a[i][i] = 0
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
r.sort()
ans = sys.maxsize
for i in itertools.permutations(r):
	b = 0
	j = 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Fixed submission:
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
a = [[sys.maxsize for i in range(N)] for i in range(N)]
for i in range(N):
	a[i][i] = 0
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
r.sort()
ans = sys.maxsize
for i in itertools.permutations(r):
	b = 0
	j = 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().strip().split())
  c_h, c_w = map(int, input().strip().split())
  d_h, d_w = map(int, input().strip().split())
  maze = [list(input().strip()) for _ in range(h)]
  visited = [[0] * w for _ in range(h)]
  
  def bfs():
    dq = deque([(c_h-1, c_w-1, 0)])
    while dq:
      (ih, iw, cnt) = dq.pop()
      if visited[ih][iw]:
        continue
      visited[ih][iw] = 1
      
      if ih == d_h-1 and iw == d_w-1:
        return cnt
      
      for dh in range(-2, 3):
        for dw in range(-2, 3):
          if not (0 <= ih + dh < h and 0 <= iw + dw < w) \
             or visited[ih + dh][iw + dw] == 1 \
             or maze[ih + dh][iw + dw] == '#':
            continue
          if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dq.append((ih + dh, iw + dw, cnt))
          else:
            dq.appendleft((ih + dh, iw + dw, cnt+1))
      
    return -1
  print(bfs())
  
if __name__=='__main__':
  main()



Fixed submission:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().strip().split())
  c_h, c_w = map(int, input().strip().split())
  d_h, d_w = map(int, input().strip().split())
  maze = [list(input().strip()) for _ in range(h)]
  visited = [[0] * w for _ in range(h)]
  
  def bfs():
    dq = deque([(c_h-1, c_w-1, 0)])
    while dq:
      (ih, iw, cnt) = dq.pop()
      if visited[ih][iw]:
        continue
      visited[ih][iw] = 1
      
      if ih == d_h-1 and iw == d_w-1:
        return cnt
      
      for dh in range(-2, 3):
        for dw in range(-2, 3):
          if not (0 <= ih + dh < h and 0 <= iw + dw < w) \
             or visited[ih + dh][iw + dw] == 1 \
             or maze[ih + dh][iw + dw] == '#':
            continue
          if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dq.append((ih + dh, iw + dw, cnt))
          else:
            dq.appendleft((ih + dh, iw + dw, cnt+1))
      
    return -1
  print(bfs())
  
if __name__=='__main__':
  main()