Fişierul intrare/ieşire:el.in, el.outSursă.campion 2010
Autorprof. Nistor MoAdăugată deIsabela_comanComan Isabela Patricia Isabela_coman
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

El

Gigel are o masă dreptunghiulară împărţită în m×n pătrate egale. În fiecare pătrat se gaseşte cel puţin o bomboană. El are dreptul să ia bomboane din mai multe pătrate care să formeze un L de lăţime 1. El poate alege “colţul” L-ului în orice pătrat, singura restricţie fiind ca ramura orizontală şi cea verticală să aibă lungimea cel puţin 2, deci să fie cel puţin încă un pătrat alăturat colţului pe orizontală şi cel puţin unul alăturat pe verticală.

Cerinţă

Găsiţi poziţia L-ului astfel ca numărul bomboanelor de pe pătratele ce compun L-ul să fie maxim.

Date de intrare

Fişierul de intrare el.in conţine pe prima linie numerele naturale m şi n reprezentând dimensiunea mesei. Pe următoarele m linii sunt câte n numere întregi separate de câte un spaţiu, matricea ce dă numărul de bomboane din fiecare pătrat.

Date de ieşire

Fişierul de ieşire el.out va conţine două linii. Pe prima linie numărul maxim de bomboane pe care le poate lua Gigel, iar pe următoarea linie 4 numere întregi separate de câte un spaţiu, precizând poziţia L-ului ce conţine acest număr maxim de bomboane. Poziţia e dată astfel: coordonatele colţului (linia şi coloana sa, numerotarea făcându-se de la 1), apoi lungimea ramurii orizontale, apoi lungimea ramurii verticale. Lungimile ramurilor înseamnă numărul de pătrate (inclusiv colţul) care alcătuiesc ramura, precedat de semnul minus dacă ramura orizontală este in stânga colţului, respectiv ramura verticală este în josul colţului. Dacă sunt mai multe soluţii posibile se alege cea care respectă, în ordine, criteriile următoare: are linia colţului minimă, are coloana colţului minimă, are ramura orizontală în stânga, are ramura verticală în jos.

Restricţii

  • 2 <= m, n <= 200
  • numărul de bomboane dintr-un pătrat este cel mult 1000

Exemplu

el.inel.out
4 4
3 1 1 4
2 1 9 2
6 1 1 8
4 3 2 1
24
2 1 4 -3

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici