Максимальный размер прямоугольника без монстров

Для прямоугольной сетки N * M (индексирование на основе 1), в котором их k монстров на k разных ячейках. Теперь нам нужно ответить на Q-запросы, в которых нам будет дана младшая строка номер (L) и наивысший номер строки (H), нам нужно указать максимальную площадь прямоугольника между этими строками, у которых нет монстра. (Здесь площадь прямоугольника означает только количество ячеек)Максимальный размер прямоугольника без монстров

Пример: Скажем, у нас есть сетка 4 * 5 (среднее n = 4 и m = 5), а монстры расположены на 7 (= k) клетках, которые являются (1,3), (1,4), (2,1), (2, 4), (3,2), (4,1), (4,2) и имеем 1 запрос, в котором L = 3 и H = 4, тогда максимальная площадь равна 6.

Теперь, если запросы очень большие, скажите 10^6. Затем, как решить эту проблему. Есть ли у них какой-либо динамический подход или что-то подобное?

enter image description here

Здесь красные блоки показывают монстр и фиолетовый один является решением прямоугольника

источник

2014-01-05 user3086701

Монстры повсюду даже на SO! – P0W

@ P0W Я не понимаю, что вы хотите сказать. В прямоугольнике решения мы видим, что их нет монстра. – user3086701

Когда вы говорите, что запросы очень большие, вы имеете в виду, что «H-L» очень большой? –

Вот рекурсивным решение, которое работает для застенков arbirary размера и относительно нескольких монстров.

Если в подземелье (n, w, s, e) есть один монстр (x, y)), то есть два случая. Случай 1 тривиален: монстр находится вне подземелья. Тогда максимальный прямоугольник - подземелье. (Подземелья всегда прямоугольные, не так ли?).

В случае 2, максимальный прямоугольник один из прямоугольников на север, запад, юг или восток от монстра:

NNNNNNNNNN ....EEEEEE .......... WWW....... 
NNNNNNNNNN ....EEEEEE .......... WWW....... 
NNNNNNNNNN ....EEEEEE .......... WWW....... 
NNNNNNNNNN ....EEEEEE .......... WWW....... 
NNNNNNNNNN ....EEEEEE .......... WWW....... 
[email protected] [email protected] [email protected] [email protected] 
.......... ....EEEEEE SSSSSSSSSS WWW....... 
.......... ....EEEEEE SSSSSSSSSS WWW....... 
.......... ....EEEEEE SSSSSSSSSS WWW.......

Теперь применим это рассуждение рекурсивно для списка местоположений монстров и следить из максимальный до сих пор. Вот некоторые псевдо-код:

max_area = 0 
max_rect = Null 

sub find_max_rect(Dungeon, Monsters) 

    if area(Dunegon) <= max_area: 
     return      # save time for small dungeons 

    if Monsters is empty: 
     if area(Dungeon) > max: 
      max_rect = Dungeon 
      max_area = area(Dungeon) 

    else 
     M = Monsters.pop()   # Remove head from list 

     if M in Dungeon: 
      find_max_rect(Subrect(Dungeon, M, North), Monsters) 
      find_max_rect(Subrect(Dungeon, M, East), Monsters) 
      find_max_rect(Subrect(Dungeon, M, South), Monsters) 
      find_max_rect(Subrect(Dungeon, M, West), Monsters) 
     else: 
      find_max_rect(Dungeon, Monsters)

Примечание: Я на самом деле сделал вопиющую ошибку в приведенных выше эскизов: @ представляет, конечно же, игрок и не монстр.

источник

2014-01-05 20:41:22

@M Ohem Не может быть их любой динамический подход, чтобы сделать то же самое?. Знать решение O (n^4). Но это будет очень медленно, так как N, M может быть до 1000. Я спрашиваю, потому что число запросов может быть очень большим и решая его снова и снова, не так эффективны. – user3086701

@MOehm Это проблема, связанная с продолжающимся конкурсом кодирования, пожалуйста, удалите ответ –

@VikramBhat: Кто вы, так полиция? Я отвечу. Я думал, что это интересная проблема, и я потратил некоторое время на внедрение примерного решения с некоторыми тестовыми примерами и написав ответ. Я не собираюсь проверять возможность испортить конкурс, прежде чем опубликовать ответ. Разве это не было бы задачей ОП указать это? (Кроме того: нет ничего нового под солнцем. Я совершенно уверен, что на этой или аналогичных проблемах в Интернете уже есть ответы. Вы также хотите удалить эти решения?) –

Знаете ли вы, что проблема с максимальной матричной суммой? Эта проблема может быть решена в O (n^3) раз, используя динамическое программирование.

Ваш вопрос очень похож на этот вопрос. Вам нужно назначить каждое пустое значение сетки 1 и каждое значение сетки-монстра -INF. Затем, после того как вы примените решение максимальной суммы матриц, вы получите максимальную площадь.

источник

2014-01-06 06:33:57 songlj

Как уменьшить его до этой проблемы? Может, пожалуйста, помогите – user3086701

Например, в вашем примере карта становится ((1,1, -INF, -INF, 1), (- INF, 1,1, -INF, 1), (1, -INF, 1,1,1), (- INF, -INF, 1,1,1)). Тогда вы можете применить максимальное решение матричной суммы. – songlj

@songlj Удалить ответ, потому что это вопрос из конкурса программирования ongiong –

Максимальный размер прямоугольника без монстров

ответ

Смежные вопросы