1 files changed, 108 insertions, 0 deletions
diff --git a/1.4/wormhole.c b/1.4/wormhole.c
new file mode 100644
index 0000000..551616a
--- /dev/null
+++ b/1.4/wormhole.c
@@ -0,0 +1,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;
+}