In general, we need an algorithm for the problem , which is written below.

Here is my idea: the idea is for O(N^2) , the base of the dynamics is dp[0][0] = 1 , and then we simply run through the cells, and write the sum of the cell values ​​from which we can get into this cell in each cell, i.e. dp[i][j] = dp[i - 2][j - 1] + dp[i - 2][j + 1] ...

And it does not work. I even know why, but I don’t know how to fix it.

Given a rectangular N × M board (N rows and M columns). In the upper left corner is a chess knight, which must be moved to the lower right corner of the board. In this case, a horse can only walk: 2 squares to the right and one, either up, or down, or 2 squares down and one, either to the right or to the left.

It is necessary to determine how many different routes exist leading from the upper left to the lower right corner.

Input file format
The first line of the input file contains two positive integers N and M (1 ≤ N, M ≤ 15).

Output file format
In the output file output a single number of ways to get a horse to the lower right corner of the board.

Вх. данные Выход 15 14 7884330

  • > And it does not work. I even know why, but I don’t know how to fix it. So why? - eigenein
  • because when we interrupt, for example, on line 2, the value of the first line can change, due to the fact that you can walk up and up! those. You can return to the starting position! - Eugene536
  • 2
    can not walk along the lines, but moving the secondary diagonal where i + j = const - Yura Ivanov
  • skip cells that you have already processed, - so you get rid of recursions - jmu
  • 2
    here is the solution on javascript =) - Yura Ivanov

1 answer 1

In general, I solved this problem, thank you all! Especially @Yura Ivanov for an interesting solution! Decided "Lazy dynamics." Below is the C ++ code:

 #define FOR(a, k, b) for(int a = k; a < b; a++) void initial() { FOR(i, 0, n) FOR(j, 0, m) dp[i][j] = -1; dp[0][0] = 1; } bool good(int i, int j) { return (i >= 0) && (j >= 0) && (i < n) && (j < m); } int solve(int i, int j) { if (good(i, j)) { if (dp[i][j] == -1) dp[i][j] = solve(i - 2, j - 1) + solve(i - 2, j + 1) + solve(i - 1, j - 2) + solve(i + 1, j - 2); } else return 0; return dp[i][j]; } int main() { initial(); printf("%d", solve(n - 1, m - 1)); return 0; }
  • You have an interesting macro. - Costantino Rupert
  • Macros - cool stuff of course. I don’t even know if it’s good or bad that they don’t fit into the concept of java ... - jmu