<prompt> Kwa kuzingatia gridi ya m x n ya vibambo ubao na mfuatano neno, rudisha kweli _kama_ neno _lipo katika gridi_.Neno linaweza kutengenezwa kutoka kwa herufi za seli zinazokaribiana kwa mpangilio, ambapo seli zilizo karibu ziko jirani kwa mlalo au wima. Seli hiyo hiyo ya herufi haiwezi kutumika zaidi ya mara moja.Mfano wa 1:Ingizo: ubao A , B , C , E , S , F , C , S , A , D , E , E , neno ABCCEDPato: kweliMfano wa 2:Ingizo: ubao A , B , C , E , S , F , C , S , A , D , E , E , neno TAZAMAPato: kweliMfano wa 3:Ingizo: ubao A , B , C , E , S , F , C , S , A , D , E , E , neno ABCBPato: si kweliVikwazo: m ubao.urefu n ubaoi.urefu 1 m, n 6 1 neno.urefu 15 ubao na neno linajumuisha herufi ndogo na kubwa za Kiingereza pekee.Fuatilia: Je, unaweza kutumia kupogoa kwa utafutaji ili kufanya suluhisho lako kwa haraka na ubao mkubwa zaidi?  <response>: chatudef kuwepoubao, neno: m, n leniubao, leniubao0 def dfsi, j, k: ikiwa sivyo 0 i m au la 0 j n au ubaoij ! nenok: kurudi Uongo ikiwa k lenneno - 1: kurudi Kweli tmp, ubaoij ubaoij, res dfsi 1, j, k 1 au dfsi - 1, j, k 1 au dfsi, j 1, k 1 au dfsi, j - 1, k 1 ubao ij tmp kurudi res kwa mimi katika safum: kwa j katika safun: ikiwa dfsi, j, 0: kurudi Kweli kurudi UongomaelezoKwa kila utekelezaji ulio hapo juu, tunatumia algoriti kulingana na Utafutaji wa Kina-Kwanza DFS ili kuvuka ubao wa gridi ya taifa. Chaguo za kukokotoa za DFS huchukua faharasa ya kisanduku i na j na faharasa ya herufi katika neno la kuingiza ambalo tunatafuta k.Kesi za msingi ni:- Ikiwa faharasa za kisanduku i au j ziko nje ya mipaka, au ubaoij herufi hailingani na nenok, rudisha sivyo.- Ikiwa k index ya herufi ya sasa ni sawa na neno.length - 1, tunapata neno kwenye gridi ya taifa, kwa hivyo rudi kweli.Kwa kila seli, tunaendesha kazi ya DFS na vigezo vya pembejeo vilivyotolewa. Ikiwa DFS itarudi kweli imepata neno, chaguo la kukokotoa litarudi kuwa kweli. 