Максимални безбедни пут
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 0,25 s | 64 Mb | standardni izlaz | standardni ulaz |
Дата је матрица Anxm у којој се налазе мине означене са 0, остала поља садрже природне бројеве. Треба из било ког поља у првој колони доћи на било које поље у последњој колони матрице безбедним путем. Пут је безбедан ако не садржи мину и не садржи поље коме је сусед, горњи, доњи, леви или десни, мина. Кроз матрицу можемо да се крећемо у четри правца горе, доле, десно и лево и при томе на једно поље можемо стати највише једанпут. Одреди максимални збир бројева који се могу наћи на неком безбедном путу од прве до последње колоне.
Улаз
Прва линија стандардног улаза садржи димензије матрице, два природна броја, m и n (1<m,n≤20). На стандардном улазу у следећих n линија налазе се по m целих бројева већих или једнаких 0, бројеви су раздвојени по једним бланко карактером, и представљају редом елементе матрице.
Излаз
На стандардном излазу приказати природан број који представља максималну суму безбедног пута од прве до последње колоне. Ако безбедан пут не постоји приказати -1.
Пример
Улаз
4 4 5 1 2 0 1 2 3 4 2 4 1 1 0 1 1 1
Излаз
17
Објашњење
1+5+1+2+4+1+1+1+1=17
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.