Soluţia problemei Drum8

Fie i indicele poziţiei la care am ajuns în vectorul A şi j indicele poziţiei la care am ajuns în vectorul B. O deplasare în jos este echivalentă cu a incrementa valoarea lui i, iar o deplasare la dreapta este echivalentă cu a incrementa valoarea lui j.

Cazul 1: 0 ≤ A[i], B[i] ≤ 1

Incrementăm valorile lui i şi j până când A[i] > 0 şi B[j] > 0. Acum incrementăm i până ajungem la ultima valoare egală cu 1 din vectorul A. Apoi incrementăm j până ajungem la ultima valoare egală cu 1 din vectorul B. După nu mai este relevantă ordinea în care incrementăm pointerii deoarece A[i] * B[j] = 0, deci nu contribuie cu nimic la sumă.

Cazul 2: 0 ≤ A[i], B[i] ≤ 2

Incrementăm valorile lui i şi j până când A[i] > 0 şi B[j] > 0. Fie x numărul de valori de 1 până la primul 2 din vectorul A şi y numărul de valori de 2 din vectorul B. Dacă x < y, incrementăm i până ajungem la primul 2, apoi incrementăm j până la ultimul 2 din vectorul B, iar apoi incrementăm iar i până la ultimul 2 din vectorul A. Pentru x > y, incrementăm în ordine inversă. Acum i şi j pointează spre ultimele valori egale cu 2 din A, respectiv B. Dacă numărul de valori egale cu 1 care au ramas în vectorul A este mai mare decât numărul de valori din vectorul B, incrementăm j până la ultima valoare egala cu 1, iar apoi i până la ultima valoare egală cu 1. Analog pentru celălalt caz. Apoi este irelevantă ordinea în care incrementăm pointerii, deci afişăm traseul minim lexicografic.