Buggy python submission (verdict: Time Limit Exceeded):

#####

import numpy as np
# from numpy import int32, int8
from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize, depth, nextParams: deque, usedRC0: set):
	
	if (row0,col0) in usedRC0: return None
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	nextUsedRC0=set()
	nextUsedRC0.add((row0,col0))
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				hwi=(hi,wi)
				if c:
					visited[hi-row0,wi-col0]=True
					if hwi in usedRC0: break
					nextUsedRC0.add(hwi)
				else:
					next.add(hwi)
			if wi>0 and visited[hi-row0,wi-1-col0]:
				hwi=(hi,wi)
				if c:
					visited[hi-row0,wi-col0]=True
					if hwi in usedRC0: break
					nextUsedRC0.add(hwi)
				else:
					next.add(hwi)
		if not visited[hi-row0].any(): break
	usedRC0.update(nextUsedRC0)
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
		print(flipSize)
		sys.exit(0)
					
# 	print("next",next)
	
	if len(next)==0: return None
	
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	
	for nrc in next:
		if nrc in usedRC0: continue
		p=(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize, depth+1)
		nextParams.append(p)


def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."


# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize, 0)
	nextParams.append(p)
	
	usedRC0=set()
	while len(nextParams)>0:
		nextDepth=nextParams[0][-1]
		nextQ=[]
		while len(nextParams)>0 and nextParams[0][-1]==nextDepth:
			nextQ.append(nextParams.popleft())
		
		nextQ=sorted(nextQ, key=lambda x: (x[3],x[4]))
		for param in nextQ:
			travel(*param, nextParams=nextParams, usedRC0=usedRC0)


if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)


Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Buggy python submission (verdict: Time Limit Exceeded):

#####

import numpy as np
# from numpy import int32, int8
from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize, nextParams: deque, usedRC0: set):
	
	if (row0,col0) in usedRC0: return None
	usedRC0.add((row0,col0))
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
					usedRC0.add((hi,wi))
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
					usedRC0.add((hi,wi))
				else:
					next.add((hi,wi))
		if not visited[hi-row0].any(): break
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
		print(flipSize)
		sys.exit(0)
					
# 	print("next",next)
	
	if len(next)==0: return None
	
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	
# 	next=sorted(next, key=lambda x: -(x[0]+x[1]))
	
	for nrc in next:
		if nrc in usedRC0: continue
		p=(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize)
		nextParams.append(p)


def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."


# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))
# 	from matplotlib import pyplot as plt
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
	nextParams.append(p)
	
	usedRC0=set()
	while len(nextParams)>0:
		param=nextParams.popleft()
		travel(*param, nextParams=nextParams, usedRC0=usedRC0)


if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)


Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Buggy python submission (verdict: Time Limit Exceeded):

#####

import numpy as np
# from numpy import int32, int8
from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize, nextParams: deque, usedRC0: set):
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
					usedRC0.add((hi,wi))
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
					usedRC0.add((hi,wi))
				else:
					next.add((hi,wi))
		if not visited[hi-row0].any(): break
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
		print(flipSize)
		sys.exit(0)
					
# 	print("next",next)
	
	if len(next)==0: return None
	
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	
	next=sorted(next, key=lambda x: -(x[0]+x[1]))
	
	for nrc in next:
		if nrc in usedRC0: continue
		usedRC0.add(nrc)
		p=(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize)
		nextParams.append(p)


def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
			
# 	print(colors.astype(np.int32))
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
	nextParams.append(p)
	
	usedRC0=set()
	while len(nextParams)>0:
		param=nextParams.popleft()
		travel(*param, nextParams=nextParams, usedRC0=usedRC0)


if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)


Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Buggy python submission (verdict: Time Limit Exceeded):

#####

import numpy as np
# from numpy import int32, int8
from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize, nextParams: deque, usedRC0: set):
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
		if not visited[hi-row0].any(): break
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
# 		return flipSize
		print(flipSize)
		sys.exit(0)
					
# 	print("next",next)
	if len(next)==0: return None
	
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	
	next=sorted(next, key=lambda x: -(x[0]+x[1]))
	
	for nrc in next:
		if nrc in usedRC0: continue
		usedRC0.add(nrc)
		p=(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize)
		nextParams.append(p)


def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
# 	print(colors.astype(np.int32))
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
	nextParams.append(p)
	
	usedRC0=set()
	while len(nextParams)>0:
		param=nextParams.popleft()
		travel(*param, nextParams=nextParams, usedRC0=usedRC0)
# 	print("flipSize",flipSize)
# 	print(flipSize)


if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)


Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Buggy python submission (verdict: Time Limit Exceeded):

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def travel(colors, h, w, row0, col0, targetColor, flipSize, usedRC0, minFlipSize):
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
		if not visited[hi-row0].any(): break
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
		return flipSize
					
# 	print(next)
	if len(next)==0: return None
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	
	for nrc in next:
		if nrc in usedRC0: continue
		usedRC0.add(nrc)
# 		print("mi", minFlipSize, "ne", nextFlipSize)
		
		if minFlipSize is not None and nextFlipSize>=minFlipSize: continue
		fs=travel(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize, usedRC0, minFlipSize)
		if fs is None: continue
		if minFlipSize is None or fs<minFlipSize: minFlipSize=fs
	return min(minFlipSize, minFlipSize)
				

def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
# 	print(colors.astype(np.uint8))

	usedRC0=set()
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	flipSize=travel(colors, h, w, 0, 0, colors[0,0], nextFlipSize, usedRC0, None)
# 	print("flipSize",flipSize)
	print(flipSize)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)


Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Buggy python submission (verdict: Time Limit Exceeded):


#####

import numpy as np
# from numpy import int32, int8
from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize, nextParams: deque, usedRC0: set):
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
		if not visited[hi-row0].any(): break
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
# 		return flipSize
		print(flipSize)
		sys.exit(0)
					
# 	print("next",next)
	if len(next)==0: return None
	minFlipSize=None
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	for nrc in next:
		if nrc in usedRC0: continue
		usedRC0.add(nrc)
		p=(colors, h, w, nrc[0], nrc[1], not targetColor, nextFlipSize)
		nextParams.append(p)


def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
# 	print(colors.astype(np.int32))
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
	nextParams.append(p)
	
	usedRC0=set()
	while len(nextParams)>0:
		param=nextParams.popleft()
		travel(*param, nextParams=nextParams, usedRC0=usedRC0)
# 	print("flipSize",flipSize)
# 	print(flipSize)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)


Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Buggy python submission (verdict: Time Limit Exceeded):

#####

import numpy as np
# from numpy import int32, int8
from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize, nextParams: deque):
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h-row0, w-col0), np.bool)
	visited[0,0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1-row0,wi-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi-row0,wi-1-col0]:
				if c:
					visited[hi-row0,wi-col0]=True
				else:
					next.add((hi,wi))
	
	if visited[h-1-row0,w-1-col0]:
# 		print("found")
# 		return flipSize
		print(flipSize)
		sys.exit(0)
					
# 	print(next)
	if len(next)==0: return None
	minFlipSize=None
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	for nr,nc in next:
		p=(colors, h, w, nr, nc, not targetColor, nextFlipSize)
		nextParams.append(p)


def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
# 	print(colors)
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	
	nextParams=deque()
	p=(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
	nextParams.append(p)
	
	while len(nextParams)>0:
		param=nextParams.popleft()
		travel(*param, nextParams=nextParams)
# 	print("flipSize",flipSize)
# 	print(flipSize)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)


Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Buggy python submission (verdict: Time Limit Exceeded):

#####

import numpy as np
# from numpy import int32, int8
# from collections import defaultdict

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def travel(colors, h, w, row0, col0, targetColor, flipSize):
	
# 	print()
# 	print("row0",row0,"col0",col0,"flipSize",flipSize)
	
	visited=np.zeros((h, w), np.bool)
	visited[row0,col0]=True
	next=set()
	for hi in range(row0, h):
		for wi in range(col0, w):
			c=colors[hi,wi]==targetColor
			if hi>0 and visited[hi-1,wi]:
				if c:
					visited[hi,wi]=True
				else:
					next.add((hi,wi))
			if wi>0 and visited[hi,wi-1]:
				if c:
					visited[hi,wi]=True
				else:
					next.add((hi,wi))
	
	if visited[h-1,w-1]:
# 		print("found")
		return flipSize
					
# 	print(next)
	if len(next)==0: return None
	minFlipSize=None
	if targetColor: nextFlipSize=flipSize+1
	else: nextFlipSize=flipSize
	for nr,nc in next:
		fs=travel(colors, h, w, nr, nc, not targetColor, nextFlipSize)
		if fs is None: continue
		if minFlipSize is None or fs<minFlipSize: minFlipSize=fs
	return minFlipSize
				

def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."
# 	print(colors)
	
	if colors[0,0]: nextFlipSize=0
	else: nextFlipSize=1
	flipSize=travel(colors, h, w, 0, 0, colors[0,0], nextFlipSize)
# 	print("flipSize",flipSize)
	print(flipSize)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)



Fixed submission:

#####

import numpy as np
# from numpy import int32, int8
# from collections import deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	h,w=getIntList(inputs[0])
	colors=np.empty((h,w),np.bool)
	for hi in range(h):
		for wi in range(w):
			colors[hi,wi]=inputs[1+hi][0][wi]=="."

# 	h=20
# 	w=20
# 	np.random.seed(0)
# 	colors=np.random.randint(0,2,(h,w))

# 	from matplotlib import pyplot as plt
# 	for hi in range(h):
# 		for wi in range(w):
# 			plt.annotate(str((hi,wi)), (wi-0.5,hi), color="g")
# 	plt.imshow(colors)
# 	plt.show()
			
# 	print(colors.astype(np.int32))
	
	flipSize=np.empty((h,w), np.int32)
	
	if colors[0,0]: flipSize[0,0]=0
	else: flipSize[0,0]=1
	
	for hi in range(h):
		for wi in range(w):
			if hi==0 and wi==0: continue
			c=colors[hi,wi]
			fs=[]
			if hi>0:
				d=int(colors[hi-1,wi] and (not c))
				s=flipSize[hi-1, wi]+d
				fs.append(s)
				
			if wi>0:
				d=int(colors[hi,wi-1] and (not c))
				s=flipSize[hi, wi-1]+d
				fs.append(s)
			
			fs=min(fs)
			flipSize[hi,wi]=fs
	
	print(flipSize[h-1,w-1])
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)