BOJ 1028 - 다이아몬드 광산

문제 링크 : https://www.acmicpc.net/problem/1028

문제 풀이

다이아몬드는 4개의 선분으로 이루어진다. 정확히 맞물리는 4개의 길이가 같은 대각선을 찾으면 된다.

어떤 위치로 부터 k개의 연속된 1이 대각선 방향으로 있으면 k 이하의 임의의 길이의 대각선을 찾을 수 있다는 것이다. 따라서 우리는 모든 위치에 대해서 4개의 방향으로 각각 어디까지 1이 이어져 있는지를 알고 있어야 한다.

따라서 다음과 같이 DP 값을 정의할 수 있다. ld[i] = 왼쪽 아래로 이어져 있는 1의 개수, rd[i] = 오른쪽 아래로 이어져 있는 1의 개수, lu[i] = 왼쪽 위로 이어져 있는 1의 개수, ru[i] = 오른쪽 위로 이어져 있는 1의 개수. 이는 주어진 맵을 스캔하는 과정에서 $O(N^2)$에 전체 DP table을 채울 수 있다.

그 다음 모든 위치에 대해서 그 위치가 마름모의 위쪽 꼭짓점일 때의 최대 크기와 왼쪽 꼭짓점일 때의 최대 크기를 구할 것이다. 이는 1부터 두 개의 대각선으로 이어져 있는 1의 갯수 중 더 작은 값까지 각각 확인하면서  최댓값을 구해주면 된다. 
예를 들어서 min(ld,rd)가 5이면 현재 위치가 위쪽 꼭짓점인 경우는 1~5까지 해볼가치가 있다는 것이고, k를 확인할 때는 아래로 (k-1)*2 만큼 떨어진 칸에 lu와 ru 값이 k보다 큰 지 확인함으로써 알 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll arr[1508][1508];
ll ld[808][808];
ll rd[808][808];
ll lu[808][808];
ll ru[808][808];
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%1lld",&arr[i][j]);
 
    for(i=n;i>=1;i--)
        for(j=1;j<=m;j++)
            if(arr[i][j]==1){
                ld[i][j]=ld[i+1][j-1]+1;
                rd[i][j]=rd[i+1][j+1]+1;
            }
 
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(arr[i][j]==1){
                lu[i][j]=lu[i-1][j-1]+1;
                ru[i][j]=ru[i-1][j+1]+1;
            }    
 
    ll ans=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            for(k=1;k<=min(ld[i][j],rd[i][j]);k++)
                if(arr[i+2*(k-1)][j]&&lu[i+2*(k-1)][j]>=k&&ru[i+2*(k-1)][j]>=k)
                    ans=max(ans,k);
            for(k=1;k<=min(ru[i][j],rd[i][j]);k++)
                if(arr[i][j+2*(k-1)]&&lu[i][j+2*(k-1)]>=k&&ld[i][j+2*(k-1)]>=k)
                    ans=max(ans,k);
            
        }
    printf("%lld",ans);
}