problem
trzeba umieścić prostokąta o rozmiarze n x m na wolnej powierzchni matrycy o rozmiarze M x N, gdzie N=n*2-1
, M=m*2-1
. Komórka macierzy jest uważana za wolną, jeśli jest true
i zajęta, jeśli jest to false
. Środkowa komórka jest zawsze true
i zawsze będzie wewnątrz prostokąta ze względu na rozmiary prostokąta i macierzy.Algorytm umieszczenie prostokąt o określonych rozmiarach umieścić w wolnej przestrzeni w matrycy
Dodatkowym wymaganiem jest, aby odległość między lewym górnym rogiem prostokąta a środkową komórką była możliwie jak najmniejsza.
Przykład z n=8
i m=5
:
gdzie szare komórki - komórkowe środek, niebieskie komórek - - zajęte, zielony roztwór prostokąt, linia czerwona - odległość między górnym lewym rogu prostokąta i środka komórki.
Próby
brute force roztwór miałyby O (N x M x N x m) złożoności czasu, który nie jest bardzo optymalne. Mogę wyeliminować obliczenia w niektórych komórkach, jeśli przygotowuję matrycę, ale to zajmie zbyt dużo czasu.
Początkowo myślałem, że mogę wziąć problem Max Rectangle i po prostu zmodyfikować warunek od maksimum do potrzebnego, ale to poszło do ślepego zaułka (musiałbym wyświetlić wszystkie prostokąty w histogramie, którego nie wiem jak). Wtedy pomyślałem, że to jest jak problem z pakowaniem, ale jedyne co mogłem znaleźć to jego wersje z początkowo całkowicie pustą przestrzenią i wieloma prostokątami, co nie dotyczy tego problemu.
Kontekst
W przeszłości, gdy użytkownik kliknie na siatce, mój program będzie umieścić prostokąt, z górnym lewym rogu pokrywającym się z punktu kliknięcia, jeżeli jest ona pusta i nie, jeśli są zajęte komórki gdzie prostokąt będzie leżał . Postanowiłem zmodyfikować to zachowanie, a zamiast niepowodzenia, znajdź najbardziej odpowiednią pozycję dla prostokąta, wciąż zawierającą punkt kliknięcia. Na powyższym rysunku matrycy punktem kliknięcia jest zielona komórka, a rozmiar matrycy reprezentuje wszystkie możliwe pozycje prostokąta.
P.S. Wolałbym przykład języka rzeczywistego zamiast pseudokodu, jeśli to możliwe. Mój program jest napisany w Javie, ale każdy język jest w porządku.