b027: 小綠人的城堡
森林裡住了一群小綠人，因為受到藍色巨人的攻擊，所以他們決定要建造一座城堡。不過由於樹是他們生活環境必須的，所以他們只會選擇沒有樹的地方，而且城堡一定要蓋成正方形，請你幫他們找出可以蓋最大城堡的地方有多大。
輸入說明：
第一行有兩個正整數 H、W (1<=H、W<=100)，代表這塊土地的大小，接下來有 H 行，每行有 W 個 0 或 1 的數字，1 代表樹，0 則是可以蓋城堡的地方。
輸出說明：
請你找出上述土地中，全部由 0 組合成的正方形區域的最大面積有多少。
範例輸入：
3 4 0 0 1 0 1 0 0 0 0 0 0 1
範例輸出 ：
4
題目：
Given a 2D binary matrix
filled with 0's and 1's, find the largest square containing all 1's and return
its area.
For example, given the
following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
動態規劃
當我們判斷以某個點為正方形右下角時最大的正方形時，那它的上方，左方和左上方三個點也一定是某個正方形的右下角，否則該點為右下角的正方形最大就是它自己了。這是定性的判斷，那具體的最大正方形邊長呢？我們知道，該點為右下角的正方形的最大邊長，最多比它的上方，左方和左上方為右下角的正方形的邊長多1，最好的情況是是它的上方，左方和左上方為右下角的正方形的大小都一樣的，這樣加上該點就可以構成一個更大的正方形。但如果它的上方，左方和左上方為右下角的正方形的大小不一樣，合起來就會缺了某個角落，這時候只能取那三個正方形中最小的正方形的邊長加1了。假設dpi表示以i,j為右下角的正方形的最大邊長，則有
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
當然，如果這個點在原矩陣中本身就是0的話，那dpi肯定就是0了。
public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int max = 0;
int[][] dp = new int[m][n];
// 第一列賦值
for(int i = 0; i < m; i++){
dp[i][0] = matrix[i][0] - '0';
max = Math.max(max, dp[i][0]);
}
// 第一行賦值
for(int i = 0; i < n; i++){
dp[0][i] = matrix[0][i] - '0';
max = Math.max(max, dp[0][i]);
}
// 遞推
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = matrix[i][j] == '1' ? Math.min(dp[i-1][j-1],
Math.min(dp[i-1][j], dp[i][j-1])) + 1 : 0;
max = Math.max(max, dp[i][j]);
}
}
return max * max;
}
}
Question - post
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Example 1:
["10100",
"10111",
"11111",
"10010"
Return
6Example 2:
["101111",
"011111",
"011011",
"001111",
"101100"]
Return
8Example 3:
["1111",
"1111",
"1111"
Return
12Solution - code
Given a navigation that goes through the elements from the left-top one to the right-bottom one, we need to know at a specific element, what is the certain information that defines the maximal rectangle from the previous left or top elements. In terms of this mentor model, the problem is essentially a Dynamic Programming (wiki) problem. So the point is ...
- To define the smallest subproblem so that we could break the problem into smallest subproblems.
- Use memorization to store the results of the solved subproblems.
The smallest subproblem is that: For every row of the array, it is a "Largest Rectangle in Histogram" problem.
Step 1 - Subproblem "Largest Rectangle in Histogram"
For every element, we go through the elements behind. The code is like,
def maximalRectangleInHistogram(self, histogram):
"""
Calculate the maximum rectangle area in terms of a given histogram.
(Ver.1)
:param histogram: List[int]
:return: int
"""
maxArea = 0
size = len(histogram)
# For every bar in the histogram, we go through the previous bars.
for i in range(size):
# Take current height as the minimum height.
minH = histogram[i]
for j in reversed(range(i)):
# Return if it meets zero.
if histogram[j] == 0:
break
# Find the minimum height at the moment.
minH = min(minH, histogram[j])
# Calculate the area at the moment.
area = minH * (i - j + 1)
# Find out the maximum area.
maxArea = max(maxArea, area)
return maxArea
Can we do this better? Sure! We could try to use
stack coming with certain rules to improve the back navigation. So the problem becomes when to push and when to pop. I still don't figure out the way to improve the previous version and it's the code from the internet:def maximalRectangleInHistogram(self, histogram):
"""
Calculate the maximum rectangle area in terms of a given histogram.
(Ver.2)
:param histogram: List[int]
:return: int
"""
# Stack for storing the index.
posStack = []
i = 0
maxArea = 0
while i < len(histogram):
if len(posStack) == 0 or histogram[i] > histogram[posStack[-1]]:
# Advance the index when either the stack is empty or the
# current height is greater than the top one of the stack.
posStack.append(i)
i += 1
else:
curr = posStack.pop()
width = i if len(posStack) == 0\
else i - posStack[-1] - 1
maxArea = max(maxArea, width * histogram[curr])
# Clean the stack.
while posStack:
curr = posStack.pop()
width = i if len(posStack) == 0\
else len(histogram) - posStack[-1] - 1
maxArea = max(maxArea, width * histogram[curr])
return maxArea
Step 2 - Break The Problem Into Subproblems
For every row of the array, it is a "Largest Rectangle in Histogram" problem and the code is like,
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
maxArea = 0
maxRow = len(matrix)
maxCol = len(matrix[0])
# For every row in the given 2D matrix, it is a "Largest Rectangle in
# Histogram" problem, which is the subproblem.
lookupTable = [0 for _ in range(maxCol)]
for row in range(maxRow):
for col in range(maxCol):
# If it is "1"
if int(matrix[row][col]) > 0:
# Accumulate the column if if's 1's.
lookupTable[col] += int(matrix[row][col])
else:
# Clean the column if it's 0's.
lookupTable[col] = 0
# Calculate the maximum area.
maxArea = max(maxArea,
self.maximalRectangleInHistogram(lookupTable))
return maxArea
"""
題目：
Given a 2D binary matrix filled with 0's and 1's,
find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
動態規劃
當我們判斷以某個點為正方形右下角時最大的正方形時，
那它的上方，左方和左上方三個點也一定是某個正方形的右下角
，否則該點為右下角的正方形最大就是它自己了。
這是定性的判斷，那具體的最大正方形邊長呢？
我們知道，該點為右下角的正方形的最大邊長，
最多比它的上方，左方和左上方為右下角的正方形的邊長多1
，最好的情況是是它的上方，左方和左上方為右下角的正方形的大小都一樣的
，這樣加上該點就可以構成一個更大的正方形。
但如果它的上方，左方和左上方為右下角的正方形的大小不一樣
，合起來就會缺了某個角落，這時候只能取那三個正方形中
最小的正方形的邊長加1了。
假設dpi表示以i,j為右下角的正方形的最大邊長，則有
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
當然，如果這個點在原矩陣中本身就是0的話，那dpi肯定就是0了。
"""
def printMaxSubSquare(M):
R = len(M) # no. of rows in M[][]
C = len(M[0]) # no. of columns in M[][]
S = [[0 for k in range(C)] for l in range(R)]
# here we have set the first row and column of S[][]
# Construct other entries
for i in range(1, R):
for j in range(1, C):
if (M[i][j] == 1):
S[i][j] = min(S[i][j-1], S[i-1][j],
S[i-1][j-1]) + 1
else:
S[i][j] = 0
# Find the maximum entry and
# indices of maximum entry in S[][]
max_of_s = S[0][0]
max_i = 0
max_j = 0
for i in range(R):
for j in range(C):
if (max_of_s < S[i][j]):
max_of_s = S[i][j]
max_i = i
max_j = j
print("Maximum size sub-matrix is: ")
for i in range(max_i, max_i - max_of_s, -1):
for j in range(max_j, max_j - max_of_s, -1):
print (M[i][j], end = " ")
print("")
global max_width
max_width= max_i
# Driver Program
max_width=0
M = [[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 0],
[1, 1, 1, 1, 1],
[0, 0, 0, 0, 0]]
printMaxSubSquare(M)
# This code is contributed by Soumen Ghosh
M = [[1,0,1,1,1,1],
[0,1,1,1,1,1],
[0,1,1,0,1,1],
[0,0,1,1,1,1],
[1,0,1,1,0,0]]
printMaxSubSquare(M)
# This code is contributed by Soumen Ghosh
====================== RESTART: F:/Python_APSC/b027.py ======================
Maximum size sub-matrix is:
1 1 1
1 1 1
1 1 1
Maximum size sub-matrix is:
1 1
1 1
>>>
沒有留言:
張貼留言