面试题 17.23. 最大黑方阵

本文主要是介绍面试题 17.23. 最大黑方阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

题目链接

找到最长的边都是0的正方形，如果长度想等，尽可能起点小

思路

• 暴力+剪枝
• dp ，预处理每个点的上下左右最长长度，再去枚举长度去转移

代码

// 力大飞砖
class Solution {
public:vector<int> findSquare(vector<vector<int>>& matrix) {int x_ans = 0;int y_ans = 0;int length_ans = -1;for (int x = 0; x < matrix.size(); x++){for (int y = 0; y < matrix[x].size(); y++){if (matrix[x][y] == 1)continue;int max_tmp = min(matrix.size() - x, matrix[y].size() - y);if (max_tmp <= length_ans)continue;for (int z = max_tmp; z > 0; z--){if (z <= length_ans)break;if (judge_invalid(matrix, x, y, z) && z > length_ans){length_ans = z;x_ans = x;y_ans = y;}}}}return ~length_ans ? vector<int> {x_ans, y_ans, length_ans} : vector<int> {};}bool judge_invalid(vector<vector<int>>& matrix, int x, int y, int length){for (int i = 0; i < length; i++)if (matrix[x][y + i] || matrix[x + i][y] || matrix[x + i][y + length - 1] || matrix[x + length -1][y + i])return false;return true;}
};

这篇关于面试题 17.23. 最大黑方阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---