흑백 초콜릿 바 나누기 알고리즘

Question

문제 설명 : m x n 개의 사각형으로 구성된 초콜릿 바가 있습니다. 일부 사각형은 검은 색이고 일부는 흰색입니다. 누군가가 초콜릿 바를 수직축 또는 수평축을 따라 끊습니다. 그런 다음 수직 또는 수평 축을 따라 다시 부러지며 하나의 사각형으로 부러 질 때까지 부러 지거나 검정색 또는 흰색 만있는 사각형으로 부러 질 수 있습니다. 가급적이면 divide-and-conquer 알고리즘을 사용하여 초콜릿 바가 깨질 수있는 방법의 수를 찾으십시오.

입력 : 첫 번째 줄은 초콜릿 바의 크기를 나타냅니다. 다음 m 줄에는 n 개의 문자가있어 초콜릿 바가 어떻게 보이는지 알려줍니다. 문자 w는 흰색 사각형이고, 문자 b는 검은 색 사각형입니다. 예 : WBW BWB

출력 : 초콜릿 바를 파손 할 수있는 방법의 수 : 위 예 는, 그것의 (5) (첨부 된 사진을 살펴).

제가 반복적 접근법을 사용하여 해결하려고 노력했다. 불행히도 코드를 완성 할 수 없었습니다. 절반을 어떻게 나눌 지 아직 확실하지 않습니다 (아래 코드 참조). 재귀 적 접근 방식이 이것보다 훨씬 쉽다고 들었지만 어떻게해야하는지 잘 모릅니다. 내 접근 방식보다이 문제를 해결할 다른 방법을 찾고 있거나 코드 완성에 대한 도움을 찾고있다.

두 개의 2D 배열을 만들었습니다. 먼저 흰색 사각형을 만들고 두 번째 검정 사각형을 만듭니다. 저는 사각형에서 행렬을 만들고 있습니다. 그런 색상의 초콜릿이 있다면, 해당 배열에서 1로 표시 할 것입니다. 그런 다음 위에 두 행의 누적 합계 중 두 개의 배열을 만들었습니다.그런 다음 크기가 4D 인 배열을 만들고 네 개의 루프를 만들었습니다. 첫 번째 두 개 (i, j)는 검색 배열의 크기 인 직사각형 배열의 크기를 늘립니다 (설명하기가 꽤 어렵습니다 ...) 그리고 2 개의 더 많은 루프 (k, l)가 배열에서 시작점 x와 y의 위치를 ​​증가시키고 있습니다. 그런 다음 알고리즘은 누적 합계를 사용하여 kxl 위치에서 시작하여 k + i x l + j에서 끝나는 영역에 검은 색 및 흰색 정사각형이 하나있는 경우 검사합니다. 있다면, 그 지역을 반으로 나눌 두 개의 루프를 더 만들고 있습니다. 두 개의 새로운 반쪽에 여전히 검은 색과 흰색 사각형이있는 경우, 첫 번째 반수 * 두 번째 반의 조합 수만큼 해당 4D 배열 요소를 증가시킵니다.

#include <iostream> 
    #include <fstream> 

    using namespace std; 

    int main() 
    { 
     int counter=0; 
     int n, m; 
     ifstream in; 
     in.open("in.txt"); 
     ofstream out; 
     out.open("out.txt"); 
     if(!in.good()) 
     { 
      cout << "No such file"; 
      return 0; 
     } 
     in >> n >> m; 

     int whitesarray[m][n]; 
     int blacksarray[m][n]; 
     int methodsarray[m][n][m][n]; 

     for(int i=0; i<m; i++) 
     { 
      for(int j=0; j<n; j++) 
      { 
       whitesarray[i][j] = 0; 
       blacksarray[i][j] = 0; 
      } 
     } 

     while(in) 
     { 
      string colour; 
      in >> colour; 
      for (int i=0; i < colour.length(); i++) 
      { 
       if(colour[i] == 'c') 
       { 
        blacksarray[counter][i] = 1; 
       } 
       if(colour[i] == 'b') 
       { 
        whitesarray[counter][i] = 1; 
       } 
      } 
      counter++; 
     } 

     int whitessum[m][n]; 
     int blackssum[m][n]; 


    for (int i=0; i<m; i++) 
    { 
     for (int j=0; j<n; j++) 
     { 
      if(i-1 == -1 && j-1 == -1) 
      { 
       whitessum[i][j] = whitesarray[i][j]; 
       blackssum[i][j] = blacksarray[i][j]; 
      } 
      if(i-1 == -1 && j-1 != -1) 
      { 
       whitessum[i][j] = whitessum[i][j-1] + whitesarray[i][j]; 
       blackssum[i][j] = blackssum[i][j-1] + blacksarray[i][j]; 
      } 
      if(j-1 == -1 && i-1 != -1) 
      { 
       whitessum[i][j] = whitessum[i-1][j] + whitesarray[i][j]; 
       blackssum[i][j] = blackssum[i-1][j] + blacksarray[i][j]; 

      } 
      if(j-1 != -1 && i-1 != -1) 
      { 
       whitessum[i][j] = whitessum[i-1][j] + whitessum[i][j-1] - whitessum[i-1][j-1] + whitesarray[i][j]; 
       blackssum[i][j] = blackssum[i-1][j] + blackssum[i][j-1] - blackssum[i-1][j-1] + blacksarray[i][j]; 
      } 
       } 
    } 


    int posx=0; 
    int posy=0; 
    int tempwhitessum=0; 
    int tempblackssum=0; 
    int k=0, l=0; 

    for (int i=0; i<=m; i++) 
    { 
     for (int j=0; j<=n; j++) // wielkosc wierszy 
     { 
      for (posx=0; posx < m - i; posx++) 
      { 
       for(posy = 0; posy < n - j; posy++) 
       { 
      k = i+posx-1; 
      l = j+posy-1; 
      if(k >= m || l >= n) 
       continue; 
      if(posx==0 && posy==0) 
      { 
       tempwhitessum = whitessum[k][l]; 
       tempblackssum = blackssum[k][l]; 

      } 
      if(posx==0 && posy!=0) 
      { 
       tempwhitessum = whitessum[k][l] - whitessum[k][posy-1]; 
       tempblackssum = blackssum[k][l] - blackssum[k][posy-1]; 

      } 
      if(posx!=0 && posy==0) 
      { 
       tempwhitessum = whitessum[k][l] - whitessum[posx-1][l]; 
       tempblackssum = blackssum[k][l] - blackssum[posx-1][l]; 

      } 
      if(posx!=0 && posy!=0) 
      { 
       tempwhitessum = whitessum[k][l] - whitessum[posx-1][l] - whitessum[k][posy-1] + whitessum[posx-1][posy-1]; 
       tempblackssum = blackssum[k][l] - blackssum[posx-1][l] - blackssum[k][posy-1] + blackssum[posx-1][posy-1]; 

      } 
     if(tempwhitessum >0 && tempblackssum > 0) 
     { 
      for(int e=0; e<n; e++) 
      { 
       //Somehow divide the previously found area by two and check again if there are black and white squares in this area 
      } 
      for(int r=0; r<m; r++) 
      { 
       //Somehow divide the previously found area by two and check again if there are black and white squares in this area 

      } 
     } 
       } 
      } 
     }} 

     return 0; 
    } 

Answer 1

강력하게 재귀를 권장합니다. 실제로 Dynamic Programming (DP)은 특히 큰 바의 경우 매우 유용합니다. 재귀 제 ...

재귀

재귀 루틴 문자 (와트 와 B)의 2-D 어레이 걸린다. 이것이 깨질 수있는 방법의 수를 반환합니다.

먼저, 기본 경우 : (1) 주어진 막대를 하나의 조각으로 나눌 수 있다면 (위의 내용을 참조하고 설명을 요구하십시오), 1을 반환하십시오. (2) 배열이 모두 하나의 색상 인 경우 1을 반환합니다. 각각에 대해 막대가 끝나는 한 가지 방법 (전달 방법) 만 있습니다.

지금, 바는 여전히 나눌 수 있습니다 더 복잡한 경우를 위해 :

total_ways = 0 
for each non-edge position in each dimension: 
    break the bar at that spot; form the two smaller bars, A and B. 
    count the ways to break each smaller bar: count(A) and count(B) 
    total_ways += count(A) * count(B) 
return total_ways 

는 일반적인 접근 방식에 대한 충분한 것이 분명하다? 당신은 여전히 ​​할 수있는 많은 코딩을 가지고 있지만 재귀를 사용하면 함수를 작성할 때 두 가지 기본 아이디어만을 생각할 수 있습니다. (1) 완료 시점을 어떻게 알 수 있습니까? (2) 내가 끝나지 않았다면 문제를 어떻게 줄일 수 있습니까?

---

동적 프로그래밍이 이미 해결 한 상황에 대한 기록을 유지 구성

. 루틴에서 가장 먼저하는 일은 "데이터베이스"를 점검하여이 사례를 이미 알고 있는지 확인하는 것입니다. 그렇다면 다시 계산하는 대신 알려진 결과를 반환하십시오. 여기에는 아마도 "bwb", "wbw"] => 5와 같은 문자열 배열 및 정수 결과의 조회 목록 (사전)을 개발하고 구현하는 오버 헤드가 포함됩니다.