글 읽기 - 다이아 몬드 광산 질문드려요

tols91 7년 전 0

전처리로 한 점 (i, j) 에서 오른쪽으로 최대길이 [0], 아래로 최대길이[1] 를 미리 저장해놓고

다시 한점 (i,j)에서 오른쪽 최대길이와 아래로 최대길이중 작은 것을 len에 넣고

그 len-1만큼 떨어진 곳에서 오른쪽최대길이 아래쪽 최대길이 해서 더 작은것을 답으로 찾게했는데 틀렸다고 하네요.

틀린점좀알려주세요~

#include <cstdio>
#include <algorithm>

using namespace std;

int dp[1000][1000][2];
int r,c;
int arr[1000][1000];

int main()
{
    scanf("%d %d", &r, &c);
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            scanf("%1d", &arr[i][j]);
            if(arr[i][j]){
                dp[i][j][0] = 1;
                dp[i][j][1] = 1;
            }
        }
    }

    for(int i=0;i<r;i++){
        for(int j=c-2;j>=0;j--){
            if(arr[i][j])
                dp[i][j][0] = dp[i][j+1][0] + 1;
        }
    }

    for(int i=0;i<c;i++){
        for(int j=r-2;j>=0;j--){
            if(arr[j][i])
                dp[j][i][1] = dp[j+1][i][1] + 1;
        }
    }

    int ans = 0;

    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            int len = min(dp[i][j][0], dp[i][j][1]);
            int len2 = min(dp[i+len-1][j][0], dp[i][j+len-1][1]);

            if(len <= len2)
                ans = max(ans, len);
        }

    }

    printf("%d\n", ans);

    return 0;
}

kyaryunha 6년 전 1

어음ㅁ.. 코드는 안읽어봤지만..

0001000

0010100

0101010

1 0 0 0 0

이런 경우 0,3을 보면, 오른쪽 최대 len은 3이고, 왼쪽 최대 len 은 2지만,

그리고 오른쪽에서 2만큼 떨어진 곳에서 내린 최대 len은 0이고, 아래쪽에서 내린 최대 len은 0이지만,

그 처음에 오른쪽 최대 len이나 왼쪽 최대len도 아닌, 그 중간 어딘가에서 생긴 다이아몬드 때문에, 답은 2가 됩니다.

이런식으로, 꼭 오른쪽 최대 len과 왼쪽 최대 len을 비교해서 더 작은 len이 꼭 그 좌표에서 채굴 할 수 있는 가장 큰 다이아몬드가 아닐 수 있어요.

그 가운데 가운데ㅔ서 더 큰 다이아몬드를 채굴 할 수도 있어요.

((으앗ㅅ.. 제가 글을 잘 못써서 설명이 좀ㅁ 난잡하지만 양해바라요 ㅠㅠ))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다이아 몬드 광산 질문드려요

tols91 7년 전 0

kyaryunha 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말