50245. Square tiling
難度：4.8/5 Used Time: 16:22
極度要注意，這種拿排列組合的方式「不會按照字典序」，「不會按照字典序」，「不會按照字典序」，所以要換下面的遞迴方法。1
2
3
4
5
6
7
8
9
10
11
12
13
14void dfs(int arr[], int now_idx, int max_idx){
if(now_idx == max_idx){
for(int i = 0; i < max_idx; i++) printf("%d ", arr[i]);
printf("\n");
}
else{
for(int i = now_idx; i < max_idx; i++){
swap(arr[now_idx], arr[i]);
dfs(arr, now_idx + 1, max_idx);
swap(arr[now_idx], arr[i]);
}
}
}
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#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define swap(a,b) {int t = (a); (a) = (b); (b) = t;}
// void swap(int* a, int *b){
// int t = *a;
// *a = *b;
// *b = t;
// }
typedef struct{
int l, t, r, b;
} square;
int n;
square s[36];
int check(int arr[]){
for(int i = 0; i < n; i++){
for(int j = 0; j < n - 1; j++){
if(s[arr[i * n + j]].r != s[arr[i * n + j + 1]].l){
return 0;
}
}
}
for(int j = 0; j < n; j++){
for(int i = 0; i < n - 1; i++){
if(s[arr[i * n + j]].b != s[arr[(i + 1) * n + j]].t){
return 0;
}
}
}
return 1;
}
void print(int arr[]){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
printf("%d%c", arr[i * n + j], (j == n - 1) ? '\n' : ' ');
}
}
}
int dfs(int arr[], int used[], int now_idx){
if(now_idx == n * n){
if(check(arr)){
print(arr);
return 1;
}
else{
return 0;
}
return 0;
}
else{
for(int i = 0; i < n * n; i++){
if(used[i] == 0){
if(now_idx % n != 0){
if(s[arr[now_idx - 1]].r != s[i].l) continue;
}
if(now_idx >= n){
if(s[arr[now_idx - n]].b != s[i].t) continue;
}
used[i] = 1, arr[now_idx] = i;
int rtv = dfs(arr, used, now_idx + 1);
if(rtv) return 1;
used[i] = 0; arr[now_idx] = -1;
}
}
return 0;
}
}
int main(){
while(scanf("%d", &n) != EOF){
for(int i = 0; i < n * n; i++) scanf("%d %d %d %d", &s[i].l, &s[i].t, &s[i].r, &s[i].b);
int arr[36] = {0}, used[36] = {0};
int rtv = dfs(arr, used, 0);
if(!rtv) printf("no solution\n");
}
}