arrow_forward
همه ارسالها
جزئیات ارسال کد#961
برای پسندیدن وارد شوید
khashayar moeinfar
(۵ ماه پیش)
1import java.util.*;
2
3public class Main {
4
5 // between[a][b] = midpoint node between a and b (1-indexed), or 0 if none
6 private static final int[][] BETWEEN = new int[10][10];
7
8 static {
9 int[] row = {0, 0,0,0, 1,1,1, 2,2,2};
10 int[] col = {0, 0,1,2, 0,1,2, 0,1,2};
11
12 for (int a = 1; a <= 9; a++) {
13 for (int b = 1; b <= 9; b++) {
14 if (a == b) continue;
15 int dr = row[b] - row[a];
16 int dc = col[b] - col[a];
17 // midpoint exists only when both deltas are even
18 if (dr % 2 == 0 && dc % 2 == 0) {
19 int mr = row[a] + dr / 2;
20 int mc = col[a] + dc / 2;
21 // find which node is at (mr, mc)
22 for (int n = 1; n <= 9; n++) {
23 if (row[n] == mr && col[n] == mc) {
24 BETWEEN[a][b] = n;
25 break;
26 }
27 }
28 }
29 }
30 }
31 }
32
33 private static int count;
34 private static boolean[] required;
35
36 public static int countPatterns(int[] requiredNodes) {
37 required = new boolean[10];
38 for (int n : requiredNodes) required[n] = true;
39
40 count = 0;
41 boolean[] visited = new boolean[10];
42
43 for (int start = 1; start <= 9; start++) {
44 visited[start] = true;
45 backtrack(start, visited, 1);
46 visited[start] = false;
47 }
48
49 return count;
50 }
51
52 private static void backtrack(int last, boolean[] visited, int visitedCount) {
53 // check if all required nodes are visited
54 boolean allRequired = true;
55 for (int n = 1; n <= 9; n++) {
56 if (required[n] && !visited[n]) {
57 allRequired = false;
58 break;
59 }
60 }
61 if (allRequired) count++;
62
63 for (int nxt = 1; nxt <= 9; nxt++) {
64 if (visited[nxt]) continue;
65 int mid = BETWEEN[last][nxt];
66 // if there's a midpoint node that hasn't been visited, move is blocked
67 if (mid != 0 && !visited[mid]) continue;
68
69 visited[nxt] = true;
70 backtrack(nxt, visited, visitedCount + 1);
71 visited[nxt] = false;
72 }
73 }
74
75 public static void main(String[] args) {
76 Scanner sc = new Scanner(System.in);
77 int T = sc.nextInt();
78 StringBuilder sb = new StringBuilder();
79
80 while (T-- > 0) {
81 int k = sc.nextInt();
82 int[] required = new int[k];
83 for (int i = 0; i < k; i++) required[i] = sc.nextInt();
84 sb.append(countPatterns(required)).append('\n');
85 }
86
87 System.out.print(sb);
88 }
89}
کد ارسالشده برای داوری خودکار هاتکدز
UTF-8