241
Cerința
O tablă de șah se reprezintă ca o matrice cu n
linii și n
coloane în care pozițiile libere au valoarea 0
, iar pozițiile ocupate de piese sunt marcate prin valoarea 1
.
Exemplu
Intrare
5 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1
Ieșire
4
Explicație
Pionul poate lua maximum 4
piese, pe traseul (1,1) (2,2) (3,3) (4,4) (5,5)
. Acest traseu nu este unicul pe care pionul poate lua 4
piese.
#include <bits/stdc++.h> using namespace std; int n , a[101][101] , maxi; int main() { cin >> n; for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) cin >> a[i][j]; for(int i = 1 ; i <= n ; i++) a[1][i] = 0; for(int i = 2 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) { if(a[i][j] == 0) a[i][j] += a[i - 1][j]; else a[i][j] += max(a[i - 1][j - 1] , a[i - 1][j + 1]); } for(int i = 1 ; i <= n ; i++) maxi = max(a[n][i] , maxi); cout << maxi; }
Comentarii