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
|
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
/*
opisno:
Zmanjkalo mi je časa, zato pišem odgovor opisno, kar bi moralo biti v redu, ker bi predvsem implementacija branja podatkov porabila veliko časa pisanja programa.
Torej. Preberemo podatke iz datoteke iz datoteke, kjer so vrstice ločene z novo vrstico in stolpci s presledkom v tabelo z vrednostjo.
Potem v zanki gremo čez vsako vrstico in v tej zanki čez vsak stolpec - vsako polje in si izpišemo za vsak zaporeden niz polij, ki imajo vrednost, večjo od 1, celotno vrstico (glej struct linija), vrednost, začetek in konec linije in usmerjenost (glej enum usmerjenost).
Potem gremo v zanki čez vsak stolpec in gledamo kot pri prejšnjem odstavku od zgoraj navzdol in si v enakem formatu, le da usmerjenost nastavimo na NAVPIČNO, zapisujemo linije z vrednostjo, večjo od 0.
Pri prejšnjih dveh odstavkih tudi iščemo vrstico z linijo z največjo vrednostjo in shranimo X in Y koordinate najmanj vrednega polja (trivialno ga je najti in te koordinate zapisati v dve spremenljivki). Tukaj vrednosti enkrat odštejemo vrednost najmanj vrednega polja, saj tja postavimo žeton in se ne šteje. To odšteto vrednost pa zapišemo v spremenljivko makskalkvred, saj bomo z njo primerjali skupne vrednosi parov.
Sedaj imamo vse vodoravne in navpične linije v dveh preglednih enodimenzionalnih tabelah (struct linija * linijev in struct linija * linije h). Za vsako vodoravno gremo v zanki čez seznam navpičnih in pogledamo, če se ti dve (navpična in vodoravna) liniji sekata. Sekata se, če je pozicija vodoravne linije med začetkom in koncem (vključno z začetkom in koncem). Sedaj pogledamo, ali je seštevek njunih vrednosti, potem ko mu dvakrat odštejemo vrednost polja, kjer se liniji sekata (ker tja postavimo žeton - dvakrat pa zato, kjer je to polje prisotno v obeh linijah), večji od največjega prejšnjega seštevka v spremenljivki makskalkvred, če je, zapišemo to izračunano vrednost v spremenljivko makskalkvred in X in Y koordinate polja, kjer se ti dve liniji sekata. Ena koordinata tega polja je torej pozicija navpične linije, druga pa pozicija vodoravne.
Ko smo šli čez vse pare linij pa na standardni izhod izpišemo spremenljivki obeh koordinat in zaključimo program.
*/
struct linija {
int začetek;
int konec;
int pozicija;
int vrednost;
};
int main (int argc, char ** argv) {
if (argc != 2) {
fprintf(stderr, "uporaba: %s polje.txt\n", argv[0] ? argv[0] : "pwnkit");
return 1;
}
int fd;
if ((fd = open(argv[1], O_RDONLY)) == -1) {
perror("open");
return 2;
}
struct stat statbuf;
if (fstat(fd, &statbuf) == -1) {
perror("fstat");
return 3;
}
char * vhod;
if ((vhod = mmap(NULL, statbuf.st_size, PROT_READ, MAP_SHARED, fd, 0)) == MAP_FAILED) {
perror("mmap");
return 4;
}
struct linija * linijev = NULL;
struct linija * linijen = NULL;
int linijv = 0;
int linijn = 0;
int * dolžine = NULL;
int ** vrstice = NULL;
int vrstic = 0;
int r = 0;
char * c = vhod;
int maksdolžina = 0;
do {
vrstice = realloc(vrstice, sizeof(*vrstice)*++vrstic);
dolžine = realloc(dolžine, sizeof(*dolžine)*vrstic);
vrstice[vrstic-1] = NULL;
dolžine[vrstic-1] = 0;
do {
vrstice[vrstic-1] = realloc(vrstice[vrstic-1], sizeof(*vrstice[vrstic-1])*++dolžine[vrstic-1]);
vrstice[vrstic-1][dolžine[vrstic-1]-1] = strtol(c, &c, 10);
} while (*c != '\n');
if (dolžine[vrstic-1] > maksdolžina)
maksdolžina = dolžine[vrstic-1];
} while (c+1 < vhod+statbuf.st_size && *c);
for (int i = 0; i < vrstic; i++) {
struct linija vrstica = {
.začetek = 0,
.konec = 0,
.pozicija = i,
.vrednost = 0
};
for (int j = 0; j < dolžine[i]; j++) {
if (vrstica.vrednost == 0) {
vrstica.začetek = j;
}
if (vrstice[i][j] == 0 && vrstica.vrednost) {
vrstica.konec = j;
linijev = realloc(linijev, sizeof(*linijev)*linijv++);
memcpy(linijev[linijv-1], &linija, sizeof(linija));
vrstica.vrednost = 0;
}
vrstica.vrednost += vrstice[i][j];
fprintf(stderr, "%d ", vrstice[i][j]);
}
fprintf(stderr, "\n");
}
for (int j = 0; j < maksdolžina; j++) {
for (int i = 0; i < vrstic; i++) {
//
}
}
r:
munmap(vhod, statbuf.st_size);
return r;
}
|
