Wprowadzenie
Jest mała wioska z kilkoma domami i pustymi polami. Lokalni biurokraci chcą podzielić wioskę na działki, tak aby każda działka zawierała dokładnie jeden dom, a granice działek tworzą ładną linię prostą. Twoim zadaniem jest ustalenie, czy jest to możliwe.
Zadanie
Twoje dane wejściowe to prostokątna tablica bitów 2D; 1 oznacza dom, a 0 puste pole. Jego rozmiar będzie wynosił co najmniej 1 × 1 i będzie zawierał co najmniej jeden 1. Możesz pobrać dane wejściowe w dowolnym rozsądnym formacie (zagnieżdżona lista liczb całkowitych, lista ciągów, ciąg wielowierszowy itp.).
Twój program określi, czy tablicę można podzielić na komórki siatki za pomocą prostych linii poziomych i pionowych, tak aby każda komórka siatki zawierała dokładnie jedną 1. Komórki siatki mogą mieć różne rozmiary i kształty, chociaż zawsze będą prostokątne. Linie muszą przebiegać od jednej krawędzi tablicy do drugiej krawędzi.
Na przykład poniżej podano poprawny podział tablicy:
00|0010|01|1
01|0000|00|0
--+----+--+-
00|0000|00|1
01|0010|01|0
--+----+--+-
01|1000|10|1
mając na uwadze, że następujący podział nie jest prawidłowy, ponieważ istnieją komórki siatki bez 1 lub więcej niż 1:
00|0010|01|1
--+----+--+-
01|0000|00|0
00|0000|00|1
01|0010|01|0
--+----+--+-
00|1000|10|1
Jeśli istnieje prawidłowy podział, należy podać wartość zgodną z prawdą, a w przeciwnym razie wartość fałsz.
Zasady i punktacja
Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów.
Przypadki testowe
[[1]] -> True
[[0,1],[1,0]] -> True
[[1,1],[1,0]] -> False
[[1,0,1],[0,1,0]] -> True
[[1,0],[0,1],[0,1]] -> True
[[1,0,0],[0,0,1],[0,1,1]] -> True
[[1,1,1],[1,1,1],[1,1,1]] -> True
[[1,0,1],[0,1,0],[1,0,0]] -> True
[[1,0,0],[1,0,0],[0,1,1]] -> False
[[0,0,0,0,1],[1,0,0,1,0],[0,0,0,1,0]] -> False
[[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,0]] -> True
[[1,1,0,0,0],[0,0,0,0,0],[1,0,1,0,0]] -> True
[[1,1,0,1,1],[0,1,0,1,1],[1,0,0,0,0]] -> True
[[0,0,0,0,0,0,0],[0,1,1,1,0,1,0],[0,1,0,0,1,0,0],[0,0,0,0,0,0,1],[0,0,1,0,0,0,1],[1,1,0,1,1,0,0]] -> False
[[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[0,0,0,0,1,0,0],[0,1,0,1,1,0,0],[1,0,0,0,1,1,0],[0,0,0,0,0,1,0]] -> False
[[0,1,0,1,1,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,0],[1,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1]] -> True
[[0,1,0,0,1,0,1],[1,0,0,0,1,0,1],[0,0,1,0,1,0,1],[1,0,0,0,1,1,0],[0,0,0,1,1,1,0],[0,1,0,0,1,0,1]] -> True
[[0,1,0,0,1,0,0,1,0],[0,0,0,0,1,1,0,1,0],[1,1,0,0,1,0,0,0,0],[0,0,1,0,1,0,1,0,0],[0,0,1,0,1,0,1,0,0],[0,1,0,0,0,1,0,0,1],[0,1,0,0,0,0,1,0,0]] -> False
[[1,0,1,0,0,1,1,0,1],[0,1,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,1,1],[0,1,1,0,1,0,1,0,1],[1,0,1,0,0,1,1,0,1]] -> True
[[1, 0, 1], [0, 1, 0], [1, 0, 0]]
była to jedyna matryca 3x3, dla której moje nowe podejście zawiodło.Odpowiedzi:
Pyth,
3029262423 bajtówWypróbuj online.
Jestem pewien, że będzie krótszy. Jest to O (2 min ) , w którym m i n są szerokość i wysokość matrycy, lecz kończy się dwa ostatnie testów w ciągu 45 sekund na laptopie z baterii (i5-5200U z ograniczoną skuteczności).
Wyświetla liczbę rozwiązań.
Wyjaśnienie
Praca z pięciowymiarowymi tablicami jest naprawdę przyjemna. </sarcasm> Nie powinieneś rozumieć, jak to działa, nawet z wyjaśnieniem.
źródło
Galaretka , 22 bajty
Wypróbuj online!
źródło
Haskell , 116 bajtów
Wypróbuj online!
źródło
mergerows
nam
.[[1,0],[0,1],[1,0]]
. Problem polega na tym, że zachłanne załamanie może przeszkadzać później.[[1,1],[1,0]]
upadek fałszywie utrudnia[[1],[1],[1]]
rozwiązanie. Pozwól mi się przespać, czy powinienem usunąć?Galaretka , 20 bajtów
To wciąż rozwiązanie brutalnej siły, ale jest nieco szybsze niż moja inna odpowiedź - która nie radzi sobie z dwoma ostatnimi przypadkami testowymi na TIO - i obsługuje wszystkie przypadki testowe w ~ 4 sekund.
Wypróbuj online!
Jak to działa
źródło