동적 프로그래밍 : 가장 큰 다이아몬드 (마름모) 찾기

Question

자바로 수행 할 작은 프로그램이 있습니다. 나는 0과 1로 채워진 2D 배열을 가지고 있으며, 가장 큰 마름모 (사각형에서 45도 회전 한 것과 같이)와 그 숫자를 찾아야합니다.

예 :

 
0 1 0 0 0 1 

1 0 1 1 1 0 

1 0 1 1 1 1 

0 1 1 1 1 1 

0 0 1 1 1 1 

1 1 1 1 1 1 

결과 :

 
     1  

    1 1 1 

    1 1 1 1 1 

    1 1 1 

     1  

this SO question 문제는 유사하다.

아이디어가 있으면 여기에 게시하십시오.

Answer 1

댓글에 너무 오래 사용했습니다. 당신이 그것을 해결할 수 없다면 나중에 해결책을 게시 할 것이지만, 나는 그것을 (코드의 15 줄 이하에서) 어떻게 했는가? 나는 처음에 두 번째 배열을 만들었다. (더 큰 [n + 2]

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 2 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 3 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 

비제 번호 X가 I와 함께 관련 크기를 표현하고있어 ("I 크기 X의 마름모의 중심 해요"의미 : N + 2) 및/2 패스 N 않았다 대각선의 길이 [두 경우 모두 동등한 마름모입니다]. {위쪽, 오른쪽, 아래쪽, 왼쪽}이 모두 크기 k의 마름모의 중심인지 확인하여 크기가 (k + 1) 인 마름모 중심이 있는지 확인할 수 있습니다.

더 큰 어레이를 처음 만드는 이점은 논리를 정말 단순화한다는 것입니다.하지만 원래의 어레이를 수정하거나 동일한 크기의 두 번째 배열을 사용하여 논리를 단순화 할 수 있습니다. 입력 (다시 한번 말하면, 입력 주위에 모두 0의 안전한 "펜스"를 넣는 것이 더 쉽습니다).

어레이를 울타리로 "둘러싸"지 않으면 if/else 검사가 추가로 많이 발생합니다. 오류가 발생하여 코드가 커지고 코드가 더 추악해질 수 있습니다.

Answer 2

짧은 튜토리얼 : 그것은 1x1 -field가 있다면

가 어떻게 문제를 해결할 것인가?
어떻게 재귀 적으로 문제를 공식화 할 수 있습니까?
어떻게 중간 결과를 기억하고 사용합니까?
하십시오.

Answer 3

void rhombus() 
{ 
    maxr=0; 
    for (int i=n-1;i>=0;i--) 
    { 
     for (int j=n-1;j>=0;j--) 
     { 
      if (b[i][j]>0) 
      { 
       if ((i==n-1) || (j==n-1) || (i==0) || (j==0)) b[i][j]=1; 
       else { 
        b[i][j]=min4(b[i][j+1],b[i][j-1],b[i+1][j],b[i-1][j])+1; 
        if (b[i][j]==maxr) nrr++; 
        else if (b[i][j]>maxr) { 
         nrr=1; 
         maxr=b[i][j]; 
        } 
       } 
      } 
     } 
    } 
} 

, 그것은 작동이 maxr이 마름모의 최대 크기이며, NRR는 최대의 수는이 거대한 배열에 어떻게 작동하는지 rhombus.Not 확실히 크기 내 기능입니다. 그것을했다 (내가 루프 이 함수는 n/2 번)