Նվազագույն ուղու գումար
Տրված է
h բարձրությամբ և w լայնությամբ ամբողջ թվերով լցված մի ցանց։ Ձեզ խնդրում են գտնել ցանցի վերևի ձախ անկյունից ներքևի աջ անկյուն տանող մի ճանապարհ, որի վրա գտնվող թվերի գումարը կլինի հնարավորինս փոքր։ Թույլատրելի է շարժվել միայն աջ կամ ներքև ուղղություններով:3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թիվ
h և w (1 ≤ h, w ≤ 1000)։Հաջորդ
h տողերում տրված են w բացատներով բաժանված ամբողջ թվեր , որոնք ցույց են տալիս ցանցի արժեքները ։Ելք
Ծրագիրը պետք է տպի վերևի ձախ անկյունից ներքևի աջ անկյուն հասնելու համար անհրաժեշտ թվերի գումարի նվազագույն հնարավոր արժեքը:
Օրինակներ
Մուտք | Ելք |
3 4
3 2 1 3
1 9 2 3
9 1 5 4 | 15 |
Բացատրություն
Հնարավոր է շարժվել այս կերպ. 3 → 2 → 1 → 2 → 3 → 4
Հուշում 1
Դինամիկ Ծրագրավորման դեպքում վիճակը կարելի է ներկայացնել 2-չափանի զանգվածով:
Հուշում 2
Այդ վիճակը կարող է ներկայացնել տվյալ կոորդինատին հասնելու լավագույն տարբերակը (
d[r][c] ցույց է տալիս r-րդ տողի և c-րդ սյան համար լավագույն պատասխանը):Ինչո՞ւ «ագահ ալգորիթմը» ճիշտ չի աշխատում այս դեպքում։ Պատկերացրեք, որ յուրաքանչյուր քայլի ժամանակ մենք միշտ ընտրենք ամենափոքր թվով ուղղությունը։ Ի՞նչ խնդիր կառաջանա նման մոտեցման դեպքում:
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB