<prompt> Unadhibiti roboti ambayo iko mahali fulani kwenye chumba. Chumba kimeundwa kama gridi ya jozi m x n ambapo 0 inawakilisha ukuta na 1 inawakilisha nafasi tupu.Roboti huanzia mahali pasipojulikana katika chumba ambacho kimehakikishwa kuwa tupu, na huna ufikiaji wa gridi ya taifa, lakini unaweza kuhamisha roboti kwa kutumia API Roboti uliyopewa.Una jukumu la kutumia roboti kusafisha chumba kizima yaani, kusafisha kila seli tupu kwenye chumba. Roboti iliyo na API nne zilizotolewa inaweza kusonga mbele, kugeuka kushoto au kugeuka kulia. Kila zamu ni digrii 90.Roboti inapojaribu kuhamia kwenye seli ya ukutani, kitambuzi chake kikubwa hutambua kizuizi, na hukaa kwenye seli ya sasa.Tengeneza algoriti ya kusafisha chumba kizima kwa kutumia API zifuatazo:interface Roboti hurejesha kweli ikiwa kisanduku kifuatacho kimefunguliwa na roboti inasogea hadi kwenye seli. hurejesha sivyo ikiwa kisanduku kifuatacho ni kikwazo na roboti itasalia kwenye kisanduku cha sasa. boolean move; Roboti itakaa kwenye kisanduku kimoja baada ya kupiga simu turnLeftturnRight. Kila zamu itakuwa nyuzi 90. utupu turnLeft; utupu turnRight; Safisha kiini cha sasa. utupu safi ;Kumbuka kwamba uelekeo wa awali wa roboti utatazama juu. Unaweza kudhani kingo zote nne za gridi ya taifa zote zimezungukwa na ukuta.Jaribio maalum:Ingizo hutolewa tu ili kuanzisha chumba na nafasi ya roboti ndani. Lazima kutatua tatizo hili kipofu. Kwa maneno mengine, ni lazima udhibiti roboti kwa kutumia API nne zilizotajwa bila kujua mpangilio wa chumba na nafasi ya roboti ya awali.Mfano wa 1:Ingizo: chumba 1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1, 1,0,1,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,1,1, 1,1,1,1, safu mlalo 1, safu mlalo 3Pato: Roboti ilisafisha vyumba vyote.Maelezo: Gridi zote kwenye chumba zimetiwa alama na 0 au 1.0 inamaanisha kisanduku kimezuiwa, wakati 1 inamaanisha kisanduku kinaweza kufikiwa.Roboti mwanzoni huanzia kwenye nafasi ya safu1, col3.Kutoka kona ya juu kushoto, nafasi yake ni safu moja chini na nguzo tatu kulia.Mfano wa 2:Ingizo: chumba 1, safu 0, col 0Pato: Roboti ilisafisha vyumba vyote.Vikwazo: m chumba.urefu n chumbai.urefu 1 m 100 1 n 200 chumbaij ni 0 au 1. 0 safu m 0 col n chumbasafucol 1 Seli zote tupu zinaweza kutembelewa kutoka kwa nafasi ya kuanzia.  <response>: chatukutoka math import combdef kthNjiaNdogolengwa, k: safu, safu marudio jibu kwa mimi katika safu safu col: ikiwa safu 0: jibu H nakala - 1 elif col 0: ans V safu - 1 elif k combsafu safu - 1, safu - 1: jibu H nakala - 1 kwingine: ans V k - kuchana safu safu - 1, safu - 1 safu - 1 kurudi ansmaelezoAlgorithm huanza katika eneo lililotolewa na kuzunguka kupitia njia zote zinazowezekana hadi kufikia seli lengwa, kwa kuchukua tu hatua ya kulia au ya chini. Katika kila hatua, inalinganisha njia ya sasa na njia ndogo ya kileksikografia, na kuendelea katika mojawapo ya maelekezo kulingana na hali ya kuangalia. Ili kupata maagizo madogo zaidi ya kth kimsamiati, tunatumia mbinu ya mseto wa kihisabati ili kuangalia kama kuchukua hatua ya mlalo inakidhi hali au la. Ikiwa inafanya, tunachukua hatua ya usawa; vinginevyo, tunachukua hatua ya wima.Utata wa saa wa algoriti hii ni Osafu na safu, ambapo safu mlalo na safu wima ni viwianishi vya kisanduku lengwa, kwa sababu tunahitaji kupitia seli zote katika safu mlalo na safu wima. 