Soluții trimise

Boris s-a hotărât să viziteze o clădire de birouri. Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătratic de dimensiune N x N. Boris va intra în clădire prin biroul (1, 1) și va trece printr-o serie de birouri. Traseul se va termina în biroul (N, N). La trecerea dintr-un birou în altul se permite:

• pe același rând doar de la stânga la dreapta: (i, j) → (i, j+1);
• pe aceeași coloană doar de sus în jos: (i, j) → (i+1, j);
• în sens diagonal în următoarele două direcții: (i, j) → (i+1, j-1), dar și (i, j) → (i-1, j+1).

Cunoscând planul birourilor și valorile B(i, j) pentru 1 ≤ i, j ≤ N care îl așteaptă pe Boris în fiecare birou, ajutați-l să calculeze câștigul maxim pe care îl poate avea la ieșirea din clădire.