Rezolvare PBinfo #4098

Data stelară 3210: Căpitanul navei USS Entrerprise, Jean-Luc Picard se află într-o misiune importantă în cuadrantul Beta al galaxiei. Acesta trebuie să ajungă cât mai rapid de la planeta Vulcan până la planeta Qo’noS, dar din păcate pentru această misiune Jean-Luc Picard nu va putea să ajungă instantaneu la destinație folosind warp drive-ul navei, ci va trebui să se deplaseze în mod normal, din sector în sector.

Harta galaxiei este reprezentată sub forma unei tabele bidimensionale de dimensiune N x N, în care fiecare celulă reprezintă un sector al galaxiei. Coordonatele sectorului în care se află planeta Vulcan sunt (xs, ys), iar coordonatele sectorului în care se află planeta Qo’noS sunt (xf, yf).

USS Enterprise se poate deplasa într-o unitate de timp dintr-un sector în oricare dintre sectorele adiacente, fie pe aceeasi linie, fie pe aceeasi coloană. În plus, nava poate staționa o perioadă nedeterminată de timp în orice sector. Nava se poate afla doar pe un sector care la momentul actual de timp nu o pune în pericol.

Pentru că nicio aventură nu este lipsită de pericole, drumul lui Jean-Luc Picard este presărat de pulsari, obiecte cosmice foarte periculoase care lansează în vecinătatea lor, la intervale fixe de timp, unde gravitaționale care ar putea distruge USS Enterprise.

Un pulsar P_i este caracterizat prin patru variabile (xi, yi, ri, ti), unde (xi, yi) reprezintă coordonatele sectorului în care se regăsește pulsarul, ri reprezintă raza de acțiune a pulsarului, iar ti reprezintă starea în care se află pulsarul la momentul de început al deplasării navei.

Un pulsar Pi trece periodic printr-un număr de ri stări de la 0 la ri - 1. Când acesta se află în starea t, acesta afectează toate sectoarele aflate la o distanță Manhattan mai mică sau egală cu t față de sectorul în care se află acesta. Dacă pulsarul la un moment de timp se află în starea t, la momentul următor se va afla în starea (t + 1) % ri.

Un exemplu de funcționare al unui pulsar cu rază de acțiune r = 4, timp de 6 unități de timp, începând cu t = 0 este următorul:

Cerința

Vouă vă revine rolul de a îl ajuta pe Jean-Luc Picard și să îi răspundeți la una din următoarele întrebări știind harta galaxiei:

• Care este numărul maxim de sectoare ale galaxiei Smax afectate la orice moment de timp de către cel puțin un pulsar.
• Care este timpul minim Tmin de care are nevoie Jean-Luc Picard pentru a ajunge pe planeta Qo’noS.

Date de intrare

Din fișierul de intrare pulsar.in se vor citi următoarele:

• Pe prima linie se vor afla trei numere C, N și P separate prin câte un spațiu, reprezentând cerința ce trebuie rezolvată, dimensiunea galaxiei și numărul de pulsari din galaxie
• Pe următoarele P linii se vor afla câte patru numere separate prin spațiu, xi, yi, ri, ti, reprezentând descrierea pulsarului Pi
• Pe penultima linie se vor afla două numere separate printr-un spațiu reprezentând coordonatele sectorului planetei Vulcan xs și ys
• Pe ultima linie se vor afla două numere separate printr-un spațiu reprezentând coordonatele sectorului planetei Qo’noS xf și yf

Date de ieșire

În fișierul de ieșire pulsar.out se va afișa un singur număr în funcție de cerință:

• Dacă C = 1, atunci se va afișa numărul Smax
• Dacă C = 2, atunci se va afișa numărul Tmin

Restricții și precizări

• Distanța Manhattan dintre două coordonate (x1, y1) și (x2, y2) este definită ca: |x1 - x2| + |y1 - y2|
• Nava nu va putea părăsi la niciun moment de timp harta galaxiei
• Undele pulsarilor pot părăsi harta galaxiei, dar acele sectoare nu reprezintă interes pentru problema noastră
• Se garantează că la momentul plecării, nava nu este aflată în pericol
• Se garantează că există soluție
• Pot exista mai mulți pulsari în același sector
• C ∈ {1, 2}
• 3 ≤ N ≤ 500
• 1 ≤ P ≤ 15.000
• 0 ≤ ti < ri ≤ 6 pentru orice 1 ≤ i ≤ P
• 1 ≤ xs, ys, xf, yf ≤ N
• 1 ≤ xi, yi ≤ N pentru orice 1 ≤ i ≤ P
• Pentru 19 puncte, C = 1
• Pentru 22 de puncte, C = 2 și ri = 1 pentru orice 1 ≤ i ≤ P
• Pentru 9 puncte, C = 2, N ≤ 7 și ri ≤ 3 pentru orice 1 ≤ i ≤ P
• Pentru 13 puncte, C = 2, ti = 0 pentru orice 1 ≤ i ≤ P
• Pentru 37 puncte, C = 2

Exemplul 1:

pulsar.in

1 5 4
3 1 2 1
1 5 3 1
5 3 2 0
3 4 2 1
1 1
5 5

pulsar.out

14

Explicație

Mai jos se poate observa dumul realizat de USS Enterprise. Cu albastru s-a ilustrat nava, cu rosu, zonele afectate de pulsari, iar cu verde planeta Qo’nos:

Se observă că nu va exista niciodată un moment de timp în care pulsarii să ocupe mai mult de 14 sectoare.

Exemplul 2:

pulsar.in

2 5 4
3 1 2 1
1 5 3 1
5 3 2 0
3 4 2 1
1 1
5 5

pulsar.out

9

Explicație

În figura de mai sus este prezentat un posibil drum de durată 9. Acest timp este și minim pentru exemplul dat.