Izziv: Servisne postaje

Servisne postaje

V nekem mestu, ki ni Ljubljana, imajo navado postavljati točke, kjer je kolesarjem na voljo nekaj orodja za nujna popravila, pa še pumpa in pipa za vodo sta tam, da si lahko kolesar umije umazane roke in napolni bidon. Recimo, da so točke na koordinatah:

1, 1
1, 6
8, 3
3, 4
5, 5
8, 9

Če točke označimo z A, B, C, D, E, F, je to na zemljevidu videti tako:

..........
.A........
..........
........C.
...D......
.....E....
.B........
..........
..........
........F.

Mesto ima tloris kvadratne oblike. Razdalje med dvema točkama zato ne računamo po Pitagori, temveč je enaka kar vsoti absolutnih vrednosti razlik koordinat. Razdalja med E in C, recimo, je enaka 3 + 2 = 5. (Temu rečemo Manhattanska razdalja: nekdo, ki stoji na križišču 5. avenije in 42. ulice, bo do križišča med 8. avenijo in 32. ulico prehodil 3 avenije in 10 ulic, torej je razdalja med tema dvema križiščema 13. Pitagora je uporaben samo za tiste s helikopterjem.)

Kolesar, ki ima težave s kolesom, gre vedno do najbližje točke (v Manhattanskem smislu). Na gornjem zemljevidu lahko tako označimo področja mesta, ki jih pokriva posamezna točka.

aaaaa.cccc
aAaaa.cccc
aaaddecccc
aadddeccCc
..dDdeeccc
bb.deEeecc
bBb.eeee..
bbb.eeefff
bbb.eeffff
bbb.ffffFf

Točke, ki so na meji, smo ponazorili s pikami.

Ta zemljevid je samo del mesta. Mesto ima še predmestje in točka A, recimo, servisira še vse, kar je zgoraj levo. Področje točke A se torej razteza v neskončnost.

Napiši program, ki izpiše velikost največjega področja, ki se ne razteza v neskončnost. V gornjem primeru je to E, katerega področje je veliko 17.

Za začetek poskusi z gornjim primerom, v priponki pa je daljša datoteka. Prebereš jo z [[int(x) for x in v.split(",")] for v in open("input.txt")]. Pravilni odgovor za te, večje podatke, je 4011.

Spoilerji. Naloge se lahko lotiš na različne načine. Če je komu prišlo na misel kaj učenega, kot, recimo, flood fill naj se skulira. Niti dvodimenzionalne tabele ali seznama seznamov ne potrebujete. Gre tudi tako, da za vsako točko preprosto poiščeš najbližjo in šteješ. Za štetje lahko uporabljate slovar, lahko pa kar seznam, ki ima toliko elementov, kolikor je točk. Petnajsti element ustreza petnajsti točki. Problem z izločanjem neskončnih lahko rešiš z razmislekom, kako izgledajo meje ... ali pa bolj brutalno, tako da si predstavljaš prevelik zemljevid in vidiš, kdo se je preveč razkomotil. Naloga je v bistvu preprosta in bi jo morali znati rešiti tudi s tem, kar je bilo odslej odpredavano. Seveda pa se lahko lotite reševanja tudi v poljubnem drugem jeziku.

Datoteka z večjim primerom (pravilni odgovor: 4011)