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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
/*
ID: mytbk921
LANG: C
TASK: wormhole
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int compare(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int willstuck(int n, int holes[][2], int hmap[])
{
int i, j;
int time, cur;
for (i = 0; i < n; i++) {
/* try to enter hole i */
time = 0;
cur = i;
while (time < n) {
cur = hmap[cur];
for (j = cur+1; j < n; j++) {
if (holes[j][1] == holes[cur][1]) {
cur = j;
break;
}
}
if (j == n)
break;
else
time++;
}
if (time == n)
return 1;
}
return 0;
}
int nextmap(int n, int hmap[])
{
int i, j;
int has_next = 0;
for (i = n-1; i >= 0; i--) {
if (hmap[i] > i) {
for (j = hmap[i]+1; j < n; j++) {
if (hmap[j] == -1) {
has_next = 1;
hmap[hmap[i]] = -1;
hmap[i] = j;
hmap[j] = i;
break;
}
}
if (!has_next) {
hmap[hmap[i]] = -1;
hmap[i] = -1;
}
}
if (has_next)
break;
}
for (i++; i < n; i++) {
if (hmap[i] == -1) {
for (j = i+1; hmap[j] != -1; j++)
;
hmap[i] = j;
hmap[j] = i;
}
}
return has_next;
}
int main()
{
FILE *fin, *fout;
int N;
int holes[12][2];
int hmap[12];
int count = 0;
int i;
fin = fopen("wormhole.in", "r");
fout = fopen("wormhole.out", "w");
fscanf(fin, "%d", &N);
for (i = 0; i<N; i++)
fscanf(fin, "%d%d", &holes[i][0], &holes[i][1]);
fclose(fin);
qsort(holes, N, sizeof(int)*2, compare);
for (i = 0; i < N; i += 2) {
hmap[i] = i+1;
hmap[i+1] = i;
}
do {
if (willstuck(N, holes, hmap))
count++;
} while (nextmap(N, hmap));
fprintf(fout, "%d\n", count);
fclose(fout);
return 0;
}
|
