삼각형 알고리즘

Question

I는이 문제를 해결해야한다 :

5 
#-##----# 
-----#- 
    ---#- 
    -#- 
    - 

수가 삼각형의 행의 수이다

입력이 예를 들어 다수의 삼각형이다.

그리고 가장 큰 "삼각형 영역"- -으로 만든 가장 큰 삼각형을 인쇄해야합니다. 이를 위해

4 
#-#-#-- 
#---# 
    ##- 
    - 

는 출력 내가 알고리즘 도움이 필요 4.

입니다 :이 하나에 대한 대답은 삼각형은 거꾸로 할 수있다 9.

입니다. 전체 알고리즘이 아니라 조금만 도와주세요. 제가 직접 해결하려고하기 때문에 방향이 필요합니다.

Answer 1

힌트

나는 모든 삼각형의 형식은 가정 : 좋아

--- 
- 

그리고하지 :

- or - or - 
---  --  -- 
      -   - 

비고 2 대 삼각형이 구성되어 있음 세 개의 1 단위 삼각형. 3 단위 삼각형은 3 개의 겹치는 2 단위 삼각형으로 구성됩니다. 전체 알고리즘 수행 돈 '

다음도 세 2 단위 삼각형 이루어진 3 부 삼각형의 일례이며, 그 자체는 세 1 부 삼각형

- -+ -+* +* *   --- +++ *** 
    - + *  ==>  - + * 
     o      o 

스포일러 이루어지는 t는

당신이 할 수있는

/!\ spoiler alert /!\ 

/!\ spoiler alert /!\ 

/!\ spoiler alert /!\ 

주요 알고리즘을 읽고 모든 단위 크기의 삼각형 (정확하게 1 -을 가지고 있음)을 계산하기위한 첫 번째 단계를 수행하십시오. T[x,y]이 삼각형의 크기 (그 변의 길이) 인 테이블을 유지 보수합니다. 이 패스에서는 -을 1로 설정하여 모든 셀을 초기화합니다.

그런 다음 위에서 아래로 이동하여 더 복잡한 삼각형을 만들 수 있습니다.

총수 [X, y]는, 당신은 그 아래 선두 인 삼각형 고려해야하는 경우 :

• [X-1, Y-1]
• [X, Y-1]
을
• [X + 1, Y-1]

새로운 삼각형의 크기는 1이 플러스 삼각형 위 (3)의 임의의 최소 크기 것이다. 그런 다음, 테이블을 끝에 T[x,y]

T[x,y+1] = 1 + min(T[x-1,y], T[x,y], T[x+1,y]) 

를 업데이트 당신의 테이블 T에서 가장 큰 크기의 삼각형을 찾아 해당 삼각형의 면적을 계산한다. (독자가 운동으로 남긴 공식)

복잡도는 O(n²)입니다.

Answer 2

효율성이 훨씬 문제가되지 않는 경우 :

후보에 대한 검색 수 (가 왼쪽에서 오른쪽으로 각 행을 통과하는) 하나 개의 루프 되세요. -을 찾은 경우을 인터럽트로 검색하고 을 시도한 후을 계산하십시오.

따라서 먼저 오른쪽으로 이동하여 끝나는 곳을 확인하십시오 (#). 그런 다음 삼각형 (지표)의 밑바닥을 알고 다음 줄에서 계속해야하는 위치를 직접 확인하고 그 후보를 완전히 조사 할 때까지 확인하고 반복하십시오. indix 왼쪽이 li이고 행이 row 인 오른쪽이 인 경우 삼각형은 row * row + 1의 색인 li + 1 및 ri - 1에서 계속되어야합니다.

크기를 저장하고 검색 부분을 다시 계속하십시오. 가 검색되면 번은 모든 행을 방문합니다.

---

당신은 약간 이미 발견 된 삼각형의 일부 -를 무시함으로써 효율성을 향상시킬 수 있습니다. 그러나 그들이 삼각형의 일부인 경우에만 기본 행.

Answer 3

저는 알고리즘 전문가는 아니지만 도움이 아닌 답변을 요청 했으므로 답변을 제출할 수 있다고 생각합니다.

공간을 테스트하여 삼각형 내에 있는지 확인하는 방법을 찾아야합니다. 일단 당신이 그것을 갖게되면 나는 무차별 대입 접근법을 설계 할 것이다. (모든 공간에 대해 "삼각형 테스트"를 실행한다.)

그런 다음 최적의 방법이 아닌 무차별 솔루션을 사용하는 경우 더 효율적으로 사용해보십시오. 예. 당신이 일하는 해결책을 얻을 때까지 능률적이 나 똑똑한 것에 대해 걱정하지 마십시오. 도움이 되길 바랍니다.