1

Всем привет. На сайте hackerrank.com существует задача под названием GridWalking. вот здесь. Задача адски сложная. Я приведу ее краткое описание.

Вы находитесь в N-мерном массиве в позиции [X1][X2][...][Xn]. Измерения в массиве выражены через (D1, D2,..., Dn). За один шаг вы можете продвинуться на одну позицию вперед или назад в любом из N измерений. Так что всегда 2 х N различных вариантов шагов. Как много вариантов есть у вас, чтобы сделать М шагов так чтобы вы не покинули пределы массива?

Так вот. У меня есть решение этой задачи. Оно выглядит следующим образом:

int getWays(vector<int> x, vector<int> d, int M) {
int N = d.size();

long long md[M + 1][N + 1];
for (int i = 0; i < N; i++) {
    long long m[d[i] + 1][M + 1];
    int D = d[i];

    for (int j = 1; j <= D; j++)
        m[j][0] = 1;

    for (int n = 1; n <= M; n++) {
        for (int j = 1; j <= D; j++) {
            m[j][n] = 0;
            if (j - 1 > 0)
                m[j][n] = (m[j][n] + m[j - 1][n - 1]) % MOD;
            if (j + 1 <= D)
                m[j][n] = (m[j][n] + m[j + 1][n - 1]) % MOD;
        }
    }

    md[0][i + 1] = 1;
    for (int j = 1; j <= M; j++)
        md[j][i + 1] = m[x[i]][j];
}

long long c[M + 1][M + 1];
for (int i = 0; i <= M; i++) {
    c[i][0] = 1;
    c[i][i] = 1;
}
for (int i = 1; i <= M; i++)
    for (int j = 1; j < i; j++)
    c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;

long long mdt[M + 1][N + 1];
for (int i = 0; i <= M; i++)
    mdt[i][1] = md[i][1];
for (int i = 0; i <= N; i++)
    mdt[0][i] = 1;

for (int i = 2; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        mdt[j][i] = 0;
        for (int k = 0; k <= j; k++)
            mdt[j][i] =
                (mdt[j][i] +
                 ((c[j][j - k] *
                   ((mdt[k][i - 1] * md[j - k][i]) % MOD)) % MOD)) % MOD;
    }
}

return mdt[M][N];
}

но даже изучив не один десяток раз эту функцию я не понимаю ПОЧЕМУ она так работает и чем руководствовался ее автор при решении задачи. В основе решения этой задачи, по всей видимости, лежит ряд математических принципов, неведомых мне.

Буду крайне признателен за любую помощь.

6
  • Даже не читая условие задачи и глядя только на код, могу сказать что это задача на динамическое программирование.
    – iksuy
    22 мар 2016 в 11:24
  • Вам необходимо описание именно этого алгоритма, или Вас устроит предложение другого алгоритма с рекурсией например? И вот вопрос можно ли наступать на одну и туже клетку 2 раза подряд? 22 мар 2016 в 11:24
  • @iksuy да, это динамическое программирование. к сожалению в нем я полный ноль
    – J. Doe
    22 мар 2016 в 11:26
  • @ДмитрийЧистик меня устроит любой вариант. на одну и ту же клетку наступать можно, но предварительно с нее надо сойти. если я стою на клетке 0 (представим что я в одномерном массиве) - то я могу стать на клетку 1, затем опять на 0, а затем опять на 1
    – J. Doe
    22 мар 2016 в 11:28
  • а что значит "вперед или назад" а лево-право? 22 мар 2016 в 11:29

1 ответ 1

1

Ну вот накидал немного, если надо - объясню.

Да, по скольку решение "в лоб" при больших значениях значительно подвисает.

//Возвращает количество возможных шагов M в N мерном массиве заданном размером D[N] начиная с шага X[N], step указывает номер текущего шага
static int Step(int[] D, int[] X, int N, int M, int step = 0, string patch= "")
{
  patch += "(" + string.Join(",", X) + ")";
  //Ну дальше нам шагать не надо мы пришли к ларьку с пивасом т.е. вариант один, стоять (вернуть 1).
  if (step >= M) 
  {
    Console.WriteLine(patch);
    return 1; 
  }
  //Значит начиная с этой клетки начинаем считать шаги
  int steps = 0;
  for (int i = 0; i < N; ++i)
  {
    //запоминаем наше положение в пространстве
    int x = X[i];
    //Можем по i оси переться в сторону уменьшение
    if (x > 0)
    {
      //Премся
      X[i] = x - 1; 
      //Выясняем сколько возможных вариантов у нас есть если идти дальше.
      steps += Step(D, X, N, M, step + 1, patch);
    }
    //Можем по i оси переться в сторону увеличения
    if (x < D[i]-1)
    {
      //Премся
      X[i] = x + 1;
      //Выясняем сколько возможных вариантов у нас есть если идти дальше.
      steps += Step(D, X, N, M, step + 1, patch);
    }
    //Ну и возвращаем начальное значение координат
    X[i] = x;
  }
  //Возвращаем количество шагов
  return steps;
}

static void Main(string[] args)
{
  int N = 5;
  int M = 2;
  int[] D = new int[N];
  int[] X = new int[N];
  for (int i = 0; i < N; ++i)
  {
    D[i] = 10;
    X[i] = 5;
  }
  Console.WriteLine(Step(D, X, N, M));
  Console.ReadKey();
}
15
  • Дмитрий, спасибо большое за помощь. Будьте добры, объясните ваш алгоритм, пожалуйста.
    – J. Doe
    22 мар 2016 в 11:50
  • Ща накатаю комментарии.. Позже выложу 22 мар 2016 в 11:51
  • С тебя магарыч камрад =) 22 мар 2016 в 12:00
  • щас перегоню в плюсы - если все работает - то за мной не заржавеет. и магарыч, и все что хочешь.
    – J. Doe
    22 мар 2016 в 12:02
  • Сразу замечу - время работы алгоритма катастрофически возрастает с размерностью системы! 22 мар 2016 в 12:03

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.