leetcode_221문항-Maximal Square(동적 기획)
3109 단어 LeetCode
Total Accepted: 6373 Total Submissions: 31927 My Submissions
Question
Solution
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
Credits:Special thanks to @Freezen for adding this problem and creating all test cases.
Hide Tags
Dynamic Programming
Have you met this question in a real interview?
Yes
No
Discuss
dp[x][y] = min(dp[x - 1][y - 1], dp[x][y - 1], dp[x - 1][y]) + 1
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int maximalSquare(vector<vector<char>>& matrix)
{
if(matrix.empty())
return 0;
int m=matrix.size();
int n=matrix[0].size();
vector<vector<int>> ma;
vector<int> ve;
for(int i=0;i<n;i++)
ve.push_back(0);
for(int i=0;i<m;i++)
{
ma.push_back(ve);
}
int re=0;
for(int i=0;i<n;i++)
{
if(matrix[0][i]=='1')
{
ma[0][i]=1;
re=1;
}
else
ma[0][i]=0;
}
for(int j=0;j<m;j++)
{
if(matrix[j][0]=='1')
{
ma[j][0]=1;
re=1;
}
else
ma[j][0]=0;
}
if(m==1)
return re;
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
if(matrix[i][j]=='1')
{
ma[i][j]=min(min(ma[i][j-1],ma[i-1][j]),ma[i-1][j-1])+1;
if(re<ma[i][j])
re=ma[i][j];
}
else
ma[i][j]=0;
}
}
return re*re;
}
int main()
{
vector<vector<char>> matrix;
vector<char> ma;
ma.push_back('0');
matrix.push_back(ma);
cout<<maximalSquare(matrix)<<endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
