Cerința

Costică este alergător la un maraton. El parcurge un traseu sub forma unei matrice cu n linii şi m coloane linie cu linie şi pe fiecare linie, de la stânga la dreapta. Matricea conţine numere naturale.

Dacă Costică întâlneşte un număr prim, el este penalizat, fiind trimis pe linia şi coloana anterioară, iar dacă acesta întâlneşte un număr perfect, poate avansa pe linia şi coloana următoare. Dacă mişcarea pe linie şi pe coloană depăşeşte limitele matricei, atunci se va efectua numai mişcarea care nu trece de aceste limite sau nu se va efectua nici o mişcare.

Afişaţi timpul t în care parcurge Costică traseul, ştiind că deplasarea dintr-un element al matricei în oricare altul durează o secundă, iar fiecare penalizare sau avansare durează o secundă.

Un număr este perfect dacă suma cifrelor lui este un număr prim.

Dacă un număr este şi prim şi perfect, atunci el va fi considerat prim.

După penalizare sau avansare, numerele prime sau perfecte îşi pierd proprietățile.

Date de intrare

Programul citește de la tastatură numerele n şi m, iar apoi n*m numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul t, reprezentând timpul în care Costică parcurge traseul.

Restricții și precizări

• 1 ≤ n,m ≤ 500
• cele n numere citite vor fi mai mici decât 1.000.000

Exemplu

Intrare

4 5
6 9 3 2 1
8 3 12 4 0
1 1 34 8 7
5 3 5 9 8

Ieșire

28

Explicație

2 3 5 7 sunt numere prime, iar 2 3 5 7 12 34 sunt numere perfecte.

#include <bits/stdc++.h>
using namespace std;

int a[501][501];

bool prim(int n)
{
    int cnt = 0;
    for(int i = 1 ; i * i <= n ; ++i)
        if(n % i == 0 && i * i != n)
            cnt+=2;
        else if(i * i == n)
            cnt++;
    if(cnt==2)
        return 1;
    return 0;
}

bool perfect(int n)
{
    int s=0;
    while(n)
        s+=n%10 , n/=10;
    if(prim(s))
        return 1;
    return 0;
}

int main()
{
    int n , m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            cin >> a[i][j];
    int cnt=0;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
        {
            if(prim(a[i][j]))
            {
                cnt+=2;
                a[i][j]=1;
                if(i-1 > 0)
                    i--;
                if(j-1 > 0)
                    j--;
            }
            else if(perfect(a[i][j]))
            {
                cnt+=2;
                a[i][j]=1;
                if(i+1<=n)
                    i++;
                if(j+1<=m)
                    j++;
            }
            else
                cnt++;
        }
    }
    cout << cnt;
    return 0;
}