#include<stdlib.h>#include<stdio.h>#defineMAX_PATTERNS 20-1#defineB 0#defineI 1#defineN 2#defineG 3#defineO 4typedefstruct{ char square[5][5];/* row, col */} bingo_card_t; int num[5], num_patterns, num_combinations; bingo_card_t pattern[MAX_PATTERNS]; int active_patterns[MAX_PATTERNS]; int active_pattern_count; int least_remaining_calls; voidcheck_combination() {/** Ok, the active_patterns array tells us which cards to combine.* Let's see how far this combination is from winning...* We do this by counting how many calls we need in each column* and then subtracting the already called count for that column.* Finally, we total that count for each column and compare to* our best case so far.*/int row, col, card; int total_count; total_count = 0;for(col = 0; col < 5; col++) { int col_count; col_count = 0;for(row = 0; row < 5; row++) { int found; found = 0;for(card = 0; card < num_patterns; card++) {if( (active_patterns[card] == 1) && (pattern[card].square[row][col] == 'X') ) { found = 1;break; } }if(found) { ++col_count; } }/* done counting this column *//* printf ("col %d = %d\n", col, col_count); */if(col_count > num[col]) { total_count += ( col_count - num[col] ); } }/* done processing this combination *//* check to see if this combination is the best so far */if(total_count < least_remaining_calls) { least_remaining_calls = total_count; } }/* end check_combination */voidcalculate_next_card(int mycard) {/** We get called only in two situtations:* #1 - our card is the last one needed before testing* #2 - more than one card is needed* In either case, we need to make the next* level call with ourselves both on and off** Of course, we could also be the last card, in* which case 'on' is the only choice that makes sense*//* activate this card & check */active_patterns[mycard] = 1; active_pattern_count++;if( active_pattern_count == num_combinations ) {check_combination(); }else{calculate_next_card(mycard+1); }/* deactivate this card before returning */active_patterns[mycard] = 1; active_patterns[mycard] = 0; active_pattern_count--;/** If there are enough inactive cards remaining* to absorb the remaining cards required to* meet the combination criteria without us,* go ahead and try that too.*/if( (num_combinations - active_pattern_count) <= (num_patterns - (mycard + 1)) ) {calculate_next_card(mycard+1); } } intmain(void) { int datasets, i;scanf(" %d ", &datasets);for(i = 0; i < datasets; i++) { int card, row, col;/* read in the header line */scanf(" %d %d %d %d %d %d %d ", &num[B], &num[I], &num[N], &num[G], &num[O], &num_patterns, &num_combinations);/* read in the patterns */for(row = 0; row < 5; row++) {for(card = 0; card < num_patterns; card++) {for(col = 0; col < 5; col ++) {scanf(" %c ", &pattern[card].square[row][col]); }/* unmark free square */if(row == 2) { pattern[card].square[row][2] = 'O'; } } }/* reset all patterns to inactive */memset(active_patterns,0,sizeof(active_patterns[0]) * MAX_PATTERNS); active_pattern_count = 0; least_remaining_calls = 24;/* do calculations */calculate_next_card(0);/* start w/first card *//* display results */printf("%d\n",least_remaining_calls); }return0; }