<prompt> Imepewa n n matrix gridi ya 0 na 1 pekee. Tunataka kuwakilisha gridi kwa kutumia Mti wa Quad.Rudisha _mzizi wa Mti wa Mrefu unaowakilisha_ gridi.Quad-Tree ni muundo wa data wa mti ambapo kila nodi ya ndani ina watoto wanne haswa. Kwa kuongezea, kila nodi ina sifa mbili: val: Kweli ikiwa nodi inawakilisha gridi ya 1 au Sivyo ikiwa nodi inawakilisha gridi ya 0. Ona kwamba unaweza kuagiza val kuwa Kweli au Si kweli wakati isLeaf ni Uongo, na zote mbili zinakubaliwa kwenye jibu. isLeaf: Kweli ikiwa nodi ni nodi ya jani kwenye mti au Si kweli ikiwa nodi hiyo ina watoto wanne.nodi ya darasa val ya boolean ya umma; boolean ya umma isLeaf; Njia ya umma juuKushoto; Nodi ya umma juuKulia; Njia ya umma chiniKushoto; Nodi ya umma chiniKulia;Tunaweza kuunda Quad-Tree kutoka eneo la pande mbili kwa kutumia hatua zifuatazo:1. Ikiwa gridi ya sasa ina thamani sawa yaani 1 zote au 0 zote weka isLeaf Kweli na uweke val kwa thamani ya gridi ya taifa na uweke watoto wanne kuwa Batili na usimamishe.2. Ikiwa gridi ya sasa ina thamani tofauti, weka isLeaf kuwa Sivyo na uweke val kwa thamani yoyote na ugawanye gridi ya sasa katika gridi ndogo nne kama inavyoonyeshwa kwenye picha.3. Marudio kwa kila mtoto aliye na gridi ndogo inayofaa.Ikiwa ungependa kujua zaidi kuhusu Mti wa Quad, unaweza kurejelea wiki wa Miti Mitatu:Huna haja ya kusoma sehemu hii ili kutatua tatizo. Hii ni ikiwa tu unataka kuelewa umbizo la towe hapa. Toleo linawakilisha umbizo la kufululiza la Mti wa Quad kwa kutumia kipenyo cha mpangilio wa kiwango, ambapo null inaashiria kimaliza njia ambapo hakuna nodi hapa chini.Ni sawa na usanifu wa mti wa binary. Tofauti pekee ni kwamba nodi inawakilishwa kama orodha isLeaf, val.Ikiwa thamani ya isLeaf au val ni Kweli tunaiwakilisha kama 1 katika orodha isLeaf, val na ikiwa thamani ya isLeaf au val ni Siyo tunaiwakilisha kama 0.Mfano wa 1:Ingizo: gridi 0,1,1,0Pato: 0,1,1,0,1,1,1,1,1,0Maelezo: Maelezo ya mfano huu yameonyeshwa hapa chini:Kumbuka kwamba 0 inawakilisha Uongo na 1 inawakilisha Kweli kwenye picha inayowakilisha Mti wa Mrefu. Mfano wa 2:Ingizo: gridi 1,1,1,0,0,0,0,1,1,1,1,0,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0, 1,1,1,1,0,0,0,0Pato: 0,1,1,1,0,1,1,1,1,0,null, null,null,null,1,0,1,0,1,1,1,1Maelezo: Thamani zote kwenye gridi ya taifa hazifanani. Tunagawanya gridi ya taifa katika gridi ndogo nne.JuuKushoto, chiniKushoto na chiniKulia kila moja ina thamani sawa.TopRight ina thamani tofauti kwa hivyo tunaigawanya katika gridi ndogo 4 ambapo kila moja ina thamani sawa.Ufafanuzi unaonyeshwa kwenye picha hapa chini: Vikwazo: n grid.length gridii.length n 2x ambapo 0 x 6  <response>: chatunodi ya darasa: def __init__binafsi, val, isLeaf, topLeft, top Right, bottomLeft, bottomKulia: self.val val self.isLeaf isLeaf self.topLeft topLeft self.topRight topRight self.bottomLeft bottomLeft self.bottomRight chiniKuliadef kujenga gridi, safu, safu, saizi: ikiwa ukubwa 1: Return Nodigridisafucol 1, Kweli, Hakuna, Hakuna, Hakuna, Hakuna nusu ukubwa 2 topLeft kujenga gridi, safu, safu, nusu topRight kujenga gridi ya taifa, safu mlalo, safu nusu, nusu bottomLeft kujenga gridi, safu nusu, col, nusu bottomRight kujenga gridi ya taifa, safu nusu, safu nusu, nusu ikiwa topLeft.isLeaf na topRight.isLeaf na bottomLeft.isLeaf na bottomRight.isLeaf na topLeft.val topRight.val na topLeft.val bottomLeft.val na topLeft.val bottomRight.val: rudi juuKushoto Njia ya kurudisha Siyo kweli, Si kweli, juuKushoto, juuKulia, chiniKushoto, chiniKuliadef constructgridi: kurejesha ujenzi gridi, 0, 0, lengridimaelezoAlgorithm hukagua kwanza ikiwa saizi ya gridi ya taifa ni 1, ambapo itarejesha Nodi mpya yenye thamani ya gridi ya taifa na kuweka sifa ya isLeaf kuwa Kweli. Vinginevyo, algoriti hukokotoa nusu ya ukubwa wa tumbo na kuunda sehemu ya juuKushoto, juuKulia, chiniKushoto na chiniKulia kwa kujirudia. Ikiwa zote ni nodi za majani na thamani zake ni sawa, nodi ya sasa inachukua thamani ya topLeft na sifa ya isLeaf imewekwa kuwa Kweli; vinginevyo, inaendelea kujenga muundo wa quad-tree kwa kila gridi ndogo.Kanuni ya jumla inajirudia na inatekeleza mbinu ya kugawanya-na-kushinda ili kujenga muundo wa miti minne. 