Leetcode176: Maximal Square

本文主要是介绍Leetcode176: Maximal Square，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

用动态规划的思想，令res[i][j]表示以i,j为右下角坐标的正方形的最大边长，则 res[i][j] = min(min(res[i-1][j], res[i][j-1]), res[i-1][j-1])+1

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int m = matrix.size();if(m==0)return 0;int n = matrix[0].size();if(n==0)return 0;vector<vector<int>> res(m, vector<int>(n));int maxlen=0;for(int i = 0; i < m; i++){if(matrix[i][0] == '1'){res[i][0] = 1;maxlen = 1;}}for(int i = 0; i < n; i++){if(matrix[0][i] == '1'){res[0][i] = 1;maxlen = 1;}}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][j] == '1'){res[i][j] = min(min(res[i-1][j], res[i][j-1]), res[i-1][j-1])+1;maxlen = max(maxlen, res[i][j]);}else{res[i][j] = 0;}}}return maxlen*maxlen;}
};

这篇关于Leetcode176: Maximal Square的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---