fbpx

Problema #329 – Bila – Rezolvari PBInfo

de Mihai-Alexandru

Cerinţa

Se consideră o tablă de joc de formă dreptunghiulară, împărţită în n lini şi m coloane. Se obţin astfel n*m zone şi se cunoaște înălțimea fiecărei zone. La o poziție cunoscută – linia istart, coloana jstart se află o bilă care se poate deplasa pe o poziție vecină (sus, jos, stânga, dreapta) doar dacă înălțimea poziției vecine este strict mai mică decât înălțimea poziției curente.

Determinați numărul maxim de zone prin care poate să treacă bila pentru a ajunge pe una dintre marginile tablei de joc.

Date de intrare

Fişierul de intrare bila.in conţine pe prima linie numerele n și m. Următoarele n linii conțin câte m numere naturale strict pozitive reprezentând înălțimile fiecărei zone.

Exemplu

bila.in

4 5
4 4 3 1 5
8 7 2 1 3
9 6 3 2 1
2 5 4 3 7
2 2

bila.out

5

Explicație

4 4 3 1 5
8 7 2 1 3
9 6 3 2 1
2 5 4 3 7
#include <bits/stdc++.h>
using namespace std;

ifstream cin("bila.in");
ofstream cout("bila.out");

int n , m , is , js , ib , jb , a[25][25] , b[25][25] , maxi;
char s;
const int di[] = {0 ,  0 , 1 , -1};
const int dj[] = {1 , -1 , 0 ,  0};

int inside(int i , int j)
{
    if(i == 1 || i == n || j == 1 || j == m)return 1;
    else return 0;
}

void back(int i , int j , int pas)
{
    if(inside(i , j))
    {
        maxi = max(maxi , pas - 1);
        return ;
    }
    else
        for(int d = 0 ; d < 4 ; d++)
        {
            int inou = i + di[d];
            int jnou = j + dj[d];
            if(!a[inou][jnou] && b[inou][jnou] < b[i][j])
            {
                a[i][j] = pas;
                back(inou , jnou , pas + 1);
                a[inou][jnou] = 0;
            }
        }
}
int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            cin >> b[i][j];
    for(int i = 0 ; i <= n + 1 ; i++)
        a[i][0] = a[i][m + 1] = -1;
    for(int i = 0 ; i <= m + 1 ; i++)
        a[0][i] = a[n + 1][i] = -1;
    cin >> is >> js;
    a[is][js] = 1;
    back(is , js , 2);
    cout << maxi;
    return 0;
}
Comentarii

S-ar putea sa iti placa