Водопад Рок Хит Счетчик - PullRequest
Новая
       40

Водопад Рок Хит Счетчик

0 голосов
/ 11 мая 2018

У меня трудности с решением проблемы из моего класса, речь идет о динамическом программировании (или так назвал мой профессор). Проблема называется «Хит водопада». (Ограничение по времени: 1 с, ограничение по памяти: 16 МБ)

Нам даны верхняя левая (v1, h1) и нижняя правая координаты (v2, h2) камня, и мы моделируем водопад и подсчитываем количество камней, попавших под воду, представьте, что вода начала падать с координаты (x, y), он упадет до (x-1, y) и продолжит падать, пока не достигнет скалы. когда он попадает в скалу, вода будет расщепляться вправо и влево и следовать длине скалы, вот изображение того, как будет работать алгоритм. Имитация изображения .

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

Вот фрагмент моего неполного кода, где я все еще думаю о втором условии, когда вода попадает в скалу и предотвращает двойной счет. 

int maks=0, n, m, nstone;
struct a{
   int v1, v2, h1, h2; //coordinates
   bool pass; //passed or not?
}; a arr[5000];

bool acompare(a lhs, a rhs){
   return  lhs.v1 < rhs.v1; //compare height descending
}

int fall(int x, int y){
   if (x == n || y == m || y == -1) //if the water passed the wall
      return 0;
   else if () //the confusing condition if the water hit the rock
      return 1 + fall(x, h1-1) + fall(x, h2+1));
   else // if there's nothing below
      return fall(x-1, y);
}

int main(){
   cin>> n>> m>> nstone; //waterfall size (n*m) and number of stone
   for (int i=0; i<nstone; i++){ //read the stone's corner
      cin>> arr[i].v1>> arr[i].h1>> arr[i].v2>> arr[i].h2; 
      arr[i].pass = false;
   }

   sort(arr, arr+nstone, acompare); //sort the stone's based on height
   cin>> start; //read the start point of the water
   cout<< fall(start, m)<< endl;

   return 0;
}

Пример ввода теста: 

6 6 3  
2 3 2 4  
4 2 5 2  
5 5 6 5

вывод: 

3

Ответы [ 2 ]

0 голосов
/ 13 мая 2018

Во-первых, состояние, с которым у вас проблемы.Неэффективно повторять все камни на каждом шаге, даже бинарный поиск не оптимален.Это можно решить с помощью стола, как в настольной игре.Создайте для этого 2D-массив NxM (например, 4 байта каждого элемента = 250000 * 4 байта = 2 МБ, далеко от вашего предела в 16 МБ) и отметьте все точки, покрытые камнями.На каждом шаге вам нужно проверять одну точку, если это камень.

Во-вторых, это проблема DP, потому что потоки могут сливаться, как в середине: 

..|..
.|X|.
.|.|.
|X|X|
|.|.|

Ваш подход рассчитал бы этот поток дважды.(Кстати, я не вижу, где вы используете своего bool pass; //passed or not? участника). После расчета сохраните количество камней, попавших в стрим в вашем столе настольной игры, например, в вашем примере: 

.1331.
.1XX1.
010.1.
0X0010
0X00X0
0.00X0

ИтакКогда вы достигнете уже рассчитанной точки потока, вы уже знаете, сколько камней вы ударили из этой точки.

0 голосов
/ 11 мая 2018

Я вижу, что вы не используете std::vector и вместо этого используете массив в стиле C.Я предполагаю, что вы не знакомы с библиотекой C ++ STL и, следовательно, предоставите ответ, который использует как можно меньше C ++ STL.

Поскольку необходимо проверить несколько камней, вам необходимо использоватьцикл (или std::find_if), чтобы проверить их все. 

for(int stone_index=0;stone_index<nstone;++stone_index)

Для каждого камня проверьте, находится ли координата (x,y) прямо на вершине этого камня.

Один разВы нашли один, гарантированно, что вы не найдете других (потому что камни не касаются), поэтому просто вернитесь немедленно. 

return 1 + fall(x, h1-1) + fall(x, h2+1));

(это просто псевдокод, замените h1и h2 с подходящими значениями)

Если вы достигли конца цикла, не найдя камень, 

// if there's nothing below
return fall(x-1, y);

Обратите внимание, что для этого решения требуется nstone шагов для проверки, вы можете сделать лучше, используя std::map или что-то.Это может быть слишком сложно для вас.

...