choose_columns_with_one_odd.cpp

#include <cstdio>

using namespace std;

 /*const int N = 4;
 const int t[N][N] = {
 {1,2,2,1},
 {1,2,2,0},
 {2,1,1,0},
 {2,2,2,2}
 };*/

const int N = 4;
const int t[N][N] = {
    { 1, 1, 1, 1 },
    { 1, 2, 2, 2 },
    { 1, 2, 2, 2 },
    { 1, 2, 2, 2 }
};

bool oneOddWithChosenRows(bool choose[N]) // Sprawdza, czy przy danym wyborze wierszy w każdym z nich jest dokładnie jedna nieparzysta
{
    int odds = 0;
    for(int col = 0; col < N; col++) // Dla każdej kolumny
    {
        odds = 0;
        for(int row = 0; row < N; row++) // Każdy wiersz
        {
            if(choose[row] && t[row][col]%2 == 1) // Sprawdź, czy jest wybrany, jeśli jest wybrany i w komórce jest nieparzysta liczba, policz ją
            {
                odds++;
            }
        }
        if(odds != 1) { return false; } // Jeśli w kolumnie nie ma dokładnie jednej nieparzystej, wybór nie spełnia naszych warunków
    }
    printf("Wybrane wiersze:\n");
    for(int i = 0; i<N; i++) { printf("%d ",choose[i]); }
    printf("\n");
    return true;
}

bool processChoose(int pos, bool choose[N], int to_choose) // Przetwarza tablicę wyborów w miejscu pos
{
    if(to_choose == 0 && pos != N) // Jeśli wykorzystaliśmy pulę wierszy do wyboru, ale nie doszliśmy do końca, możemy już sprawdzić, czy dany wybór spełnia warunki
    {
        return oneOddWithChosenRows(choose);
    }
    if(pos == N && to_choose != 0) // Jeśli doszliśmy do końca, ale wybraliśmy mniej wierszy niż wymagane, na pewno nie o to nam chodzi
    {
        return false;
    }
    if(to_choose == 0 && pos == N) // Jeśli doszliśmy do konca i wybraliśmy idealnie wierszy, sprawdzamy wybór
    {
        return oneOddWithChosenRows(choose);
    }
    if(!processChoose(pos+1,choose,to_choose)) // Jeśli nie biorąc aktualnego wiersza nie spełnimy warunku zadania
    {
        choose[pos] = 1; // Bierzemy aktualny wiersz
        if(!processChoose(pos+1,choose,to_choose-1)) // I sprawdzamy, czy biorąc ją zadziała, jeśli nie
        {
            choose[pos] = 0; // Oddajemy ją
            return false; // I mówimy, że nie da rady
        }
    }
    return true; // Jeśli któraś opcja zwróciła prawdę – i my zwracamy prawdę
}

bool canChoose(int rows_to_choose) // Spradza, czy da się wybrać rows_to_choose wierszy spełniających warunki zadania
{
    bool choose[N]; // Tablica trzymająca 0 – nie bierzemy wiersza, 1 – bierzemy wiersz
    for(int i = 0; i<N; i++) // Cza wyzerować
    {
        choose[i] = 0;
    }
    return processChoose(0,choose,rows_to_choose); // Przetwarzamy tablicę od 0, mogąc wybrać rows_to_choose wierszy
}

int main()
{
    printf("%d\n",canChoose(2));
    return 0;
}