Problem p02735 (python)

Fixed submission:
import itertools

H,W=map(int, input().split())
garden=[]

for i in range(H):
    garden.append(list(input().replace(".","1").replace("#","0")))

#print(garden)
dct=[(1,0),(0,1),(-1,0),(0,-1)]
#garden=[[1,0,1,0,1],[0,1,0,1,0],[1,0,1,0,1],[0,1,0,1,0],[1,0,1,0,1]]
#H,W=5,5
start=(0,0)
goal=(H-1,W-1)
path=[start]
d=[ [i+j for i in range(W)] for j in range(H)]
#print(d)
done=[(0,0)]
for i, j in itertools.product(range(H),range(W)):
    color=garden[i][j]
    for each in dct:
        di,dj=each[0],each[1]
        if i+di<H and j+dj< W and i+di>=0 and j+dj>=0 and  garden[i+di][j+dj]==color:
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j])
            done.append((i+di,j+dj))
            #print((i,j),(i+di,j+dj))
            #print("same")
        elif i+di<H and j+dj< W and i+di>=0 and j+dj>=0 :
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j]+1)
            done.append((i+di,j+dj))
            #print((i,j),(i+di,j+dj))
            #print("not same")
    #print(d)
if int(garden[0][0])+int(garden[H-1][W-1])==0:
  print(int((d[H-1][W-1]+1)/2)+1)
else:
  print(int((d[H-1][W-1]+1)/2))

Buggy submission (verdict: Runtime Error):
import itertools
 
H,W=map(int, input().split())
garden=[]
 
for i in range(H):
    garden.append(list(input().replace(".","1").replace("#","0")))
 
#print(garden)
dct=[(1,0),(0,1),(-1,0),(0,-1)]
#garden=[[1,0,1,0,1],[0,1,0,1,0],[1,0,1,0,1],[0,1,0,1,0],[1,0,1,0,1]]
#H,W=5,5
start=(0,0)
goal=(H-1,W-1)
path=[start]
d=[ [i+j for i in range(W)] for j in range(H)]
#print(d)
done=[(0,0)]
for i, j in itertools.product(range(H),range(W)):
    color=garden[i][j]
    for each in dct:
        di,dj=each[0],each[1]
        if i+di<H and j+dj< W and i+di>=0 and j+dj>=0 and  garden[i+di][j+dj]==color:
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j])
            done.append((i+di,j+dj))
            #print((i,j),(i+di,j+dj))
            #print("same")
        elif i+di<H and j+dj< W and i+di>=0 and j+dj>=0 :
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j]+1)
            done.append((i+di,j+dj))
            #print((i,j),(i+di,j+dj))
            #print("not same")
    #print(d)
if int(garden[0][0])+int(garden[H-1][W-1])==0:
  print(int((d[H-1][W-1]+1)/2)+1)
else:
  print(int((d[H-1][W-1]+1)/2))import itertools
 
H,W=map(int, input().split())
garden=[]
 
for i in range(H):
    garden.append(list(input().replace(".","1").replace("#","0")))
 
#print(garden)
dct=[(1,0),(0,1)]
#garden=[[1,0,1,0,1],[0,1,0,1,0],[1,0,1,0,1],[0,1,0,1,0],[1,0,1,0,1]]
#H,W=5,5
start=(0,0)
goal=(H-1,W-1)
path=[start]
d=[ [i+j for i in range(W)] for j in range(H)]
#print(d)
done=[(0,0)]
for i, j in itertools.product(range(H),range(W)):
    color=garden[i][j]
    for each in dct:
        di,dj=each[0],each[1]
        if i+di<H and j+dj< W and i+di>=0 and j+dj>=0 and  garden[i+di][j+dj]==color:
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j])
            done.append((i+di,j+dj))
            #print((i,j),(i+di,j+dj))
            #print("same")
        elif i+di<H and j+dj< W and i+di>=0 and j+dj>=0 :
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j]+1)
            done.append((i+di,j+dj))
            #print((i,j),(i+di,j+dj))
            #print("not same")
    #print(d)
if int(garden[0][0])+int(garden[H-1][W-1])==0:
  print(int((d[H-1][W-1]+1)/2)+1)
else:
  print(int((d[H-1][W-1]+1)/2))