golu-and-coins-1
Source: hackerearth
Difficulty: UNKNOWN_DIFFICULTY

Golu is given a task of clearing coins fallen down  on floor. Naughty being his modus operandi, he thought of playing a game while clearing coins. He arranges the coins like an M X N matrix with random heads (1) and tails (0).

In every move, he chooses a sub-matrix of size L X B [such that max(L,B) >1] and interchanges all heads to tails and vice-versa present in the chosen sub-matrix. Then if he finds a 2X2 sub-matrix exclusively of heads anywhere in the M X N matrix, he removes those coins.

Your task is simple. You have to report the minimum no. of moves taken by him before he clears his first 2X2 sub-matrix.

Input:

Your first line of input consists of two numbers M, N. Each of the next M lines consists of N space-separated integers which are either 0 or 1.

Output:

Output a single line answer giving the minimum no. of steps taken before his first clearance. If it is impossible for him to do so, print "-1" (quotes for clarity).

Constraints :

2 ≤ M,N ≤ 10

Author : Srinivas

Testers : Shubham Parekh , Shreyans

(By IIT Kgp HackerEarth Programming Club)

SAMPLE INPUT
2 4
0 0 1 1
0 0 1 1

SAMPLE OUTPUT
0


M, N = [int(_) for _ in input().split()]
m = [[0] * N] * M
for i in range(M):
	m[i] = [int(_) for _ in input().split()]
ans = 2
corners = [(0, 0), (0, N-2), (M-2, 0), (M-2, N-2)]
if M == 2 and N == 2:
	s = m[0][0] + m[0][1] + m[1][0] + m[1][1]
	if s == 4:
		ans = 0
	elif s == 0:
		ans = 1
	elif s == 2:
		if m[0][0] != m[0][1] and m[0][0] != m[1][0]:
			ans = 2
		else:
			ans = 1
	else:
		ans = -1
else:
	for i in range(M-1):
		for j in range(N-1):
			tl = m[i][j]
			tr = m[i][j+1]
			bl = m[i+1][j]
			br = m[i+1][j+1]
			s = tl + tr + bl + br
			if (i,j) in corners:
				if s == 4:
					ans = 0
				elif s == 0:
					ans = min(ans, 1)
				elif s == 2:
					if tl != tr and tl != bl:
						ans = min(ans, 2)
					else:
						ans = min(ans, 1)
				elif s == 1:
					if i == 0 and j == 0 and tl == 1:
						ans = min(ans, 2)
					elif i == 0 and j == N-2 and tr == 1:
						ans = min(ans, 2)
					elif i == M-2 and j == 0 and bl == 1:
						ans = min(ans, 2)
					elif i == M-2 and j == N-2 and br == 1:
						ans = min(ans, 2)
					else:
						ans = min(ans, 2)
				elif s == 3:
					if i == 0 and j == 0 and tl == 0:
						ans = min(ans, 2)
					elif i == 0 and j == N-2 and tr == 0:
						ans = min(ans, 2)
					elif i == M-2 and j == 0 and bl == 0:
						ans = min(ans, 2)
					elif i == M-2 and j == N-2 and br == 0:
						ans = min(ans, 2)
					else:
						ans = min(ans, 1)
			else:
				if s == 4:
					ans = 0
				elif s == 1:
					ans = min(ans, 2)
				elif s == 0 or s == 3:
					ans = min(ans, 1)
				else:
					if tl != tr and tl != bl:
						ans = min(ans, 2)
					else:
						ans = min(ans, 1)
print(ans)


M,N=list(map(int,input().split()))
L=[]
for i in range(M):
	L.append(list(map(int,input().split())))

if M+N==4 and (L==[[0,1],[1,1]] or L==[[1,0],[1,1]] or L==[[1,1],[1,0]] or L==[[1,1],[0,1]]) or L==[[1,0],[0,0]] or L==[[0,1],[0,0]] or L==[[0,0],[1,0]] or L==[[0,0],[0,1]]:
		print("-1")
else:
	List=[]
	for i in range(M-1):
		for j in range(N-1):
			List.append(([L[i][j],L[i][j+1],L[i+1][j],L[i+1][j+1]],[j!=0,j+2!=N,i!=0,i+2!=M]))   #L,R,T,B
	zero=False
	one=False
	for i in List:
		if i[0]==[1,1,1,1]:
			zero=True
			print("0")
			break
		elif i[0]==[0,0,0,0] or i[0]==[1,0,1,0] or i[0]==[1,1,0,0] or i[0]==[0,1,0,1] or i[0]==[0,0,1,1] or (i[0]==[0,1,1,1] and (i[1][0] or i[1][2])) or (i[0]==[1,0,1,1] and (i[1][1] or i[1][2])) or (i[0]==[1,1,0,1] and (i[1][0] or i[1][3])) or (i[0]==[1,1,1,0] and (i[1][1] or i[1][3])):
			one=True
	if (not zero):
		if (one):
			print("1")
		else:
			print("2")
			
		


'''f=open('input.txt')
g=open('output.txt', 'w')
nooftest=int(f.readline().strip())'''
#import cmath
import math
#import time
m,n=list(map(int,input().split()))
array=[]
for i in range(m):
	array.append(list(map(int,input().split())))
def check(a1,a2,a3,a4):
	if a1==a2==a3==a4==1:
		return 0
	elif a1==a2==a3==a4==0:
		return 1
	elif (a1==a2==0 and a3==a4==1) or (a2==a3==0 and a4==a1==1) or (a3==a4==0 and a1==a2==1) or (a4==a1==0 and a2==a3==1):
		#print a1,a2,a3,a4,"here"
		return 1
	elif (a1==a3==0 and a2==a4==1) or(a2==a4==0 and a1==a3==1):
		return 2
	elif (a1==a2==a3==0 and a4==1) or (a2==a3==a4==0 and a1==1) or (a3==a4==a1==0 and a2==1) or (a4==a1==a2==0 and a3==1):
		if i>0 or j>0:
			return 2
		else:
			return 4
	else:
		if j>0 and array[i][j-1]==array[i+1][j-1]:
			return 1
		elif j<n-2 and array[i][j+2]==array[i+1][j+2]:
			return 1
		elif i>0 and array[i-1][j]==array[i-1][j+1]:
			return 1
		elif i<m-2 and array[i+2][j]==array[i+2][j+1]:
			return 1
		elif i>0 or j>0:
			return 2
		else:
			return 4
ans=4
for i in range(m-1):
	for j in range(n-1):
		k=check(array[i][j],array[i][j+1],array[i+1][j+1],array[i+1][j])
		if k==2:
			if j>0 and array[i][j-1]==array[i+1][j-1]==1:
				k=1
			elif j<n-2 and array[i][j+2]==array[i+1][j+2]==1:
				k=1
			elif i>0 and array[i-1][j]==array[i-1][j+1]==1:
				k=1
			elif i<m-2 and array[i+2][j]==array[i+2][j+1]==1:
				k=1
		if k<ans:
			ans=k
if ans<4:
	print(ans)
else:
	print(-1)


import sys
M,N = str(input()).split()
M,N = [int(M), int(N)]
data = [[0]*N]*M
for m in range(M):
	data[m] = str(input()).split()
	data[m] = [int(data[m][n]) for n in range(N)]
if M == 2 and N == 2:
	c1 = data[0].count(1)
	c2 = data[1].count(1)
	if c1+c2 == 4:
		print("0")
	elif c1+c2 == 3 or c1+c2 == 1:
		print("-1")
	elif (data[0][0] == 1 and data[1][1] == 1) or (data[0][1] == 1 and data[1][0] == 1):
		print("2")
	else:
		print("1")
else:
	maskval = [[0]*(N-1)]*(M-1)
	p = 3
	for i in range(M-1):
		for j in range(N-1):
			maskval[i][j] = data[i][j] + data[i][j+1] + data[i+1][j] + data[i+1][j+1]
			if maskval[i][j] == 4:
				print("0")
				sys.exit()
			elif maskval[i][j] == 3:
				if ((data[i][j] == 0 and (i != 0 or j != 0)) or \
				(data[i][j+1] == 0 and (i != 0 or j+1 != N-1)) or \
				(data[i+1][j] == 0 and (i+1 != M-1 or j != 0)) or \
				(data[i+1][j+1] == 0 and (i+1 != M-1 or j+1 != N-1))):
					p = min(1,p)
				else:
					p = min(2,p)
			elif maskval[i][j] == 2:
				if (data[i][j] == 1 and data[i+1][j+1] == 1) or (data[i][j+1] == 1 and data[i+1][j] == 1):
					p = min(2,p)
				else:
					p = min(1,p)
			elif maskval[i][j] == 0:
				p = min(1,p)
			else:
				p = min(2,p)
	print(p)