Zīmējumā attēlots skaitļu šūnu fragments, kura šūnās (zīmējumā aplīšos) ir ierakstīti skaitļi (malas garums attēlotajam šūnu fragmentam ir 3).
Maršruts sākas no jebkuras šūnas augšējā līnijā un beidzas ar kādu šūnu apakšējā līnijā. No katras šūnas maršruts var turpināties tikai vai nu diagonāli uz leju pa labi vai arī diagonāli uz leju pa kreisi. Veidojot maršrutu caur skaitļu šūnām, jums ir atļauts ne vairāk kā vienu reizi izpildīt divu skaitļu maiņu ne vairāk kā vienā skaitļu šūnu horizontālajā rindā. (Maiņa būtībā nozīmē, ka vienā izvēlētā rindā jums ir atļauts pārvietot lielāko šis rindas skaitli uz jebkuru vietu tajā pašā rindā).
Jūsu uzdevums ir uzrakstīt programmu, kas skaitļu šūnu fragmentam atrod lielāko starp visu iespējamo maršrutu skaitļu summām,
izmantojot iespēju vienu reizi izpildīt skaitļu maiņu, kā aprakstīts iepriekš.
Ierobežojumi:
Skaitļu šūnu fragmenta malas garums ir teksta faila shunas.in pirmajā rindā. Ja fragmenta malas garums ir n, fragments sastāv no 2n-1 skaitļu šūnu rindas. Nākamajās 2n-1 ievaddatu faila rindās ir doti katrai šūnu rindai atbilstošie skaitļi, kas atdalīti ar tukšumsimboliem.
Teksta faila shunas.out vienīgajā rindā jāizvada vesels skaitlis - vislielākā iespējamā maršruta summa.
| shunas.in | shunas.out |
3 1 2 3 3 2 2 1 4 2 8 0 3 5 3 1 2 3 1 4 |
22 |
Zīmējumā maršruts ar lielāko summu (3+2+8+5+4=22) ir ieēnots.
Atzīmēsim, ka skaitlis '5' ceturtajā rindā ir jāsamaina uz šīs rindas trešo šūnu (skaitot no kreisās puses).