1905 年。計算子島嶼
難度:中
主題:陣列、深度優先搜尋、廣度優先搜尋、並集查找、矩陣
給定兩個 m x n 二進位矩陣 grid1 和 grid2,其中僅包含 0(代表水)和 1(代表土地)。 島嶼是一組由1連接的4向(水平或垂直)。網格之外的任何細胞都被視為水細胞。
如果grid1 中的一個島包含所有構成grid2 中這個島的單元格,則grid2 中的島被視為子島 .
返回grid2中被視為子島的數量個島嶼。
範例1:
範例2:
約束:
提示:
解:
我們將使用深度優先搜尋 (DFS) 方法來探索 grid2 中的島嶼,並檢查每個島嶼是否完全包含在 grid1 中的相應島嶼中。以下是我們如何實作該解決方案:
讓我們用 PHP 實作這個解:1905。數一下子島嶼
<?php /** * @param $grid1 * @param $grid2 * @return int */ function countSubIslands($grid1, $grid2) { ... ... ... /** * go to ./solution.php */ } /** * @param $grid1 * @param $grid2 * @param $i * @param $j * @param $m * @param $n * @return int|true */ function dfs(&$grid1, &$grid2, $i, $j, $m, $n) { ... ... ... /** * go to ./solution.php */ } // Example usage: // Example 1 $grid1 = [ [1,1,1,0,0], [0,1,1,1,1], [0,0,0,0,0], [1,0,0,0,0], [1,1,0,1,1] ]; $grid2 = [ [1,1,1,0,0], [0,0,1,1,1], [0,1,0,0,0], [1,0,1,1,0], [0,1,0,1,0] ]; echo countSubIslands($grid1, $grid2); // Output: 3 // Example 2 $grid1 = [ [1,0,1,0,1], [1,1,1,1,1], [0,0,0,0,0], [1,1,1,1,1], [1,0,1,0,1] ]; $grid2 = [ [0,0,0,0,0], [1,1,1,1,1], [0,1,0,1,0], [0,1,0,1,0], [1,0,0,0,1] ]; echo countSubIslands($grid1, $grid2); // Output: 2 ?>
時間複雜度為 (O(m × n)),其中 m 是行數,n 是列數。這是因為我們可能會訪問每個單元格一次。
該解決方案應該在給定的限制內有效地工作。
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
以上是計數子島的詳細內容。更多資訊請關注PHP中文網其他相關文章!