計算網格中不受保護的單元格

2257。計算網格中不受保護的單元

難度：中

主題：陣列、矩陣、模擬

給定兩個整數 m 和 n，表示 0 索引 m x n 網格。您還獲得兩個2D 整數數組Guards 和Walls，其中Guards[i] = [row_i, col_i] 和Walls[j] = [row_j, col_j] 代表第i^th個守衛的位置，分別是第 j 面牆。

警衛可以從其位置開始看到四個基本方向（北、東、南或西）的每個牢房，除非被牆壁或其他警衛阻擋。如果有至少一名守衛可以看到某個牢房，則該牢房受到看守。

回傳不受保護的未佔用儲存格的數量。

範例1：

• 輸入： m = 4, n = 6, 守衛= [[0,0],[1,1],[2,3]], 牆壁= [[0,1],[2, 2],[1,4]]
• 輸出： 7
• 說明：上圖中，受保護和不受保護的儲存格分別以紅色和綠色顯示。
  • 總共有 7 個無人看守的儲存格，所以我們回傳 7 個。

範例2：

• 輸入： m = 3, n = 3, 守衛= [[1,1]], 牆壁= [[0,1],[1,0],[2,1],[1, 2]]
• 輸出： 4
• 說明：未受保護的儲存格在上圖中以綠色顯示。
  • 總共有 4 個無人看守的儲存格，所以我們回傳 4 個。

約束：

• 1 5
• 2 5
• 1 4
• 2
• 守衛[i].length == 牆[j].length == 2
• 0 i，行_j
• 0 i, col_j
• 守衛和牆壁中的所有位置都是獨特的。

提示：

1. 建立一個二維陣列來表示網格。你能標記出守衛可以看到的方塊嗎？
2. 迭代守衛，並針對 4 個方向中的每一個，推進目前圖塊並標記該圖塊。什麼時候該停止前進？

解：

我們需要標記至少由一名守衛看守的單元格。守衛可以看到四個基本方向（北、南、東、西），但他們的視線被牆壁阻擋。我們可以模擬這個過程並計算不受保護的單元格的數量。

方法：

1. 建立一個網格：我們可以將網格表示為一個二維數組，其中每個單元格可以是牆、守衛或空。
2. 標記被看守的單元格：對於每個守衛，在四個方向（北、南、東、西）迭代並標記它能看到的所有單元格，當遇到牆壁或另一個守衛時停止。
3. 計算不受看守的單元格：標記受看守的單元格後，計算有多少個單元格不受看守且不是牆。

步驟：

1. 網格初始化：建立一個二維陣列來表示網格。當我們迭代時，用牆壁、守衛和守衛區域標記單元格。

2. 模擬警衛覆蓋範圍:

   • 守衛可以看到四個方向（北、南、東、西）。
   • 標記每個守衛所看守的牢房，直到遇到牆壁或另一個守衛。

3. 計算不受看守的單元格：處理完所有守衛後，對既不是牆壁、守衛、也沒有看守的單元格進行計數。

讓我們用 PHP 實作這個解：2257。計算網格中不受保護的單元格

<?php
/**
 * @param Integer $m
 * @param Integer $n
 * @param Integer[][] $guards
 * @param Integer[][] $walls
 * @return Integer
 */
function countUnguarded($m, $n, $guards, $walls) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$m = 4;
$n = 6;
$guards = [[0, 0], [1, 1], [2, 3]];
$walls = [[0, 1], [2, 2], [1, 4]];
echo countUnguarded($m, $n, $guards, $walls); // Output: 7

// Example 2
$m = 3;
$n = 3;
$guards = [[1, 1]];
$walls = [[0, 1], [1, 0], [2, 1], [1, 2]];
echo countUnguarded($m, $n, $guards, $walls); // Output: 4
?>

解釋：

1. 初始化:

   • 對於空白單元格，網格初始化為 0。牆壁和守衛都標有獨特的常量。

2. 守衛模擬：

   • 對於每個守衛，模擬所有四個方向的移動，將單元標記為受守衛，直到撞到牆壁或另一個守衛。

3. 計算不受保護的細胞:

   • 處理完所有守衛後，迭代網格並計算仍標記為 0 的單元格。

表現：

• 時間複雜度：O(m x n g x d)，其中gd 是守衛的數量，d
是每個守衛可以移動的方向上的單元格數量旅行。
• 空間複雜度：O(m x n)
對於網格。

時間複雜度：

• 網格初始化：_O(m * n)，其中_m和n
和
• nn
• nn

n 是網格的尺寸。

標記警衛視野

：每位警衛最多檢查行或列在四個方向上的長度。所以，對於每個守衛，它是

• O(m n)
• 。

計算不受保護的細胞：

O(m * n)

.

因此，整體複雜度為

O(m * n)
• ，在給定問題限制的情況下，這是有效的。
邊緣情況：
• 如果沒有守衛或牆壁存在，整個網格將無人守衛。

如果所有單元格都有防護或有牆，則結果將為 0 個未防護單元格。 聯絡連結 如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！ 如果您想要更多類似的有用內容，請隨時關注我： 領英 GitHub

以上是計算網格中不受保護的單元格的詳細內容。更多資訊請關注PHP中文網其他相關文章！