[BOJ] 1028 다이아몬드 광산

https://www.acmicpc.net/problem/1028

1028번: 다이아몬드 광산

쉬워보여서 도전했는데 플레는 역시 플레 문제... 다른 분의 코드를 참조하여 풀었지만 다행히 방식이 똑같았다.

위에 꼭짓점이 i,j일 때 각 선분을 위와 같이 정의하였다

leftdown에는 왼쪽 밑, rightdown에는 오른쪽 위, leftup에는 왼쪽 위, rightup에는 오른쪽 위로 얼마나 긴 선분이 존재하는지 저장하였다. 그리고 각 점 ( i , j )를 방문하면서 왼쪽 밑으로 가는 선분의 길이(leftdown)와 오른쪽 밑으로 가는 선분의 길이(rightdown) 중 작은 값 k를 골라 1부터 k까지 반복문을 돈다. (i,2*(k-1)) 에서 오른쪽 위로 가는 선분의 길이(rightup), 왼쪽 위로 가는 선분의 길이(leftup)의 길이가 k보다 클 때 비로소 4개의 선분이 모두 이어져 크기가 k인 다이아가 존재 할 수 있게 된다.

 

코드

#include <iostream>
using namespace std;

int info[751][751];
int leftdown[752][752];
int rightdown[752][752];
int leftup[752][752];
int rightup[752][752];
int R,C;
void cal(){
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            if(info[i][j]){
                leftup[i][j]=leftup[i-1][j-1]+1;
                rightup[i][j]=rightup[i-1][j+1]+1;
            }
        }
    }
    for(int i=R;i>=1;i--){
        for(int j=C;j>=1;j--){
            if(info[i][j]){
                leftdown[i][j]=leftdown[i+1][j-1]+1;
                rightdown[i][j]=rightdown[i+1][j+1]+1;
            }
        }
    }
}
int find_ans(){
    int ans=0;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            int m=min(leftdown[i][j],rightdown[i][j]);
            for(int k=1;k<=m;k++){
                int point=i+2*(k-1);
                if(point<=R&&info[point][j]&&leftup[point][j]>=k&&rightup[point][j]>=k){
                    ans=max(ans,k);
                }
            }
        }
    }
    return ans;
}

int main(){
    cin>>R>>C;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            scanf("%1d",&info[i][j]);
        }
    }
    cal();
    cout<<find_ans();
    
    return 0;
}