二次元配列を塗りつぶすロジック

Question

私はRow_wise_sumとColumn_wise_sumだけが与えられた0と1の2次元配列を満たすための一般的なロジックを探しています。

以下はサンプルコードですが、ロジックが動作しません。

ご注意：Colの配列の順序は関係ありません。 Rowの順序が重要であり、RowSumとColSumの順序はまったく同じであると言います。

もう1つの例外/条件は、すべての行が一意であることです。

RowSizeとColSizeが任意の値に変更されても、フィットするロジックが必要です。 10x10または4x8または2x9または7x4などとしましょう。

#include <stdio.h> 

/* 

0 1 1 1 1 | 4 --> Row wise totals, order is important 
1 0 0 1 0 | 2 
1 1 0 1 1 | 4 
0 1 0 1 1 | 3 
1 1 1 1 0 | 4 
--------------------- 
3 4 2 5 3  --> Column wise totals, order is not important 

*/ 


int main()      
{ 

    int i = 0; 
    int j = 0; 

    int RowSum[5] = {4, 2, 4, 3, 4}; 
    int ColSum[5] = {3, 4, 2, 5, 3}; 

    int matrix[5][5] = {0}; 

    // Fill up the matrix 
    for(i=0; i<5; ++i) 
    { 
     for(j=0; j<5; ++j) 
     { 
      if(RowSum[i]>0 && ColSum[j]>0) 
      { 
       matrix[i][j] = 1; 
       RowSum[i]--; 
       ColSum[j]--; 
      } 
     } 

    } 


    // Print matrix 
    for(i=0; i<5; ++i) 
    { 
     printf("\n"); 
     for(j=0; j<5; ++j) 
     { 
      printf(" %d ", matrix[i][j]); 
     } 
    } 


    // Validate RowSum 
    printf("\n\n"); 
    for(i=0; i<5; ++i) 
    { 
     printf("\n RowSum[%d] = %d ", i+1, RowSum[i]); 
     if(RowSum[i] != 0) 
      printf("Invalid, must be 0"); 
    } 


    // Validate ColSum 
    printf("\n\n"); 
    for(i=0; i<5; ++i) 
    { 
     printf("\n ColSum[%d] = %d ", i+1, ColSum[i]); 
     if(ColSum[i] != 0) 
      printf("Invalid, must be 0"); 
    } 

    printf("\n\n"); 

    return 0; 

} 

/* Output 


1 1 1 1 0 
1 1 0 0 0 
1 1 1 1 0 
0 1 0 1 1 
0 0 0 1 1 


RowSum[1] = 0 
RowSum[2] = 0 
RowSum[3] = 0 
RowSum[4] = 0 
RowSum[5] = 2 Invalid, must be 0 


ColSum[1] = 0 
ColSum[2] = 0 
ColSum[3] = 0 
ColSum[4] = 1 Invalid, must be 0 
ColSum[5] = 1 Invalid, must be 0 


*/ 

ありがとうございます。

Answer 1

可能性のある配列（2 ^（RowSum.length * ColSum.length）の可能性）ごとに同様のことを考えることができる他の方法がない場合は、それを強制して、配列が行/列合計を満たすかどうかを確認してください。アイデアは非常に単純であるので、ここですべてのコンボを、取得するにはいくつかの方法は、おそらくあります私はJavaでなく、アイデアの上にいた非常に粗製の試みは簡単に私が手C

public class f { 

    static int[] RowSum={4,2,4,3,4}; 
    static int[] ColSum={3,4,2,5,3}; 
    static int[] tmp = new int[RowSum.length*ColSum.length]; 


    /** 
    * 
    * @param A array w/ 1s and 0s 
    * @return true if A is a valid solution 
    */ 
    static boolean sums(int[] A){ 
     for(int i=0;i<ColSum.length;i++){ 
      int sum = 0; 
      for(int j=0;j<RowSum.length;j++){ 
       sum+=A[i+j*ColSum.length]; 
      } 
      if(sum!=ColSum[ColSum.length-i-1]) return false; 
     } 

     for(int i=0;i<RowSum.length;i++){ 
      int sum = 0; 
      for(int j=0;j<ColSum.length;j++){ 
       sum+=A[j+i*ColSum.length]; 
      } 
      if (RowSum[RowSum.length-1-i]!=sum) return false; 
     } 
     return true; 
    } 


    /** 
    * 
    * @param A array length = RowSum*ColSum initially filled with only 0s 
    * @param i initialize to 0 
    * @param j initialize to A.length-1 
    */ 
    static void g(int[] A,int i, int j){ 
     if(sums(A)) { 
      // copy A to tmp 
      System.arraycopy(A, 0, tmp, 0, A.length); 
      return; 
     } 
     if(i<=j){ 
      A[i]=0; 
      g(A,i+1,j); 
      A[i]=1; 
      g(A,i+1,j); 
     } 

    } 

    /** 
    * 
    * @param A array w/ length l 
    * @return 2d array with length = l/RowSum and height = l/ColSum 
    */ 
    static int[][] h(int[] A){ 
     int[][] result = new int[RowSum.length][ColSum.length]; 
     for(int i=0;i<result.length;i++){ 
      for(int j=0;j<result[0].length;j++){ 
       result[i][j]=A[i*result[0].length+j]; 
      } 
     } 
     return result; 
    } 

    static int[] reverse(int[] A){ 
     for(int i = 0; i < A.length/2; i++) { 
      int temp = A[i]; 
      A[i] = A[A.length - i - 1]; 
      A[A.length - i - 1] = temp; 
     } 
     return A; 
    } 

    // print 2d array 
    static void print(int[][] A){ 
     for(int[] i:A) System.out.println(Arrays.toString(i)); 
    } 

    static int[][] solve(){ 
     tmp=reverse(tmp); // reverse to make array look like array in question 
     return h(tmp); // change to 2d array and return result 
    } 



    public static void main(String [] args) { 
     //int A[] = {0,1,1,1,1,1,1,0,1,0,1,1,0,1,1,0,1,0,0,1,1,1,1,1,0}; 
     int Arr[] = new int[ColSum.length*RowSum.length]; 
     g(Arr,0,Arr.length-1); 
     print(solve()); 

    } 



} 

出力に拡張する必要があります：

[1, 1, 1, 1, 0] 
[1, 0, 0, 1, 0] 
[1, 1, 0, 1, 1] 
[0, 1, 0, 1, 1] 
[0, 1, 1, 1, 1]