0

Stamp Box

Difficulty: MEDIUM
Contributed By
Shrey Pansuria
Avg. time to solve
25 min
Success Rate
75%

Problem Statement

Ninja got a moody friend who is very curious about colors. His friend presented him with a design made of various colors and gave him a stamp box. The various colors are given in the form of numbers. He can adjust the dimensions of the stamp box as per need.

Ninja is supposed to draw the given design under the given conditions:

1. Ninja can use one color at a time.
2. Ninja can’t use one color more than once.
3. The stamp box is in the form of a rectangle. So, Ninja can only draw rectangles(or squares) by adjusting the dimensions of the stamp box.
4. Once Ninja prints any color using the stamp box, the old color won’t be visible and only the new color will be visible.

Ninja is very busy in doing some other stuff but he can find some time if it is possible to print the design under the given conditions and if it is impossible to print the design, he won’t waste time on it.

Can you help Ninja to find if it is possible to print the design or not?

Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line contains two space-separated integers ‘N’ and ‘M’, which denotes the number of rows and columns in the matrix ‘MAT’.

The next ‘N’ lines contain ‘M’ space-separated integers denoting the colors at that point.
Output Format:
For each test case, print 1 if it is possible to draw the given design. Otherwise, print 0.

Print the output of each test case in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
1 <= MAT[i][j] <= 50

Where 'MAT[i][j]' is the color in the coordinate (i, j).

Time Limit: 1 sec
Sample Input 1:
2
3 3
1 2 3
4 5 6
7 3 7
4 4
1 3 2 2
1 3 2 2
1 1 1 1
1 4 4 4
Sample Output 1:
0
1
Explanation For Sample Input 1:
In the first test case, there are 7 colors in a matrix of size 3X3 as shown in the figure.

alt text

To create the given design, we need to reuse one of the two colors - 3 or 7. Otherwise, it is not possible to make the given design under the given conditions. So, the output is 0.

In the second test case, there are 4 colors in a matrix of size 4X3 as shown in the figure. 

alt text

To create the given design, 
One of the options to make the given design is:
Make the stamp box of size 3X3 and print color 1 in all the boxes.
Make the stamp box of size 2X2 and then print color 2 in the top right corner.
Make the stamp box of size 2X1 and then print color 3 beside color 2.
Make the stamp box of size 1X3 and then print color 1 behind color 2.
Hence, it is possible to make this design. So, the output is 1.
Sample Input 2:
2
4 3
1 2 1
1 3 1
1 1 3
1 1 1
2 2
1 2
3 4
Sample Output 2:
0
1
Explanation For Sample Input 2:
In the first test case, it is possible to draw the given design. Thus, we will print 1 as output.
In the second test case, it is impossible to draw the design. So, we will print 0.
Reset Code
Full screen
copy-code
Console