[Here][1] is my short and simple solution.
**Number of ways = (Number of ways of forming *i* non-empty groups of *k* columns) \* (Number of ways of placing this *i* groups around *n-k* columns) *for i=1,2,3..k***
Number of ways of forming *i* groups of *k* columns = (Number of ways of distributing *k* objects into *i* groups) * (2^i)
where in each group alternate bricks of row *1,2* are selected and each group can have two orientation (either first brick is from first row or second)
Thus, **Number of ways = sum( (k-1)C(i-1) * 2^i * ~~(n-k+1)C(i)**
~~(n-k+1)C(i) ) for i=1,2,..k**
Extended the logic of single row to two rows *:)* ...
Time Complexity = O( T . K^2 )
[1]: http://www.codechef.com/viewsolution/20580951