[Cpt Balu]

Originally Posted by Redback

Milyen nyelven írtad? Ha C,C++,Java vagy Pascal akkor e-mail-ben küldd már el a forráskódot, mert van itt jóhényán forrásom, aztán megnézem, és azt is, hogy helyes-e

C#...
De sok programnyelvre át tudom írni, java, c++, delphi, pascal, asm, php amit akarsz.

Közben megálmodtam mégegy algoritmust, ami nem brute-force, csak sajna elég nehéz optimalizálni. Sajna képek nélkül elég nehéz lenne elmagyarázni, majd kitalálok valamit, addig is elküldtem a progit, az egyszerűség kedvéért 500x500-as képre korlátoztam, de bármekkora területen működik (1000x1000-nél sem nagyon ment 4-5sec fölé)
Itt egy táblázat 500x500-ra, hogy adott telítettség mellett milyen futási idők jöttek ki. Az oszlopok:
1. Telítettség: az a valószínűség, amivel a terület fel lett töltve, tehát nem a pontos területarány, ettől lehet kis eltérés
2. Minimális futási idő
4. Átlagos futási idő
3. Maximális futási idő
(adott valószínűséggel legenerált 100 egyedi térképen való futtatás alapján)

A 3 érték mindegyike millisec, jól látható, hogy kis telítettségnél (1-esek aránya <95%) a sok 0 elszórva a térképen megakadályozza, hogy nagy eredmény jöhessen létre, a kicsi lehetőségek vizsgálata hamar megtörténik [a futási idő O(n^3) közelítésű], valamint nagyon nagy telítettségnél (csak néhány 0 található) a kevés variáció vizsgálata tart rövid ideig (pontosabban, mivel nagyon nagy eredmények hamar születhetnek, sok vizsgálatot el tudunk dobni):

10,000% 17 21 31
20,000% 21 28 50
30,000% 24 30 35
40,000% 32 38 60
50,000% 35 37 41
60,000% 37 41 49
70,000% 42 47 63
80,000% 50 56 74
90,000% 73 79 93
91,000% 80 85 98
92,000% 78 87 109
93,000% 89 99 117
94,000% 106 110 130
95,000% 115 126 145
96,000% 138 146 164
97,000% 170 178 196
98,000% 242 255 274
99,000% 369 391 433
99,100% 388 411 434
99,200% 416 436 520
99,300% 457 518 648
99,400% 481 548 617
99,500% 503 582 798
99,600% 501 567 615
99,700% 518 589 649
99,800% 441 490 662
99,900% 314 395 456
99,910% 298 334 429
99,920% 276 307 336
99,930% 256 296 406
99,940% 231 269 327
99,950% 198 211 225
99,960% 162 204 271
99,970% 133 151 194
99,980% 115 126 160
99,990% 85 104 130
99,991% 78 91 111
99,992% 70 92 124
99,993% 61 69 93
99,994% 54 70 113
99,995% 53 66 90
99,996% 41 54 84
99,997% 40 47 71
99,998% 24 29 36
99,999% 18 26 43

A keresés bizonyíthatóan a legjobb eredményt hozza ki.