Leetcode 221. Maximal Square

triplebee

发布于 2018-01-12 14:46:02

6150

发布于 2018-01-12 14:46:02

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础计算机视觉与深度学习基础

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:

Return 4.

找出矩阵中最大的由1组成的正方形的大小。

dp[i][j]表示以这个点为右下角的最大正方形的边长。

如果一个点为0，那么这个点不能作为正方形的右下角，所以跳过.

一个点是否可以并入正方形取决于左边、上边、左上边格子的取值，取他们的最小值。

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-03-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除

area