<prompt> Kwa kuzingatia ubao wa m x n ambapo kila seli ni meli ya kivita X au tupu., rudisha _idadi ya meli za kivita kwenye_ ubao.Meli za kivita zinaweza kuwekwa tu kwa mlalo au wima kwenye ubao. Kwa maneno mengine, zinaweza tu kufanywa kwa umbo la 1 x k 1 safu wima, k safu wima au k x 1 k safu, 1 safu, ambapo k inaweza kuwa. ya ukubwa wowote. Angalau seli moja ya mlalo au wima hutenganisha kati ya meli mbili za kivita yaani, hakuna meli za kivita zilizo karibu.Mfano wa 1:Ingizo: ubao X , . , . , X , . , . , . , X , . , . , . , X Pato: 2Mfano wa 2:Ingizo: ubao . Pato: 0Vikwazo: m ubao.urefu n ubaoi.urefu 1 m, n 200 ubaoij ama ni . au X.Fuata: Je, unaweza kuifanya kwa pasi moja, ukitumia kumbukumbu ya ziada ya O1 pekee na bila kurekebisha thamani ubao?  <response>: chatudef countBattleshipsbodi: hesabu 0 kwa mimi katika anuwailenbodi: kwa j katika safulenubao0: ikiwa ubaoij X na i 0 au ubaoi - 1j . na j 0 au ubaoij - 1 .: hesabu 1 hesabu ya kurudimaelezoAlgorithm inarudia juu ya kila seli katika ubao uliyopewa. Ikiwa seli ya sasa ni X meli ya kivita na seli zote zilizo juu yake ikiwa ipo na seli iliyo upande wake wa kushoto ikiwa ipo si X, inamaanisha tumepata meli mpya ya kivita. Tunaongeza idadi ya meli za kivita katika kesi hii. Mwishowe, tunarudisha hesabu ya jumla ya meli za kivita zilizopatikana.Sababu ya sisi kuangalia seli za juu na kushoto pekee ni kwamba tunataka tu kuhesabu mwanzo wa meli ya kivita, na sio kuhesabu meli sawa ya kivita mara kadhaa. Kwa kuwa meli za kivita zinaweza kuwa katika mwelekeo wa mlalo au wima, kuangalia seli za kushoto na za juu huhakikisha kwamba tunahesabu kila meli ya kivita mara moja pekee. 