[백준 4095] 최대 정사각형 (C++)

4095번: 최대 정사각형

 

반례:

1 1

0

 

answer : 0

 

 

1 2

0

 

answer : 0

 

2 1

1

2

 

answer : 1

 

 

 

dp[r][c] : r,c를 오른쪽 아래 꼭짓점으로 가지는 정방 행렬의 크기.

 

 

현재 위치의 왼쪽, 위, 왼쪽 위 대각선의 dp값 중에서 가장 작은 값을 +1 한게 현재 위치의 dp값이 된다.

dp[r][c] = min(dp[r-1][c-1], min(dp[r][c-1], dp[r-1][c])) + 1;

 

 

 

❗️주의사항 : answer를 반드시 초기화 하자

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>

typedef long long ll;
// typedef pair<int, int> pii;

using namespace std;

int N, M, answer;
int Map[1001][1001];
int dp[1001][1001];

void solve(){
    for(int r = 2; r <= N; r++){
        for(int c = 2; c <= M; c++){
            if(Map[r][c]){
                dp[r][c] = min(dp[r-1][c-1], min(dp[r][c-1], dp[r-1][c])) + 1;
                answer = max(answer, dp[r][c]);
            }
        }
    }
    cout << answer << "\n";
}

int main(){
    while(true){
        memset(dp, 0, sizeof(dp));
        
        answer = 0;
        cin >> N >> M;
        if(!N && !M) break;
        
        for(int r = 1; r <= N; r++){
            for(int c = 1; c <= M; c++){
                cin >> Map[r][c];
                dp[r][c] = Map[r][c];
                answer = max(answer, dp[r][c]);
            }
        }
        solve();
    }
    
    return 0;
}​