1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include <stdio.h>
int n;
int len;
int arr[16] = {0};
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};
int d;
void print_one_idx_arr(int arr[]){
for(int i = 0; i < len; i++) if(arr[i]) printf("%d ", i);
printf("\n");
}
int is_valid(int x, int y){
return x >= 0 && y >= 0 && x < n && y < n;
}
void press(int cnt[], int num){
int x = num / n, y = num % n;
for(int i = 0; i < 5; i++){
int now_x = x + dx[i], now_y = y + dy[i];
if(is_valid(now_x, now_y)){
cnt[now_x * n + now_y]++;
}
}
}
int check_valid_comb(int used[], int arr[]){
int cnt[16] = {0};
for(int i = 0; i < len; i++){
if(!used[i]) continue;
else press(cnt, i);
}
for(int i = 0; i < len; i++){
if(arr[i] == 0 && cnt[i] % 2 == 1){
return 0;
}
if(arr[i] == 1 && cnt[i] % 2 == 0){
return 0;
}
}
return 1;
}
int dfs(int used[], int now_idx, int now_size, int target_size){
if(now_size == target_size){
if(check_valid_comb(used, arr) == 1){
print_one_idx_arr(used);
return 1;
}
else{
return 0;
}
}
else if(now_idx == len){
return 0;
}
else{
int rtv;
used[now_idx] = 1;
rtv = dfs(used, now_idx + 1, now_size + 1, target_size);
if(rtv) return 1;
used[now_idx] = 0;
rtv = dfs(used, now_idx + 1, now_size, target_size);
if(rtv) return 1;
return 0;
}
}
int main(){
scanf("%d", &n);
while(scanf("%d", &d) != EOF) arr[d] = 1;
len = n * n;
int used[16] = {0};
for(int i = 0; i < len; i++){
int rtv = dfs(used, 0, 0, i + 1);
if(rtv == 1) break;
}
}
C
|