Question

Ai învățat să folosești matricele în programele tale și ai decis să implementezi un joc simplu. În joc, ai un personaj Max care se plimbă printr-o lume de formă dreptunghiulară, având n linii și m coloane.


El se poate deplasa din căsuța în care se află fie spre stânga, fie spre dreapta, fie în sus sau în jos. Pentru a face lucrurile mai interesante, te-ai gândit să adaugi un grad de siguranță pentru fiecare căsuță din joc, la fel cum în fiecare oraș există zone mai sigure și zone mai puțin sigure. Astfel, personajul tău poate acum să se deplaseze într-o căsuță vecină doar dacă nivelul său de siguranță e mai mare decât cel al căsuței din care vine.


Ai implementat jocul, care atribuie aleator (la întâmplare) un număr întreg fiecărei căsuțe din matrice la pornirea aplicației. Acel număr reprezintă gradul său de siguranță. Max se află în căsuța din colțul stânga sus și vrei să îl faci să se deplaseze în spirală, pornind spre dreapta.


Afișează mesajul DA dacă e posibil ca Max să parcurgă în spirală toate elementele matricei sau NU, în caz contrar.


Date de intrare

De pe prima linie se citesc de la tastatură numerele n și m. De pe următoarele n linii se citesc m numere naturale, reprezentând elementele matricei.


Date de ieșire

Programul va afișa DA în cazul în care Max poate parcurge în spirală toate elementele matricei, iar NU în caz contrar.


Restricții

1 ≤ n, m ≤ 50

1 ≤ fiecare grad de siguranță ≤ 1 000 000 000

Exemplu

Date de intrare Date de ieșire

4 4

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16 NU

4 4

1 2 3 4

14 16 17 5

13 19 18 7

11 10 9 8 DA
Limbaj C++

Answer 1

Pentru a rezolva această problemă, poți utiliza o metodă numită "parcurgere în spirală". Aceasta implică parcurgerea elementelor matricei începând din colțul din stânga sus și continuând în spirală spre dreapta, apoi în jos, apoi la stânga și în cele din urmă în sus.

Pentru a verifica dacă este posibil ca Max să parcurgă în spirală toate elementele matricei, poți folosi un algoritm care verifică dacă gradul de siguranță al fiecărei căsuțe din drumul lui este mai mare decât cel al căsuței din care vine. Dacă acest lucru se întâmplă pentru fiecare căsuță din matrice, atunci poți afișa mesajul "DA". În caz contrar, afișează mesajul "NU".

Acesta ar fi un exemplu de cod în C++ care rezolvă problema:

#include
using namespace std;

int n, m, a[55][55], dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

bool check(int x, int y) {
if (x < 1 || x > n || y < 1 || y > m) return false;
if (a[x][y] <= a[x - dx[0]][y - dy[0]]) return false;
return true;
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
int x = 1, y = 1, d = 0;
while (true) {
if (x == n && y == m) {
cout << "DA";
return 0;
}
if (!check(x + dx[d], y + dy[d])) d = (d + 1) % 4;
x += dx[d], y += dy[d];
}
cout << "NU";
return 0;
}