# Untitled

unknown

plain_text

10 days ago

3.0 kB

5

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] The adjacency matrix about a basic diagram is entered. 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.util.Scanner; /* As the name of the class should be Solution, using Solution.java as the filename is recommended. In any case, you can execute your program by running 'java Solution' command. */ class Solution { 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(); } }

Leave a Comment