summaryrefslogtreecommitdiffstats
path: root/inf/zotks/3.c
blob: 1d4208cfc9a4d58648ae0133dc38f51b55afc284 (plain) (blame)
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
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <signal.h>
#include <string.h>
/* int ob (unsigned long long char * matrika, unsigned long long * obiskan, unsigned long long besed, unsigned long long ttl) {
	for (int i = 0; i < besed; i++) {
		for (int j = 0; j < besed; j++) {
			if (matrika[i*d+j] && obiskan[j]) {
				if (obiskan[i] == 0) {
					obiskan[i] = obiskan[j]+1;
					continue;
				}
				if (obiskan[j]+1 < obiskan[i])
					obiskan[i] = obiskan[j]+1; // če obstaja krajša pot
			}
		}
	}
} */
unsigned long long naivno (unsigned char * matrika, unsigned long long * obiskan, unsigned long long besed, unsigned long long ttl, unsigned long long d, unsigned long long lok) {
#ifndef EVAL
	fprintf(stderr, "ttl je %llu\n", ttl);
#endif
	if (!ttl)
		return 0;
	// if (obiskan[lok]) // nič več, smo že
	//	return 0;
	obiskan[lok]++;
	unsigned long long povezav = 1;
	for (unsigned long long i = 0; i < besed; i++) {
		if (matrika[besed*i+lok])
			povezav += naivno(matrika, obiskan, besed, ttl-1, d, i);
	}
	return povezav;
}
int main (void) {
	char buf[256];
	fgets(buf, 256, stdin);
	char * c;
	unsigned long long s = strtoul(buf, &c, 10);
	unsigned long long d = strtoul(++c, &c, 10);
	unsigned long long n = strtoul(++c, &c, 10); // število otrok
	unsigned long long z = strtoul(++c, &c, 10); // ??? . edit kasneje: aja, razumem, prva izrečena beseda
	char ** w = malloc(sizeof(char *)*s);
	unsigned long long i = 0;
	while (i++ <= s) {
		fgets(buf, 256 /* še newline in NULL */, stdin);
		w[i-1] = strdup(buf);
#ifndef EVAL
		fprintf(stderr, "w[%llu]: %s\n", i-1, w[i-1]);
#endif
		if (ferror(stdin) || feof(stdin))
			break;
	}
	unsigned char matrika[s*s]; // en megabajt največ, gucci
	memset(matrika, '\0', s*s);
	for (unsigned long long i = 0; i < s; i++) {
#ifndef EVAL
		fprintf(stderr, "%llu\n", i);
#endif
		for (unsigned long long j = 0; j < s; j++) {
			int ne = 0;
			for (unsigned long long k = 0; k < d; k++)
				if (w[i][k] != w[j][k]) 
					ne++;
			if (ne <= 1)
				matrika[s*i+j] = 1;
		}
	}
#ifndef EVAL
	for (unsigned long long i = 0; i < s; i++) {
		for (unsigned long long j = 0; j < s; j++) {
			fprintf(stderr, "%u ", matrika[s*i+j]);
		}
		fprintf(stderr, "\n");
	}
#endif
	unsigned long long obiskan[s]; // da vpisujemo TTLje
	memset(obiskan, '\0', s*sizeof(unsigned long long));
	fprintf(stderr, "%llu\n", naivno(matrika, obiskan, s, n+1, d, z));
	unsigned cx = 0;
	for (int i = 0; i < s; i++) {
		if (obiskan[i])
			cx++;
	}
	fprintf(stdout, "%u\n", cx);
	/* 
	int ret = ob(matrika, obiskan, d, n);
	if (ret == -1) { // nihče ni bil dodatno obiskan
		unsigned long long obiskanih = 0;
		for (int i = 0; i < d; i++)
			if (obiskan[d])
				obiskanih++;
		fprintf(stdout, "%u\n", obiskanih);
		return 0;
	}*/
	return 0;
}