Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Drumuri

Adăugată de :
sorynsoo
Sursă :
XOR2011
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
200 ms
Limită memorie :
5536 kbytes

Considerăm o matrice de numere naturale cu N linii şi N coloane. Definim un drum în această matrice ca fiind o succesiune maximală de componente alăturate pe linii şi coloane din matrice cu proprietatea că valorile din aceste componente sunt în ordine strict crescătoare. Succesiunea maximală se referă la faptul că drumul nu poate fi extins la unul din capetele sale. Considerăm ca exemplu matricea:

1  4  7

5  3  9

8 12  2

Un drum este 1 5 8 12. Alte drumuri sunt 3 9, sau 3 12, sau 1 4 7 9, sau 3 4 7 9. De menţionat că 3 5 8 nu este drum pentru că nu este maximal, el putând fi extins la unul din capete cu 12, obţinându-se drumul 3 5 8 12.

 

Cerinţa

Să se determine numărul drumurilor din matrice.

 

Date de intrare

Fişierul de intrare conţine pe prima linie un număr natural N reprezentând dimensiunile matricei. Pe următoarele N linii sunt descrise liniile matricei, pe fiecare linie aflându-se câte N numere naturale separate prin câte un spaţiu.

 

Date de iesire

Fişierul de iesire va conţine un singur număr natural reprezentând numărul de drumuri din matrice.

 

Restricţii şi precizări:

  • 3 <= N <= 300
  • Valorile memorate în matrice sunt numere naturale cuprinse între 1 şi 10 000

 

Exemplu

  Date de intrare

  Date de iesire  

  Explicaţii

  3

  1 4 7

  5 3 9

  8 12 2

  8

  Cele 8 drumuri sunt:

  1 4 7 9

  1 5 8 12

  3 4 7 9

  3 5 8 12

  3 9

  3 12

  2 9

  2 12

 


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Grafuri


Comentarii

Adauga un comentariu: Click !