(New page: #include <stdio.h> #include <stdlib.h> #include <string.h> #include "IPA2-5print.h" void print_partition(int size,int *partition) { printf("["); int i; for (i=0;i<size;i++) { ...) |
|||
Line 1: | Line 1: | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
void print_partition(int size,int *partition) | void print_partition(int size,int *partition) | ||
{ | { |
Latest revision as of 05:08, 25 April 2012
void print_partition(int size,int *partition) {
printf("["); int i; for (i=0;i<size;i++) { printf("%d",partition[i]); } printf("]\n");
}
int emptyFirstColumn(char *data,int dim) {
int empty=1; int i; for (i=0;i<dim;i++) {
if (data[i*dim]!='0')empty=0; } return empty;
}
Blokus *gen_row(int row,int prevCol, int size,int *partition, char *data,int dim) {
//base case:gone through all rows if(row==size) {if(emptyFirstColumn(data,dim))return NULL; return Blokus_create(data,dim); } // recursive case: we stil have not assigned all blocks in // this partition int col; int start=0; int stop =dim-partition[row]+1;
if(row!=0) { start=prevCol - partition[row]+1; if(start<0)start=0;
stop=prevCol+partition[row-1]; if (stop + partition[row]>dim) stop=dim-partition[row]+1;
}
Blokus *head =NULL; for (col=start;col<stop;col++) { memset(data+row*dim,'0',sizeof(char)* dim); memset(data+row*dim+col,'1',sizeof(char)*partition[row]); Blokus *list= gen_row(row+1,col,size,partition,data,dim); head=BlokusL_append(head,list);
} return head;
}
Blokus *gen_shifts(int *partition,int size, int dim)
{
char *data=malloc(sizeof(char)*dim*dim); memset(data,'0',sizeof(char)*dim*dim); Blokus *list= gen_row(0,0,size,partition,data,dim);
free(data); return list;
}
Blokus *gen_partition(int budget, int pos, int *partition,int dim)
{
//base case:no more budget spin spin everything if(budget==0) {print_partition(pos,partition); Blokus *list=gen_shifts(partition,pos,dim); return list;
} //recursive case:we have budget Blokus *head =NULL; int spending; for (spending=1;spending<=budget;spending++) { partition[pos]=spending; Blokus *list= gen_partition(budget-spending,pos+1,partition,dim); head =BlokusL_append(head,list); } return head;
} Blokus *make_unique(Blokus*head) {
return head;
}
Blokus *generate_pieces(int n)
{
int *partition=malloc(sizeof(int)*n); // step 1+2:partition+shift valid Blokus *head =gen_partition(n,0,partition,n); // step 3:uniqueness
head =make_unique(head);
free(partition);
return head;
}
int main(int argc, char *argv[])
{
if(argc !=2) { return EXIT_FAILURE; }
int n=strtol(argv[1],NULL,10); Blokus *head = generate_pieces(n); BlokusL_print(head); BlokusL_destroy(head);
return EXIT_SUCCESS;
}