tco pre bin new find fin bsp char div
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest square containing only 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.
- public class Solution {
- public int MaximalSquare(char[,] matrix) {
- int rows = matrix.GetLength(0), cols = matrix.GetLength(1);
- var dp = new int[rows + 1, cols + 1];
- int max = 0;
- for (int i = 0; i < rows; i++)
- {
- for (int j = 0; j < cols; j++)
- {
- if (matrix[i, j] == ‘0‘)
- {
- dp[i + 1, j + 1] = 0;
- }
- else
- {
- dp[i + 1, j + 1] = Math.Min(Math.Min(dp[i, j + 1], dp[i + 1, j]), dp[i, j]) + 1;
- max = Math.Max(max, dp[i + 1, j + 1]);
- }
- }
- }
- return max * max;
- }
- }
Leetcode 221: Maximal Square
来源: http://www.bubuko.com/infodetail-2414140.html