Olimpiada Jude
teană de InformaticăCLASA a IX-a
PROBLEMA 2 (Mouse)
Un experiment urmăreste comportarea unui soricel pus într-o cutie dreptunghiulară, împărtită în m´ n cămărute egale de formă pătrată. Fiecare cămărută contine o anumită cantitate de hrană. Soricelul trebuie să pornească din coltul (1,1) al cutiei si să ajungă în coltul opus, mâncând cât mai multă hrană. El poate trece dintr-o cameră în una alăturată (două camere sunt alăturate dacă au un perete comun), mănâncă toată hrana
din cămărută atunci când intră si nu intră niciodată într-o cameră fără hrană. Stabiliti care este cantitatea maximă de hrană pe care o poate mânca si traseul pe care îl poate urma pentru a culege această cantitate maximă.Datele de intrare
Fisierul de int
rare mouse.in contine pe prima linie două numere m si n reprezentând numărul de linii respectiv numărul de coloane ale cutiei, iar pe următoarele m linii cele m´ n numere reprezentând cantitatea de hrană existentă în fiecare cămărută, câte n numere pe fiecare linie, separate prin spatii. Toate valorile din fisier sunt numere naturale între 1 si 100.Datele de iesire
În fisierul de iesire
mouse.out se vor scrie pe prima linie două numere separate printr-un spatiu: numărul de cămărute vizitate si cantitatea de hrană maximă culeasă. Pe următoarele linii se va scrie un traseu posibil pentru cantitatea dată, sub formă de perechi de numere (linie coloană) începând cu 1 1 si terminând cu m n.mouse.in
2 4
1 2 6 3
3 4 1 2
mouse.out
7 21
1 1
2 1
2 2
1 2
1 3
1 4
2 4
Exemplu :
Timp maxim de executare: 1 sec/test
Pentru revenire închideti fereastra curentă