Given a matrix of size n*m. Every cell of matrix contains either 'A' or 'B'. Exchange is defined as swaping the characters between two cells. Your task is to find the minimum number of exchange needed to rearrange the given matrix such that no adjacent cell contains the same characters.
Two cells are adjacent if they share one of their common sides (left,right,front or back if exists). 
Note: There will not be any case that answer does not exist.
 
Example 1:
Input: matrix = {{A,A,B,A},{B,A,B,A},{B,B,A,B}}
Output: 2
Explanation: Minimum number of students whose 
sets got changed are 4 (indexes: ((0,1),(0,2),
(0,3),(2,0))). The final alloted sets are:
A B A B
B A B A
A B A B
Here 2 exchange are done so answer is 2.
Example 2:
Input: matrix = {{A,B},{B,A}}
Output: 0
Explanation: No two adjacent cell contains same
character.
 
Your Task:
You don' t need to read or print anything. Your task is to complete the function MinimumExchange() which takes matrix as input parameter and returns minimum number of  exchange needed.
 
Expected Time Complexity: O(n*m)
Expected Space Compelxity: O(1)
 
Constraints:
1 <= n, m <= 100

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3



class Solution:

	def MinimumExchange(self, matrix):

		# Code here

Solutions:
class Solution:

	def MinimumExchange(self, matrix):
		ans = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0 and matrix[i][j] == 'B':
					ans += 1
				elif (i + j) % 2 == 1 and matrix[i][j] == 'A':
					ans += 1
		ans2 = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 1 and matrix[i][j] == 'B':
					ans2 += 1
				elif (i + j) % 2 == 0 and matrix[i][j] == 'A':
					ans2 += 1
		if ans == 0 or ans2 == 0:
			return 0
		if ans == 1 and ans2 >= 1 or (ans >= 1 and ans2 == 1):
			return 1
		if ans % 2 == 0 and ans2 % 2 == 0:
			return min(ans // 2, ans2 // 2)
		elif ans % 2 == 0 and ans2 % 2 != 0:
			return min(ans // 2, ans2)
		else:
			return min(ans, ans2 // 2)


class Solution:

	def MinimumExchange(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		(count1, count2) = (0, 0)
		for i in range(0, m):
			for j in range(0, n):
				if matrix[i][j] == 'A':
					if (i + j) % 2 == 0:
						count1 += 1
					else:
						count2 += 1
				elif (i + j) % 2 == 0:
					count2 += 1
				else:
					count1 += 1
		ans = min(count1, count2)
		if ans % 2 == 0:
			return ans // 2
		return min(ans, (m * n - ans) // 2)


class Solution:

	def MinimumExchange(self, matrix):
		(n, m, a) = (len(matrix), len(matrix[0]), 0)
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0 and matrix[i][j] != 'A':
					a += 1
				if (i + j) % 2 == 1 and matrix[i][j] != 'B':
					a += 1
		b = n * m - a
		if a & 1:
			return b // 2
		if b & 1:
			return a // 2
		return min(a // 2, b // 2)


class Solution:

	def MinimumExchange(self, matrix):
		(count1, count2, a, b) = (0, 0, 0, 0)
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] != 'A':
						count1 += 1
						b += 1
					else:
						count2 += 1
						a += 1
				elif matrix[i][j] != 'B':
					count1 += 1
					a += 1
				else:
					count2 += 1
					b += 1
		count1 //= 2
		count2 //= 2
		if a == b:
			answer = min(count1, count2)
		elif a > b:
			answer = count1
		else:
			answer = count2
		return answer


class Solution:

	def MinimumExchange(self, matrix):
		a = 0
		b = 0
		ch = ('A', 'B')
		for (y, row) in enumerate(matrix):
			for (x, letter) in enumerate(row):
				a += 0 if ch[(x + y) % 2] == letter else 1
				b += 0 if ch[(x + y + 1) % 2] == letter else 1
		if a % 2 == 1:
			return b // 2
		if b % 2 == 1:
			return a // 2
		return min(a // 2, b // 2)


class Solution:

	def MinimumExchange(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		seq1 = 0
		for i in range(rows):
			for j in range(cols):
				if (i + j) % 2 == 0 and matrix[i][j] == 'B':
					seq1 += 1
				elif (i + j) % 2 != 0 and matrix[i][j] == 'A':
					seq1 += 1
		seq2 = 0
		for i in range(rows):
			for j in range(cols):
				if (i + j) % 2 == 0 and matrix[i][j] == 'A':
					seq2 += 1
				elif (i + j) % 2 != 0 and matrix[i][j] == 'B':
					seq2 += 1
		ans = min(seq1, seq2)
		if ans % 2 == 0:
			return ans // 2
		return min(ans, (rows * cols - ans) // 2)


class Solution:

	def MinimumExchange(self, matrix):
		cnt = 0
		cnt1 = 0
		x = 'A'
		y = 'B'
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				if matrix[i][j] != x:
					cnt += 1
				if matrix[i][j] != y:
					cnt1 += 1
				(y, x) = (x, y)
			if j % 2 != 0:
				(x, y) = (y, x)
		if min(cnt, cnt1) % 2 == 0:
			return min(cnt, cnt1) // 2
		else:
			return max(cnt, cnt1) // 2


class Solution:

	def MinimumExchange(self, ma):
		import math
		x = 'A'
		y = 'B'
		count = 0
		count1 = 0
		for i in range(n):
			for j in range(m):
				if ma[i][j] != x:
					count += 1
				if ma[i][j] != y:
					count1 += 1
				(x, y) = (y, x)
			if j % 2 != 0:
				(x, y) = (y, x)
		if min(count, count1) % 2 == 0:
			return min(count, count1) // 2
		else:
			return max(count, count1) // 2


class Solution:

	def MinimumExchange(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		cA = 0
		cB = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] == 'B':
						cA += 1
				elif matrix[i][j] == 'A':
					cA += 1
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] == 'A':
						cB += 1
				elif matrix[i][j] == 'B':
					cB += 1
		ans = min(cA, cB)
		if ans % 2 == 0:
			return ans // 2
		else:
			return min(ans, (m * n - ans) // 2)


class Solution:

	def MinimumExchange(self, matrix):
		(N, M) = (len(matrix), len(matrix[0]))
		missA = missB = 0
		for i in range(N):
			for j in range(M):
				if not i + j & 1 and matrix[i][j] == 'B':
					missA += 1
				elif i + j & 1 and matrix[i][j] == 'A':
					missA += 1
		for i in range(N):
			for j in range(M):
				if not i + j & 1 and matrix[i][j] == 'A':
					missB += 1
				elif i + j & 1 and matrix[i][j] == 'B':
					missB += 1
		if missA & 1:
			return missB >> 1
		if missB & 1:
			return missA >> 1
		return min(missA, missB) >> 1


class Solution:

	def MinimumExchange(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		seq = [0] * rows
		seq1_data = ['AB', 'BA', 1, 0]
		seq2_data = ['BA', 'AB', 2, 0]
		seq_list = [seq1_data, seq2_data]
		for s in seq_list:
			for i in range(rows):
				for j in range(cols):
					exp = s[i % 2][j % 2]
					if matrix[i][j] != exp:
						s[3] += 1
		if seq1_data[3] % 2:
			mv = seq2_data[3]
		elif seq2_data[3] % 2:
			mv = seq1_data[3]
		else:
			mv = min(seq1_data[3], seq2_data[3])
		return mv // 2


class Solution:

	def MinimumExchange(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		c1 = c2 = 0
		for i in range(m):
			for j in range(n):
				if (i + j) % 2 == 0:
					if matrix[i][j] != 'A':
						c1 += 1
					else:
						c2 += 1
				elif matrix[i][j] == 'A':
					c1 += 1
				else:
					c2 += 1
		c = min(c1, c2)
		if c % 2 == 0:
			return c // 2
		return (n * m - c) // 2


import math

class Solution:

	def MinimumExchange(self, matrix):
		(seq1, seq2) = (0, 0)
		m = len(matrix)
		n = len(matrix[0])
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'A':
					if (i + j) % 2 == 1:
						seq1 += 1
					else:
						seq2 += 1
				elif (i + j) % 2 == 1:
					seq2 += 1
				else:
					seq1 += 1
		if m * n % 2 == 1:
			return seq1 // 2
		return min(seq1, seq2) // 2


class Solution:

	def MinimumExchange(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		countA = 0
		countB = 0
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] != 'A':
						countA += 1
				elif matrix[i][j] != 'B':
					countA += 1
		for i in range(n):
			for j in range(m):
				if (i + j) % 2 == 0:
					if matrix[i][j] != 'B':
						countB += 1
				elif matrix[i][j] != 'A':
					countB += 1
		ans = min(countA, countB)
		if ans % 2 == 0:
			return ans // 2
		return min(ans, (n * m - ans) // 2)


class Solution:

	def MinimumExchange(self, matrix):
		p1 = 0
		p2 = 0
		a = 0
		b = 0
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'A':
					a += 1
				if matrix[i][j] == 'B':
					b += 1
				if i % 2 == 0 and j % 2 == 0 and (matrix[i][j] == 'B'):
					p1 += 1
				if i % 2 == 0 and j % 2 != 0 and (matrix[i][j] == 'A'):
					p1 += 1
				if i % 2 != 0 and j % 2 == 0 and (matrix[i][j] == 'A'):
					p1 += 1
				if i % 2 != 0 and j % 2 != 0 and (matrix[i][j] == 'B'):
					p1 += 1
				if i % 2 == 0 and j % 2 == 0 and (matrix[i][j] == 'A'):
					p2 += 1
				if i % 2 == 0 and j % 2 != 0 and (matrix[i][j] == 'B'):
					p2 += 1
				if i % 2 != 0 and j % 2 == 0 and (matrix[i][j] == 'B'):
					p2 += 1
				if i % 2 != 0 and j % 2 != 0 and (matrix[i][j] == 'A'):
					p2 += 1
		if a != b:
			if a > b:
				return p1 // 2
			else:
				return p2 // 2
		if p1 == 0 or p2 == 0:
			return 0
		if p1 // 2 == 0 or p2 // 2 == 0:
			return max(p1 // 2, p2 // 2)
		return min(p1 // 2, p2 // 2)


class Solution:

	def MinimumExchange(self, matrix):
		count = 0
		start = matrix[0][0]
		prev = 'A' if start == 'B' else 'B'
		countA = 0
		countB = 0
		N = len(matrix) * len(matrix[0])
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'A':
					countA += 1
				else:
					countB += 1
				if j % 2 == 0 and prev == matrix[i][j]:
					count += 1
				elif j % 2 == 1 and start == matrix[i][j]:
					count += 1
			(start, prev) = (prev, start)
		count = count // 2
		if N % 2 == 1 and (matrix[0][0] == 'A' and countA > countB or (matrix[0][0] == 'B' and countB > countA)):
			return count
		count1 = 0
		start = matrix[0][0]
		prev = 'A' if start == 'B' else 'B'
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if j % 2 == 0 and start == matrix[i][j]:
					count1 += 1
				elif j % 2 == 1 and prev == matrix[i][j]:
					count1 += 1
			(start, prev) = (prev, start)
		count1 = count1 // 2
		if N % 2 == 1 and (matrix[0][0] == 'A' and countA < countB or (matrix[0][0] == 'B' and countB < countA)):
			return count1
		return min(count1, count)


class Solution:

	def MinimumExchange(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		(num1, num2) = (0, 0)
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 'A':
					if (i + j) % 2 == 0:
						num1 += 1
					else:
						num2 += 1
				elif (i + j) % 2 == 0:
					num2 += 1
				else:
					num1 += 1
		mini = min(num1, num2)
		if mini % 2 == 0:
			return mini // 2
		return min(mini, (m * n - mini) // 2)


class Solution:

	def MinimumExchange(self, m):
		r = len(m)
		c = len(m[0])
		co = 0
		c1 = 0
		c2 = 0
		c3 = 0
		c4 = 0
		for i in range(r):
			c3 += m[i].count('A')
			c4 += m[i].count('B')
			for j in range(c):
				x = i + j
				if x % 2 == 0 and m[i][j] != 'A':
					c1 += 1
				if x % 2 == 0 and m[i][j] != 'B':
					c2 += 1
		if c3 == c4:
			return min(c1, c2)
		elif c3 > c4:
			return c1
		else:
			return c2


class Solution:

	def MinimumExchange(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		valid1 = []
		valid2 = []
		zero = 0
		one = 0
		odd = 0
		flag = 0
		row_start = 1
		for i in range(n):
			row_start = 1 - row_start
			flag = row_start
			row1 = []
			row2 = []
			for j in range(m):
				row1.append(flag)
				row2.append(1 - flag)
				if matrix[i][j] == 'A':
					matrix[i][j] = 1
				else:
					matrix[i][j] = 0
				flag = 1 - flag
			valid1.append(row1)
			valid2.append(row2)
		row_start = True
		if n * m % 2:
			one = n * m
			odd = True
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == valid1[i][j]:
					zero += 1
				if matrix[i][j] == valid2[i][j] and (not odd):
					one += 1
		return min(zero // 2, one // 2)


class Solution:

	def MinimumExchange(self, matrix):
		count1 = count2 = count_a = count_b = 0
		for i in range(len(matrix)):
			if i % 2 == 0:
				char = 'A'
			else:
				char = 'B'
			for j in range(len(matrix[0])):
				if matrix[i][j] != char:
					count1 += 1
				if char == 'A':
					char = 'B'
				else:
					char = 'A'
				if matrix[i][j] == 'A':
					count_a += 1
				else:
					count_b += 1
		for i in range(len(matrix)):
			if i % 2 == 1:
				char = 'A'
			else:
				char = 'B'
			for j in range(len(matrix[0])):
				if matrix[i][j] != char:
					count2 += 1
				if char == 'A':
					char = 'B'
				else:
					char = 'A'
		if count_a == count_b:
			return min(count1, count2) // 2
		if count_a > count_b:
			return count1 // 2
		return count2 // 2


class Solution:

	def MinimumExchange(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		ans1 = 0
		ans2 = 0

		def g1(i, j):
			if i & 1 == 0:
				if j & 1 == 0:
					return 'A'
				else:
					return 'B'
			if j & 1 == 0:
				return 'B'
			return 'A'

		def g2(i, j):
			if i & 1 == 0:
				if j & 1 == 0:
					return 'B'
				else:
					return 'A'
			if j & 1 == 0:
				return 'A'
			return 'B'
		for i in range(n):
			for j in range(m):
				if g1(i, j) == matrix[i][j]:
					ans1 += 1
				if g2(i, j) == matrix[i][j]:
					ans2 += 1
		if ans1 & 1 == 0:
			ans1 //= 2
		if ans2 & 1 == 0:
			ans2 //= 2
		return min(ans1, ans2)


class Solution:

	def MinimumExchange(self, matrix):
		AnA = 0
		AnB = 0
		BnA = 0
		BnB = 0
		solA = 0
		solB = 0
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if (i + j) % 2 == 0:
					if matrix[i][j] == 'B':
						solA += 1
						AnB += 1
					else:
						solB += 1
						BnA += 1
				elif matrix[i][j] == 'A':
					solA += 1
					AnA += 1
				else:
					solB += 1
					BnB += 1
		solA = solA // 2
		solB = solB // 2
		if BnB == BnA and AnA == AnB:
			return min(solA, solB)
		elif BnB == BnA:
			return solB
		else:
			return solA


class Solution:

	def MinimumExchange(self, matrix):
		dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		res1 = 0
		res2 = 0
		ca = 0
		cb = 0
		mat1 = [[0] * len(matrix[0]) for i in range(len(matrix))]
		mat2 = [[0] * len(matrix[0]) for i in range(len(matrix))]
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 'A':
					ca = ca + 1
				else:
					cb = cb + 1
				if i % 2 == 0:
					if j % 2 == 0:
						mat1[i][j] = 'A'
						mat2[i][j] = 'B'
					else:
						mat1[i][j] = 'B'
						mat2[i][j] = 'A'
				elif j % 2 == 0:
					mat1[i][j] = 'B'
					mat2[i][j] = 'A'
				else:
					mat1[i][j] = 'A'
					mat2[i][j] = 'B'
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] != mat1[i][j]:
					res1 = res1 + 1
				if matrix[i][j] != mat2[i][j]:
					res2 = res2 + 1
		if ca == cb:
			res1 = res1 // 2
			res2 = res2 // 2
			return min(res1, res2)
		elif ca > cb:
			return res1 // 2
		else:
			return res2 // 2


class Solution:

	def MinimumExchange(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		a_a_wr = 0
		b_a_wr = 0
		a_count = 0
		for (i, sts) in enumerate(matrix):
			for (j, st) in enumerate(sts):
				loc = i + j
				if st == 'A':
					a_count += 1
				if loc % 2 == 0:
					if st == 'A':
						b_a_wr += 1
					else:
						a_a_wr += 1
		if a_count > int(n * m / 2):
			return a_a_wr
		elif a_count < int(n * m / 2):
			return b_a_wr
		else:
			return min([a_a_wr, b_a_wr])


class Solution:

	def MinimumExchange(self, mat):
		c1 = c2 = 0
		flag = True
		r = len(mat)
		c = len(mat[0])
		for i in range(r):
			cflag = flag
			for j in range(c):
				if cflag and mat[i][j] == 'B':
					c1 += 1
				elif not cflag and mat[i][j] == 'A':
					c1 += 1
				if cflag and mat[i][j] == 'A':
					c2 += 1
				elif not cflag and mat[i][j] == 'B':
					c2 += 1
				cflag = not cflag
			flag = not flag
		ans = min(c1, c2)
		if ans % 2 == 0:
			return ans // 2
		return min(ans, int((r * c - ans) / 2))


class Solution:

	def MinimumExchange(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		s1 = s2 = 0
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 'A':
					if (i + j) % 2 == 0:
						s1 += 1
					else:
						s2 += 1
				elif (i + j) % 2 == 0:
					s2 += 1
				else:
					s1 += 1
		r = min(s1, s2)
		return r // 2 if r % 2 == 0 else min(r, (m * n - r) // 2)


class Solution:

	def MinimumExchange(self, matrix):
		(c1, c2) = (0, 0)
		for r in range(len(matrix)):
			for c in range(len(matrix[0])):
				if (r + c) % 2 == 0 and matrix[r][c] == 'B' or ((r + c) % 2 != 0 and matrix[r][c] == 'A'):
					c1 += 1
		for r in range(len(matrix)):
			for c in range(len(matrix[0])):
				if (r + c) % 2 == 0 and matrix[r][c] == 'A' or ((r + c) % 2 != 0 and matrix[r][c] == 'B'):
					c2 += 1
		if c1 % 2 == 0 and c2 % 2 == 0:
			return min(c1, c2) // 2
		elif c1 % 2 != 0 and c2 % 2 != 0:
			return min(c1, c2)
		elif c1 % 2 == 0 and c2 % 2 != 0:
			return c1 // 2
		else:
			return c2 // 2


class Solution:

	def MinimumExchange(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		correct_mat = []
		correct_mat1 = []
		FC = [0, 0]
		SC = [0, 0]
		NC = [0, 0]
		for i in range(rows):
			t = []
			for j in range(cols):
				if (i + j) % 2:
					t.append('B')
					FC[1] += 1
				else:
					t.append('A')
					FC[0] += 1
			correct_mat.append(t)
		for i in range(rows):
			t = []
			for j in range(cols):
				if (i + j) % 2:
					t.append('A')
					SC[0] += 1
				else:
					t.append('B')
					SC[1] += 1
			correct_mat1.append(t)
		ans = 0
		for (i, j) in zip(correct_mat, matrix):
			for (x, y) in zip(i, j):
				if x != y:
					ans += 1
				if y == 'A':
					NC[0] += 1
				else:
					NC[1] += 1
		tans = 0
		for (i, j) in zip(correct_mat1, matrix):
			for (x, y) in zip(i, j):
				if x != y:
					tans += 1
		if NC[0] == SC[0] and SC[0] == FC[0] and (NC[1] == SC[1]) and (SC[1] == FC[1]):
			return min(ans // 2, tans // 2)
		elif NC[0] == SC[0] and NC[1] == SC[1]:
			return tans // 2
		else:
			return ans // 2


class Solution:

	def MinimumExchange(self, matrix):
		x = len(matrix)
		y = len(matrix[0])
		seq1 = 0
		seq2 = 0
		for i in range(x):
			for j in range(y):
				if matrix[i][j] == 'A':
					if (i + j) % 2 == 0:
						seq1 += 1
					else:
						seq2 += 1
				elif (i + j) % 2 == 0:
					seq2 += 1
				else:
					seq1 += 1
		ans = min(seq1, seq2)
		if ans % 2 == 0:
			return ans // 2
		return min(ans, (x * y - ans) // 2)


class Solution:

	def MinimumExchange(self, mat):
		n = len(mat)
		m = len(mat[0])
		seq1 = 0
		seq2 = 0
		cntA = 0
		cntB = 0
		for i in range(0, n):
			for j in range(0, m):
				if (i + j) % 2 == 0:
					if mat[i][j] == 'A':
						seq1 += 1
						cntA += 1
					else:
						seq2 += 1
						cntB += 1
				elif mat[i][j] == 'A':
					seq2 += 1
					cntA += 1
				else:
					seq1 += 1
					cntB += 1
		if n % 2 and m % 2:
			if cntA > cntB:
				return seq2 // 2
			else:
				return seq1 // 2
		ans = min(seq1, seq2)
		return (ans + 1) // 2


class Solution:

	def MinimumExchange(self, matrix):
		m1 = 0
		n = len(matrix[0])
		m2 = 0
		for i in range(len(matrix)):
			for j in range(n):
				if (i + j) % 2 == 0:
					if matrix[i][j] != 'A':
						m1 += 1
					else:
						m2 += 1
				if (i + j) % 2 != 0:
					if matrix[i][j] != 'B':
						m1 += 1
					else:
						m2 += 1
		if m1 % 2 != 0:
			m1 = m2
		if m2 % 2 != 0:
			m2 = m1
		k = m1 // 2
		if m1 > m2:
			k = m2 // 2
		return k