Routine solution - the problem of horse walking on the chessboard

subject ： The chess board assumes a horizontal line 10 strip , A vertical bar 9 strip ; The lower left corner is the position origin (0,0); Suppose the horse is now at the origin , jump 10 Time just jumps to (7,7) How many jumping methods are there ;

• Recursive writing
• code

// Brute force recursive algorithm 
// chess " Horse " from (0,0) Let's go and jump rest Step by step (aim_x,aim_y) How many measurements are there 
// Look at it in reverse (aim_x,aim_y) To (0,0) How many jumps are there 
//cur_x,cur_y Indicates chess " Horse " Now the difference from the target position 

int get_N1(int cur_x, int cur_y, int rest)
{
    
	// Chess cannot cross the line , Out of bounds means that this method is invalid 
	if (cur_x > 8 || cur_x < 0 || cur_y < 0 || cur_y > 9)
		return 0;
	// The steps are just finished 
	if (rest == 0)
	{
    
		// The target position is not reached 
		if (cur_x !=0 || cur_y != 0)
			return 0;
		// Get to the target position 
		return 1;
	}
	// There are still steps left 
	int p1 = get_N1(cur_x + 1, cur_y + 2, rest - 1);
	int p2 = get_N1(cur_x + 1, cur_y - 2, rest - 1);
	int p3 = get_N1(cur_x - 1, cur_y + 2, rest - 1);
	int p4 = get_N1(cur_x - 1, cur_y - 2, rest - 1);
	int p5 = get_N1(cur_x + 2, cur_y + 1, rest - 1);
	int p6 = get_N1(cur_x + 2, cur_y - 1, rest - 1);
	int p7 = get_N1(cur_x - 2, cur_y + 1, rest - 1);
	int p8 = get_N1(cur_x - 2, cur_y - 1, rest - 1);
	return p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;
}

You can think of the recursive solution as an octree ; The node asked eight children for information

• Strict table structure solution

This is a three-dimensional dp Array , according to basecase You can get dp[0][0][0] = 1;
dp[i][j][0] stay i,j When not all are zero , by 1; Fill in part first dp; Then according to the location dependency , Specify the traversal order of the axes , And the traversal order of each axis

• code

// Strict table structure 
int getValue(vector<vector<vector<int>>>& dp, int x, int y, int z)
{
    
	if (x < 0 || x > 8 || y < 0 || y > 9 || z < 0)
	{
    
		return 0;
	}
	return dp[x][y][z];
}

int get_N3(int cur_x, int cur_y, int rest)
{
    
	if (cur_x > 8 || cur_x < 0 || cur_y < 0 || cur_y > 9 || rest < 0)
		return 0;
	vector<vector<vector<int>>>  dp(9, vector<vector<int>>(10, vector<int>(rest+1,0)));
	dp[0][0][0] = 1;
	for (int z = 1; z  <= rest; z++)
	{
    
		for (int x = 0; x < 9; x++)
		{
    
			for (int y = 0; y < 10; y++)
			{
    
				dp[x][y][z] += getValue(dp, x - 1, y - 2, z - 1);
				dp[x][y][z] += getValue(dp, x - 1, y + 2, z - 1);
				dp[x][y][z] += getValue(dp, x + 1, y - 2, z - 1);
				dp[x][y][z] += getValue(dp, x + 1, y + 2, z - 1);
				dp[x][y][z] += getValue(dp, x - 2, y - 1, z - 1);
				dp[x][y][z] += getValue(dp, x - 2, y + 1, z - 1);
				dp[x][y][z] += getValue(dp, x + 2, y - 1, z - 1);
				dp[x][y][z] += getValue(dp, x + 2, y + 1, z - 1);
			}
		}
	}
	return dp[cur_x][cur_y][rest];
}