# Untitled

unknown
plain_text
a month ago
3.1 kB
0
Indexable
Never
```/*Painting

The design team at SAMSUNG Electronics considers an innovative design for a new product.

The left figure is the basic diagram and the design team tries to distinguish each area marked by letter of the alphabet with four colors.

When proceeding with this, the design team pursues perfection by researching the combinations of all colors and chooses one of them.

However, they have trouble because they do not know the total number of cases of the color combinations.

Due to this difficulty, you convert the basic diagram on the left to the graph in the center and then you solve the problem by converting it to the adjacency matrix on the right.

The number of cases is 264.

What is the method used to solve this?  (Time Limit : 2 seconds)

﻿

﻿

[Input]

On the first line, the number of the test cases (1<=T <= 10) is given.

On the first line of each test case, the size of the matrix n (1<=n <= 30, n is the positive number).

From the second line, the values of matrix are entered by being distinguished as one blank or other.

[Output]

For each test case, you should print "Case #T" in the first line where T means the case number.
In the second line, print out the total number of cases to paint and distinguish them with four colors for each area.

[Sample Input ]

3

4

0 0 0 1

0 0 0 1

0 0 0 1

1 1 1 0

5

0 1 1 1 0

1 0 0 1 1

1 0 0 1 0

1 1 1 0 1

0 1 0 1 0

7

0 1 0 0 1 0 1

1 0 1 0 1 0 0

0 1 0 1 1 0 0

0 0 1 0 1 1 0

1 1 1 1 0 1 1

0 0 0 1 1 0 1

1 0 0 0 1 1 0

[Sample Output]

Case #1
108

Case #2
96

Case #3
264*/
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Scanner;

public class Painting {
static{
try {
System.setIn(new FileInputStream("src/inp.txt"));
//			System.setOut(new PrintStream("src/out.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
static Scanner scanner=new Scanner(System.in);
static int res;
/*phan biet cac khu vuc danh dau bang chu cai bang 4 mau
* chon to hop cac mau*/

static boolean check(int[][] a,int[] color,int n,int u){
for(int v=0;v<n;++v)
if(a[u][v]==1 && color[u]==color[v])
return false;
return true;
}

static void bt(int[][] a,int[] color,int n,int u){
if(u==n){
++res;
return;
}

for(int co=1;co<=4;++co){
color[u]=co;
if(check(a,color,n,u))
bt(a,color,n,u+1);
color[u]=0;
}
}

static void exec(int test){
int n=Integer.parseInt(scanner.next());
int[][] a=new int[n][n];
for(int i=0;i<n;++i) for(int j=0;j<n;++j) a[i][j]=Integer.parseInt(scanner.next());

res=0;

bt(a,new int[n],n,0);

System.out.printf("Case #%d\n%d\n",test,res);
}

public static void main(String[] args) {
int t=Integer.parseInt(scanner.next());

for(int test=1;test<=t;++test)
exec(test);

scanner.close();
}
}
```