teleport1
Data je kvadratna tabla dimenzija nxn. Polje u levom donjem ćošku ima koordinate (1, 1), a njemu dijagonalni ćošak ima koordinate (n, n). Cilj je stići od polja (1, 1) do (n, n). Neka polja sadrže teleporte. Ako polje (x, y) sadrži teleport, onda se teleport može iskoristi za teleportovanje na polje (u, t) za koje važi: (u, t) != (x, y), u >= x, t >= y. Napomenimo da korišćenje teleporta nije obavezno, i ako teleport na nekom polju postoji, onda je on eksplicitno naveden. Sa polja (x, y) se može preći na polja (x + 1, y) ili (x, y + 1), ili iskoristiti teleport ako na tom polju postoji. Kretanje van table nije dozvoljeno.
Svakom polju je pridružena celobrojna vrednost. Prilikom kretanja od polja (1, 1) do polja (n, n) sabiramo vrednosti svih polja koje smo obišli i tu sumu nazivamo cenom puta.
Koja je maksimalna cena puta koju možemo ostvariti?
Potom se učitava jedan broj T koji predstavlja broj teleporta. U narednih T redova se učitavaju po 4 broja x, y, u i t, što znači da na polju (x, y) postoji teleport do polja (u, t). Jedno polje može imati najviše jedan teleport.
7
5 1 -6 7 -9 1 2
1 -3 1 2 2 0 1
-4 2 -6 2 -4 1 1
-7 -4 2 -1 1 1 -2
2 -2 -1 -1 -4 -3 1
-3 -1 -1 1 -2 1 3
1 -2 -1 -3 2 -4 1
4
2 5 4 7
1 1 4 4
4 1 7 5
5 4 7 5Izlaz:
9Objašnjenje:
Kreće se od polja (1, 1). Sa polja (1, 1) se teleportujemo na polje (4, 4). Nakon toga pređemo na polje (5, 4). Na ovom polju imamo mogućnost da iskoristimo teleport, ali nam je bolje da ne koristimo, jer nas vodi u lošije rešenje. Potom nastavimo da polja (7, 7) poljima (6, 4) -> (6, 5) -> (6, 6) -> (6, 7) -> (7, 7).
Suma vrednosti polja koje smo obišli je 1 + (-1) + 2 + 2 + 2 + 0 + 1 + 2 = 9.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.