Динамическое программирование - Теория графов

Question

Вы в большой сетке NxN с (2 < < = N = 100), пронумерованных от (1, 1) до (N, N). Каждая из этих комнат, кроме (1,1), считается повернутой 'off'. Ваша цель - включить как можно больше комнат.

Вы начинаете в комнате (1,1), единственной комнате, изначально «включенной». В некоторых номерах вы найдете переключатели освещения, которые вы можете использовать для переключения состояния в другие комнаты; например, может быть переключатель в комнате (1,1), который переключает состояние комнаты (1,2) между включением и выключением. Вы можете путешествовать только по комнатам 'on' и может только перемещаться из комнаты (x, y) в своими четырьмя соседними соседями (x-1, y), (x + 1, y), (x, y- 1) и (x, y + 1) (или , возможно, меньше соседей, если эта комната находится на границе сетки).

Найти максимальное количество комнат, в которые вы можете включить 'on'.

Пример: первая строка ввода содержит целые числа N и M (1≤M≤20,000).

В следующих строках M каждый описывают единый выключатель света с четырьмя целых чисел х, у, а, б, что переключатель в комнате (х, у) может быть использована для переключения состояние, в комнате (а, б). В любой комнате могут присутствовать несколько коммутаторов, и несколько переключателей могут переключать состояние любой комнаты.

Выход: единственная линия, предоставляющая максимальное количество комнат, которые вы можете повернуть 'on'.

SAMPLE INPUT:

3 6 
1 1 1 2 
2 1 2 2 
1 1 1 3 
2 3 3 1 
1 3 1 2 
1 3 2 1 

SAMPLE OUTPUT:

Я работал этот пример, на мой собственный. Максимальный случай, который я нашел, - это когда вы находитесь (1,1), включаете (1,2) и (1,3). Затем переходите к (1,3) и включайте (2,1). Затем вы направляетесь в (2,1) и включаете (2,2). Тем не менее, вы не можете добраться до (2,3), поскольку оно все еще повернуто 'из'. Это дает максимум 5 «на» комнатах.

Моего подход до сих пор:

Я подумал, что это может быть либо динамическое программирование или жадными программами. Поскольку границы на N довольно низки, я думал, что каждый раз, когда вы посещаете узел, вы обновляете количество возможных посещенных мест. Там также может быть подход, когда вы только пытаетесь найти места с включенными переключателями и попытаться отправиться туда.

Не могли бы вы указать мне алгоритм для решения этой проблемы и, возможно, некоторый псевдокод, поскольку я немного новичок в этих типах вопросов.

Answer 1

Это может быть разрешено измененным методом поиска по ширине на графиках. Прежде всего, имеет смысл освещен все номера возможны из текущей комнаты. Чтобы осветить максимальное количество комнат, мы должны найти все номера, которые могут быть достигнуты от (1,1) (это означает, что есть путь от (1,1), проходящий через освещенные комнаты), а затем освещенные комнаты являются союзом из всех комнат, которые могут быть освещены из каждой из этих «доступных» комнат. Мы исследуем доступные номера один за другим и находим номера, которые можно осветить. Это потенциально может дать нам более доступные комнаты.

Полный pseudo-code является:

queue Q 
Q.push (1,1) // room (1,1) reachable 
set litupRooms 
litupRooms.push(1,1) // room (1,1) is lit up 
set visitedRooms 
while (Q is not empty) 
    room r = Q.pop() 
    if r is in visitedRooms 
    continue 
    add r to visitedRooms 
    for every room that can be lit up from r 
    if it is already lit up 
     continue 
    add it to litupRooms 
    push it to Q if it is adjacent to a room already visited 
    for every adjacent room of r 
    push it to Q if it is lit up and not visited 
return the size of litupRooms