1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <iostream>
using namespace std;
const int dxh[] = {-2, -2, 2, 2, -1, -1, 1, 1};
const int dyh[] = {-1, 1, -1, 1, -2, 2, -2, 2};
bool in(int i, int j, int n, int m)
{
return i >= 1 && i <= n && j >= 1 && j <= m;
}
int dp[11][11][11];
//dp[cnt][i][j] == количество способов добраться до клетки (i, j) ровно за cnt шагов
int main()
{
int n, k;
cin >> n >> k;
//количство способв добраться до левой нижней клетки сделав о ходов равно 1
dp[0][n][1] = 1;
for(int cnt = 0; cnt < k; cnt++)
{
//перебрали, сколько шагов сделали
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
//перебрали клетку в которой стоим
for(int dir = 0; dir < 8; dir++)
{
//перебрали ход(их 8 штук и они занесены в константу массив где dxh - смещение по строке, dyh - смещение по столбцу
int ni = i + dxh[dir];
int nj = j + dyh[dir];
//теперь (ni, nj) - координаты клетки в которую мы прыгнем
//проверка на то, что мы не вышли за пределы доски с помощью функции
if(in(ni, nj, n, n))
{
//вот мы знаем что до клетки (i, j) за cnt шагов можно добраться dp[cnt][i][j] способами
//значит до клетки (ni, nj) за cnt + 1 шаг надо увеличить на dp[cnt][i][j]
dp[cnt + 1][ni][nj] += dp[cnt][i][j];
}
}
}
}
cout << dp[k][1][n] << endl;
return 0;
} |
