Witam,
mam mało ciekawy problem, z którym elegancko nie mogę sobie poradzić.
Dana jest tablica \(\displaystyle{ n \times m}\) o wartościach \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\). Należy znaleźć tablicę, w której w każdym wierszu znajduje się dokładnie 1 jedynka i ta jedynka również znajduje się w tablicy wejściowej i w żadnej kolumnie nie ma więcej niż 1 jedynki.
Przykład:
Tabela wejściowa:
\(\displaystyle{ \begin{tabular}{cccccc}
0 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 \\
\end{tabular}}\)
Przykładowy wynik:
\(\displaystyle{ \begin{tabular}{cccccc}
0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
\end{tabular}}\)
Oczywiście dla wielu tabel rozwiązań może być więcej, ale chodzi mi o to, aby znaleźć jedno dowolne lub zwrócić informację, że nie ma takiej możliwości.
Jest jakiś algorytm określający ten problem, bądź prosty i niezbyt złożony sposób na obliczenie tego w aplikacji?
[Algorytmy][C] Znajdywanie unikalnej kombinacji
- miki999
- Użytkownik
- Posty: 8691
- Rejestracja: 28 lis 2007, o 18:10
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 36 razy
- Pomógł: 1001 razy
[Algorytmy][C] Znajdywanie unikalnej kombinacji
Dzięki za odpowiedź. Znalazłem nawet doprecyzowanie tego problemu nazwane "dziurawą szachownicą", chociaż i tak wykracza to poza moje umiejętności (chyba się starzeję ), ale może zapożyczę od kogoś w przyszłości algorytm.