Dave recently mastered the problem of placing N queens on a chessboard so
that no two queens attack eachother.
Now he wants to see how many knights he can place on a chessboard so
that no two knights attack eachother.
Normally this would be a simple task, but some of the squares of the
chessboard have been marked as unusable and hence cannot have a knight placed
on them.
Recall that a knight can attack another knight if their vertical distance
is 2 and their horizontal distance is 1, or if their vertical distance is 1 and
their horizontal distance is 2.  Only one knight may be placed on each square
of the chessboard

------ Input ------ 

The first line of input contains an integer T (0
Each test case will begin with a line containing 2 integers M and N (0

------ Output ------ 

For each test case, output on a single line the maximum number of knights that may be placed
on the chessboard such that no two attack each other.

----- Sample Input 1 ------ 
2
2 4
....
....
5 5
..#..
#..#.
##...
...##
.....
----- Sample Output 1 ------ 
4
11
----- explanation 1 ------ 
The following image represents the chessboard and a possible solution to the second test case:

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Data structures

Flows and cuts


Solutions:
import random
dy = [-2, -1, 1, 2, -2, -1, 1, 2]
dx = [-1, -2, -2, -1, 1, 2, 2, 1]

class Ponies:
	mat = []
	G = []
	match = []
	used = []

	def dfs(self, v):
		global used
		used.add(v)
		for i in range(len(G[v])):
			u = G[v][i]
			w = match[u]
			if w < 0 or (w not in used and self.dfs(w)):
				match[v] = u
				match[u] = v
				return 1
		return 0

	def bipartiteMatching(self, V):
		global used
		global match
		res = 0
		match = [-1] * 1500
		for v in range(V):
			if match[v] < 0:
				used = set([])
				if self.dfs(v):
					res += 1
		return res

	def maxIndependentSet(self, h, w, V):
		global G
		G = [[] for _ in range(1500)]
		for i in range(h):
			for j in range(w):
				if mat[i][j] == -1:
					continue
				curr = mat[i][j]
				for k in range(8):
					y = i + dy[k]
					x = j + dx[k]
					if y < 0 or y >= h or x < 0 or (x >= w) or (mat[y][x] == -1):
						continue
					G[curr] += [mat[y][x]]
		maximalIndependentSet = V - self.bipartiteMatching(V)
		return maximalIndependentSet

	def solve(self, chessboard):
		global mat
		V = 0
		mat = [[0 for _ in range(50)] for _ in range(50)]
		h = len(chessboard)
		w = len(chessboard[0])
		for i in range(h):
			for j in range(w):
				if chessboard[i][j] == '.':
					V += 1
					mat[i][j] = V
				else:
					mat[i][j] = -1
		return self.maxIndependentSet(h, w, V)
solver = Ponies()
T = int(input())
while T:
	T -= 1
	(h, w) = [int(entry) for entry in input().split(' ')]
	input_mat = []
	for _ in range(h):
		row = input()
		input_mat += [row]
	print(solver.solve(input_mat))