Patrix

All submissions for this problem are available.
Patrix  Number of Patterns possible for a given matrix.
Chef got a supercool smartphone recently. It has an option for Pattern lock. Now Chef wants to find the number of patterns possible connecting P points in a given Matrix of M rows and N columns.
Assume that any number of dots can be connected to arrive at a valid pattern i.e. even a single dot combination is perfectly valid.
Input
The first line takes T, the number of test cases. Each of the test case takes 3 space separated numbers, first one takes M (number of rows), second one takes N (number of columns) and then the third one takes P, the number of dots need to be connected to a get a pattern.
Output
Your program has to print Patrix for every test case in T lines.
Constraints
While connecting two dots A and B, it is not possible to skip a nonconnected dot C, if A,B,C are colinear and C lies between A and B.
 0 < T ≤ 101
 0 < M , N ≤ 101
 0 < P ≤ MxN
Note: It might not be possible to cover all the values in the pool of permitted numbers due to huge processing time. eg you might not be able to deliver the output for 100 x 100 dot matrix, while 100 x 1 would be possible. Hence, we advise you to optimise your code as much as possible to maximise the number of cases covered.
Example
Input: 2
3 1 2
2 2 2
Output: 4
12
Explanation
Test Case 1 : 3 rows, 1 column. The task is to print the number of twodot combinations possible in a 3 x 1 dotmatrix. Patrix for connecting two dots is 4.
The 1st dot can be connected to the 2nd dot
The 2nd dot can be connected to the 1st dot
The 2nd dot can be connected to 3rd dot and,
The 3rd dot can be connected to the 2nd dot.
Test Case 2 : 2 rows, 2 columns. Patrix for connecting 2 points is, take any one point, it can be connected with three other dots to form a two dot pattern. So for 4 dots 4x3=12.
Author:  c_cube_iist 
Tags  c_cube_iist 
Date Added:  2032015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 