Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
dist={}
queue=set()
dist[(0,0)]=0
queue.add((0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    dist[(i,j)]=10**9
    queue.add((i,j))
#print(queue)

#dkjstra
while(True):
  d=10**9
  min_q=None
  for q in queue:
    if dist[q]<d:
      min_q=q
      d=dist[q]
      
  #print(min_q,d)
  if min_q==None:
    break
    
  queue.remove(min_q)
  candlist=graph[min_q]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[min_q]+dd)
  
print(dist[(H,W)])

Fixed submission:
import heapq

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
dist={}
hq=[]
dist[(0,0)]=0
heapq.heappush(hq,(0,0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    dist[(i,j)]=10**9
    heapq.heappush(hq,(i+j,i,j))
#print(queue)

#dkjstra
while(True):
  if len(hq)==0:
    break

  ij,ii,jj=heapq.heappop(hq)
  
  candlist=graph[(ii,jj)]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[(ii,jj)]+dd)
  
print(dist[(H,W)])

Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
used={}
dist={}
queue=set()
used[(0,0)]=False
dist[(0,0)]=0
queue.add((0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    used[(i,j)]=False
    dist[(i,j)]=10**9
    queue.add((i,j))
#print(queue)

#dkjstra
while(True):
  d=10**9
  min_q=None
  for q in queue:
    if not used[q] and dist[q]<d:
      min_q=q
      d=dist[q]
      
  #print(min_q,d)
  if min_q==None:
    break
    
  used[min_q]=True
  candlist=graph[min_q]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[min_q]+dd)
  
print(dist[(H,W)])

Fixed submission:
import heapq

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
dist={}
hq=[]
dist[(0,0)]=0
heapq.heappush(hq,(0,0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    dist[(i,j)]=10**9
    heapq.heappush(hq,(i+j,i,j))
#print(queue)

#dkjstra
while(True):
  if len(hq)==0:
    break

  ij,ii,jj=heapq.heappop(hq)
  
  candlist=graph[(ii,jj)]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[(ii,jj)]+dd)
  
print(dist[(H,W)])

Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
used={}
dist={}
queue=set()
used[(0,0)]=False
dist[(0,0)]=0
queue.add((0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    used[(i,j)]=False
    dist[(i,j)]=10**9
    queue.add((i,j))
#print(queue)

#dkjstra
while(True):
  d=10**9
  min_q=None
  for q in queue:
    if not used[q] and dist[q]<d:
      min_q=q
      d=dist[q]
      
  #print(min_q,d)
  if min_q==None:
    break
    
  used[min_q]=True
  candlist=graph[min_q]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[min_q]+dd)
  
print(dist[(H,W)])

Fixed submission:
import heapq

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

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
dist={}
hq=[]
dist[(0,0)]=0
heapq.heappush(hq,(0,0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    dist[(i,j)]=10**9
    heapq.heappush(hq,(i+j,i,j))
#print(queue)

#dkjstra
while(True):
  if len(hq)==0:
    break

  ij,ii,jj=heapq.heappop(hq)
  
  candlist=graph[(ii,jj)]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[(ii,jj)]+dd)
  
print(dist[(H,W)])