<prompt> Umepewa gridi ya m x n vyumba iliyoanzishwa kwa thamani hizi tatu zinazowezekana. -1 Ukuta au kizuizi. 0 lango. INF Infinity maana yake ni chumba tupu. Tunatumia thamani 231 - 1 2147483647 kuwakilisha INF kwani unaweza kudhani kuwa umbali wa lango ni chini ya 2147483647.Jaza kila chumba tupu kwa umbali wa _lango lake la karibu_. Ikiwa haiwezekani kufikia lango, inapaswa kujazwa INF.Mfano wa 1:Ingizo: vyumba 2147483647,-1,0,2147483647,2147483647,2147483647,2147483647,-1,2147483647,-7,-7 0,-1,2147483647,2147483647Pato: 3,-1,0,1,2,2,1,-1,1,-1,2,-1, 0,-1,3,4Mfano wa 2:Ingizo: vyumba -1Pato: -1Vikwazo: m vyumba.urefu n vyumbai.urefu 1 m, n 250 vyumbaij ni -1, 0, au 231 - 1.  <response>: chatukutoka kwa makusanyo kuagiza dequedef kutaAndGatesvyumba: m, n lenivyumba, lenivyumba0 q deque INF 2147483647 kwa mimi katika safum: kwa j katika safun: ikiwa vyumbaij 0: q.ongeza i, j maelekezo 0, 1, 0, -1, 1, 0, -1, 0 wakati q: i, j q.popleft kwa d kwa maelekezo: ni, nj i d0, j d1 ikiwa 0 ni m na 0 nj n na vyumbaninj INF: vyumbaninj vyumbaij 1 q.ongeza ni, njmaelezoAlgorithm hutumia BFS Utafutaji wa Upana-Kwanza kupata umbali mfupi zaidi kutoka kwa vyumba tupu hadi milango. Kwanza tunaunda foleni q na kuongeza viwianishi vya milango yote kwake. Kisha, tunaunda safu maelekezo iliyo na miondoko inayowezekana juu, chini, kushoto, kulia.Wakati foleni haina tupu, tunapita kwenye milango yote kwenye foleni, na kwa kila lango, tunachunguza majirani zake juu, chini, kushoto, kulia na angalia ikiwa ni vyumba tupu. Ikiwa wako, tunasasisha umbali wao kuwa 1 zaidi ya umbali wa lango la sasa, na kuongeza majirani hawa kwenye foleni. Umbali wa chumba ukisasishwa, hautasasishwa tena kwa sababu huo ndio umbali mfupi zaidi kupatikana. Mchakato unaendelea hadi vyumba vyote vinavyoweza kufikiwa visivyo na watu zisasishwe umbali wao.Algorithm hii inafanya kazi katika utata wa wakati wa Omn, ambapo m na n ni vipimo vya vyumba vya gridi ya taifa, kwani kila seli hutembelewa mara moja. 