2017-08-14 98 views
6

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:

111111101111111;111111111111111;111111111111111;111111111111111;110111111111111;111111111110111;111111111111111;111111111011111;111111111111111

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.

Odpowiedz

4

Można to zrobić w O(N.M) przestrzeni i czasu złożoności przez:

  1. obliczyć summed area table w O(N.M)
  2. iteracyjne nad wszystkimi górnym lewym rogach, należy sprawdzić, czy sumuje obszar prostokąta jest równa n.m i zaktualizuj najlepszą pozycję, jeśli odległość od środka poprawi się. Test jest O(1) za lewym górnym rogu, a istnieją O(N.M) lewego górnego naroża, więc ogólnie O(N.M)

Kluczową ideą jest to, że zsumowane stół powierzchnia pozwala obliczyć sumę dowolnego prostokąta w O (1 raz.