O sa postez aici solutia mea pentru ca este diferita de solutia oficiala, si are o complexitate mai buna, dar nu sunt sigur ca este corecta (dar am luat 100 de puncte), asa ca poate ma ajuta cineva sa demonstrez ca e corect sau nu ce fac
Solutie de complexitate
O(N^2) timp, si
O(N^2) memorie
Fie D distanta minima intre A si B. Dupa cum zice si in solutia oficiala A si B vor incerca sa mearga pe drumurile minime intre cele doua puncte. In caz ca D este impar A, castiga.
Ramane cazul in care D este par. Cand D este par A o sa incerce sa nu ajunga in aceeasi pozitie cu B (pentru ca atunci B va sari peste A) si B o sa incerce sa ajunga in aceeasi pozitie cu A ca sa poata sa sara peste A.
Fie Xa, Ya si Xb si Yb pozia lui A si respectiv B pe tabla. Fie Dx = |Xa - Xb| si Dy = |Ya - Yb|. Ca B sa il ajunga pe A inseamna ca el trebuie sa faca Dx si Dy sa fie egale cu 0.
O sa facem in continuare niste observatii pe o tabla libera de obstacole:
A***
****
****
***B
in acest caz D = 6
Daca A muta la stanga, se observa ca B este obligat sa mute in sus altfel nu-l va putea prinde pe A.
In mod asemanator daca A muta in jos, B este obligat sa mute la dreapta.
Putem observa ca B incearca sa minimizeze MAX(Dx, Dy) si are o singura modalitate de a face acest lucru. Poate ca va ganditi ce se intampla cand Dx == Dy ca atunci o va putea lua in mai multe directii, dar din cauza ca D este par, dupa ce A muta, D (distanta intre A si B) va fi impar => Dx + Dy = impar => Dx != Dy => B muta pe directia care va miscora valoarea maxima intre Dx si Dy. Se poate usor observa ca daca B nu muta astfel va trece pe langa A, si se potriveste foarte bine cu faptul ca atunci cand B il prinde pe A, MAX(Dx, Dy) = 0.
Deci de aici putem deduce ca B o sa se mute in functie de A in modul urmator: trebuie sa ramana pe drumul minim dintre A si B si sa minimizeze MAX(Dx, Dy), si ca pentru aceasta el are o singura mutare posibila la fiecare pas (dupa ce muta A)
Pentru ca B este dependent de pozitia lui A putem sa facem urmatoarea dinamica : din[xa][ya] = true daca A are sigur strategie de castig daca se afla in pozitia (xa, ya) pe tabla. Dupa cum am stabilit mai sus pozitia lui B o sa fie unic determinata si o sa fie un anume (xb, yb). O sa rezolvam aceasta dinamica memoizat pentru ca este mult mai usor sa urmarim poztia lui B la fiecare pas.
O sa scriu un mic
pseudo-cod pentru a se intelege mai bine:
bool get_din(int xa, int ya, int xb, int yb)
{
daca deja_calculat[xa][ya] == true return din[xa][ya];
deja_calculat[xa][ya] = true;
daca A este in pozitia finala return din[xa][ya] = true;
daca pozitia lui B este deasupra lui A return din[xa][ya] = false; // (xa == xb && ya == yb) <=> MAX(ABS(xna - xnb), ABS(yna, ynb) == 0
pentru fiecare pozitie (xna, yna) inspre care o poate lua A pe drumul minin do {
calculeaza noua pozitie B (xnb, ybn) pe drumul minim, astfel incat MAX(ABS(xna - xnb), ABS(yna - ynb)) minim posibil
daca get_din(xna, yna, xnb, ynb) == true return din[xa][ya] = true; // reapelam functia pentru un caz mai mic
}
return din[xa][ya] = false;
}
Explicatie algoritm: ------------------------------------------------------------------------------------------
La fiecare pas mai intai vedem daca suntem intr-o stare finala (ori A este la final, ori A si B sunt pe aceeasi pozitie, caz in care B poate sa sara peste A si sa castige).
Apoi incercam sa mutam A spre o pozitie castigatoare (in acelasi timp calculam si unde ajunge B). Daca gasim o astfel de pozitie inseamna ca pozitia curenta este si ea castigatoare, altfel pozitia curenta este pierzatoare.
La inceputul functiei verificam daca cumva am mai calculat starea curenta pentru a nu o calcula din nou. In aceasta consta memoizarea. Pornim de la starea initiala (cea mai mare) si ne mutam spre starile mai mici si chiar finale si nu invers cum facem la majoritatea dinamicilor nememoizate.
-------------------------------------------------------------------------------------------------------------
Se mai observa ca chiar daca B nu poate miscora la acest pas MAX(Dx, Dy) nu inseamna ca pierde neaparat pentru ca drumul intre A si B poate fi unul serpuit din cauza obstacolelor. De genul:
A**********
***********
***********
****###*###
****#***###
****#*#####
****#*#***#
****#*#*#*#
****#***#*#
****#####B#
****#######
Acest ultim caz ma face sa fiu nesigur pe solutia mea pentru ca din cauza drumurilor serpuite conditia de mai sus pentru drumul parcurs de B devine un pic cam aiurea, dar ma gandesc ca atunci cand A si B vor fi cumva intr-o pozitie mai apropiata fara un drum serpuit intre ele atunci acea conditie conteaza si pana atunci nu, pentru ca pana atunci nu conteaza foarte mult pe unde o ia fiecare ca tot acolo o sa ajunga. (nu prea are sens ultima fraza dar nu stiu sa formulez mai bine
).
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena