[백준] 가장 큰 정사각형 - 1915번

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

 

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
 
typedef struct {
    int x;
    int y;
}movepos;
 
int main(int argc, char* argv[]) {
    int n, m;
    char** map;
    int** dp;
    int answer=0;
    movepos move[3] = { {-1,0},{-1,-1},{0,-1} };
    
    scanf("%d %d", &n, &m);
 
    map = new char*[n];
    dp = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new char[m+1];
        dp[i] = new int[m];
        scanf("%s", map[i]);
        memset(dp[i], 0, sizeof(int) * m);
        
    }
 
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if (map[x][y] == '0') {
                dp[x][y] = 0;
                continue;
            }
            int min;
            int posx, posy;
            bool one=false;
            bool end=false;
 
            for (int i = 0; i < 3; i++) {
                posx = x + move[i].x;
                posy = y + move[i].y;
                if (posx < 0 || posy < 0 || dp[posx][posy] == 0) {
                    dp[x][y] = 1;
                    end = true;
                    break;
                }
                else if (dp[posx][posy] == 1) {
                    one = true;
                    continue;
                }
 
                if (i == 0) {
                    min = dp[posx][posy];
                }
                else if(min>dp[posx][posy]) {
                    min = dp[posx][posy];
                }
            }
 
            if (end == false) {
                if (one) {
                    dp[x][y] = 2;
                }
                else{
                    dp[x][y] = min + 1;
                }
            }
 
            if (dp[x][y] > answer)
                answer = dp[x][y];
        }
    }
    printf("%d", answer*answer);
 
    for (int i = 0; i < n; i++) {
        delete[] map[i];
        delete[] dp[i];
    }
 
    delete[] map;
    delete[] dp;
 
    return 0;
}