题干
力扣-最大正方形
题干详见 LeetCode ,图片过多不在此赘述。
暴力
思路
暴力算嘛,计算每一个最大的正方形的边长并存储,遍历一轮。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| public int MaximalSquare(char[][] matrix) { var maxSide = 0;
if (matrix is null || matrix.Length == 0 || matrix[0].Length == 0) return 0;
var rows = matrix.Length; var columns = matrix[0].Length;
for (var i = 0; i < rows; i++) { for (var j = 0; j < columns; j++) { if (matrix[i][j] == '1') { maxSide = maxSide > 1 ? maxSide : 1;
var currentMaxSide = rows - i > columns - j ? columns - j : rows - i; for (var k = 1; k < currentMaxSide; k++) { var flag = true; if (matrix[i + k][j + k] == '0') break;
for (var m = 0; m < k; m++) { if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') { flag = false; break; } }
if (flag) { maxSide = maxSide > k + 1 ? maxSide : k + 1; } else { break; } } } } }
return maxSide * maxSide; }
|