最大可能的方形油漆刷畫一個畫布

Question

有一個問題，在採訪中問我。問題陳述如下： - 有一位畫家，並有一個NxM網格畫布。畫家有任何正方形大小，即任何nxn大小的油漆刷。畫家知道他需要繪製哪些網格，哪些必須留白（Painter意圖繪製黃色和白色繪畫）。所以任何網格塊都應該是黃色或白色。除此之外，還有一些不關心塊被塗上黃色或留下白色。現在，我們不得不提出一種算法來最大限度地減少畫家的工作量，並告訴可能用於繪製畫布的最大可能的nxn畫筆。 實施例： -

Sample canvas of 8x4 Grid. Yellow color block has to paint,white color block has to left white and blue color block are don't care blocks can either be white or painted

按照實施例以上，2×2刷子的最大尺寸可以是使用成功地畫在畫布上。

我提出了使用蠻力的解決方案，即檢查每種顏色，並決定哪些將覆蓋最大可能的方形筆刷。檢視器不滿意此解決方案。 我想問： - 1）做這個問題的最好方法是什麼？ 2）可以使用動態編程概念來解決這個問題。

Answer 1

讓我們用A來表示min(N,M)。這個問題可以通過簡單的解決方案在O(A^2 N M Log A)中解決。還有一個複雜的解決方案O(N M Log A)。

重要的觀察

如果有可能轉色董事會K x K刷，那麼它絕對有可能轉色板與任何較小的畫筆。因此我們可以通過二分查找來解決問題。

解決方案刮開

int left = 1, right = min(N, M) + 1; 
while (right - left > 1) { 
    int middle = (left + right)/2; 
    if (PossibleToColor(middle)) { 
    left = middle; 
    } else { 
    right = middle; 
    } 
} 
OutputAnswer(left); 

簡單的解決方案和提示覆雜的解決方案

唯一棘手的是仍是如何實現PossibleToColor(int K)事情。

簡單的解決方案只是遍歷畫筆的每個可能的位置。如果在這個位置刷子下沒有白色細胞，我們需要畫刷子下的所有細胞。在所有職位被檢查後，我們需要檢查每個黃色單元是否被塗漆。 PossibleToColor的每個呼叫將在O(K^2NM)中運行，因此總運行時間爲O(A^2 N M Log A)。

在複雜的解決方案中，您需要構建一個整數矩陣NxM。它的元素是相等的，當且僅當畫布的相應像素是白色的，否則它等於零。然後你需要遍歷所有的筆刷位置，並檢查我們是否可以在這裏放置筆刷（如果是正方形，則需要計算子平方的和，然後不能）。要快速執行此操作，需要使用數據結構來計算O(1)中整數矩陣的子矩形中的數字總和。可以在O(NM)中構建這樣的數據結構。

然後在找到畫筆的所有可能位置後，您需要構建一個更多的整數矩陣NxM。當且僅當此元素中有左上角的刷子位置時，它的元素等於1，否則它等於零。然後你需要遍歷每個黃色像素，並檢查它是否會被畫刷至少一個可能的位置。檢查您是否需要在描述的矩陣的子矩形中計算總和。你需要用相同的數據結構來完成。

爲整數矩陣A所描述的數據結構僅僅是一個矩陣S，使得

S[i][j] =總和的A[p][q]使得1 <= p <= i，1 <= p <= j

它可以用簡單的動態編程來計算在O(NM)。當您計算它時，子矩形i1 <= i <= i2, j1 <= j <= j2中的總和可以計算爲

S[i2][j2] - S[i2][j1 - 1] - S[i1 - 1][j2] + S[i1 - 1][j1 - 1]。