<prompt> Mashetani walikuwa wamemkamata binti wa mfalme na kumfunga katika kona ya chini kulia ya chimba. Dunge lina vyumba m x n vilivyowekwa katika gridi ya P2. shujaa wetu shupavu hapo awali aliwekwa katika chumba cha juu kushoto na lazima apige njia kupitia shimoni ili kumwokoa bintiye.Knight ina hatua ya awali ya afya inayowakilishwa na nambari chanya. Ikiwa wakati wowote kiwango chake cha afya kitashuka hadi 0 au chini, atakufa mara moja.Vyumba vingine vinalindwa na mapepo inayowakilishwa na nambari hasi, kwa hivyo knight hupoteza afya wakati wa kuingia vyumba hivi; vyumba vingine ni tupu vinawakilishwa kama 0 au vina orbs za uchawi ambazo huongeza afya ya knight inayowakilishwa na nambari chanya.Ili kufikia binti mfalme haraka iwezekanavyo, knight anaamua kusogea tu kulia au chini katika kila hatua.Rudisha _afya ya awali ya knight ili aweze kumwokoa bintiye_.Kumbuka kwamba chumba chochote kinaweza kuwa na vitisho au nguvu-ups, hata chumba cha kwanza ambacho knight huingia na chumba cha chini kulia ambapo binti mfalme amefungwa.Mfano wa 1:Ingizo: shimo -2,-3,3,-5,-10,1,10,30,-5Pato: 7Maelezo: Afya ya awali ya shujaa lazima iwe angalau 7 ikiwa atafuata njia bora: KULIA- KULIA - CHINI - CHINI.Mfano wa 2:Ingizo: shimo 0Pato: 1Vikwazo: m dungeon.length n shimoi.urefu 1 m, n 200 -1000 shimoij 1000  <response>: chatudef countMinimumHPshimoni: m, n lenishimoni, lenishimoni0 dp 0 n kwa _ masafam kwa i katika safu m - 1, -1, -1: kwa j katika safun - 1, -1, -1: ikiwa i m - 1 na j n - 1: dpij min0, shimoij elif i m - 1: dpij min0, dpij 1 shimoij elif j n - 1: dpij min0, dpi 1j shimoij kwingine: dpij min0, maxdpi 1j, dpij 1 shimoij return absdp00 1maelezoKanuni hutumia upangaji programu kupata kiwango cha chini zaidi cha afya kinachohitajika kwa njia ya kutoka chini kwenda juu kwa kuanzia kona ya chini kulia ya shimo hadi kona ya juu kushoto. Tunaunda meza ya dp yenye ukubwa sawa na shimoni na kuijaza awali na zero. Kisha tunarudia kila seli kwenye shimo kutoka chini-kulia hadi juu-kushoto. Kwa kila seli, tunazingatia seli zilizo karibu za kulia na chini ikiwa zipo na kuhesabu kiwango cha chini cha afya kinachohitajika ili kusonga mbele. Tunasasisha jedwali la dp na maadili haya. Kiwango cha chini cha afya kinachohitajika kusongeshwa kulia au chini, pamoja na thamani ya sasa ya seli, huhifadhiwa kwenye seli ya sasa kwenye jedwali la dp. Hatimaye, tunarudisha thamani kamili ya seli ya juu kushoto ya jedwali la dp pamoja na moja kwa nukta ya afya ya mwanzo. Hii inatupa kiwango cha chini cha afya kinachohitajika ili kufika kwa binti mfalme. 