Chapter 17: go back to find the entrance to the specified traverse, "ma bu" or horse stance just look greedy, no back to search traversal, "ma bu" or horse stance just look recursive search NXM board

//Backtracking to explore the horse-step traversal of the specified entry
int main()
{
    
	int i, j, k, m, n, q, u, v, z;
	int d[20][20] = {
     0 }, x[400] = {
     0 }, y[400] = {
     0 }, t[400] = {
     0 };
	int a[9] = {
     0, 2, 1, -1, -2, -2, -1, 1, 2 };
	int b[9] = {
     0, 1, 2, 2, 1, -1, -2, -2, -1 }; //as possible8位给a、b赋初值 
	printf("The chessboard is a row of rows and rows of rows,请输入 n, 1：");
	// scanf("%d, %d", &n, &m);
	printf(" The starting point is the mouth linev列,请输入 u,v: ");
	//scanf(" % d, % d", &u, &v);
	n = 3;
	m = 4;
	u = 1;
	v = 1;
	i = 1;
	z = 0;
	x[i] = u;
	y[i] = v;
	d[u][v] = 1;
	while (i > 0)
	{
    
		q = 0; // The starting position is assigned an initial value 1 / Not found yet i + 1 step direction 
		for (k = t[i] + 1; k <= 8; k++)
		{
    
			u = x[i] + a[k];
			v = y[i] + b[k];//探索第kpossible locations 
			if (u > 0 && u <= n && v > 0 && v <= m && d[u][v] == 0)
			{
    
				x[i + 1] = u;
				y[i + 1] = v;
				d[u][v] = i + 1; // The selected position goes first i 1步 
				t[i] = k; //记录第i 1step direction 
				q = 1;
				break;
			}
		}
		if (q == 1 && i == m * n - 1)
		{
    
			z++;
			{
    
				printf(" The first traversal of this horse step%d个解为：\n", z);
				for (j = 1; j <= n; j++) //Output the ergodic solution in 2D 
				{
    
					for (k = 1; k <= m; k++)
						printf("%4d", d[j][k]);
					printf("\n");
				}
			}
			t[i] = d[x[i]][y[i]] = d[x[i + 1]][y[i + 1]] = 0; i--;
		}
		else if (q == 1) i++;
		else {
    
			t[i] = d[x[i]][y[i]] = 0; i--;
		}
	}
	printf("共有%d个解\n", z);
}

//Recursive traversal of the specified entrance and exit 
int k, n, m, x1, yy, z, d[20][20] = {
     0 };
int  main()
{
    
	int g, x, y;
	void tr(int g, int x, int y);
	printf("棋盘为n行m列,请输入n, m: ");
	scanf("%d, %d", &n, &m);
	printf("Specify the entry location（x, y）,请输入 x, y：");
	scanf("%d, %d", &x, &y);
	printf("指定出口位置(x1, yy),请输入 x1, yy： ");
	scanf("%d,%d", &x1, &yy);
	g = 2;
	z = 0;
	d[x][y] = 1; //The starting position is assigned an initial value tr (g, x, y); //调用 
	tr(g, x, y);
	if (z > 0)
		printf(" 共有以上 %d a specified horse stride path.\n", z);
	else
		printf("未找到指定路径！\n");
}
// Specifies a recursive function for the stance path 
void tr(int g, int x, int y)
{
    
	int i, j, u, v, k = 0;
	static int a[9] = {
     0, 2, 1, -1, -2, -2, -1, 1, 2 }; //technology possible8位给a、b赋初值 
	static int b[9] = {
     0, 1, 2, 2, 1, -1,-2,-2, -1 };
	while (k < 8) {
    
		k = k + 1;
		u = x + a[k];
		v = y + b[k]; // Explore the firstk possible locations
		if (u > 0 && u <= n && v > 0 && v <= m && d[u][v] == 0)
		{
    
			d[u][v] = g; // The selected position goes first：步
			if (g == m * n)
			{
    
				if (u == x1 && v == yy)
				{
    
					z++;
					printf("第%dThe specified horse stride path is ：\n ",z);
					for (i = 1; i <= n; i++) // Output a solution in 2D 
					{
    
					for (j = 1; j <= m; j++) printf("%4d", d[i][j]); printf("\n");
					}
				}
				d[u][v] = 0; break;
			}
			else
				tr(g + 1, u, v);
			d[u][v] = 0;
		}
	}
}

//Greedy traversal without backtracking
int main()
{
    
	int i, j, k1, k, m, n, u, v, min;
	int d[20][20] = {
     0 }, x[400] = {
     0 }, y[400] = {
     0 }, t[9] = {
     0 };
	int a[9] = {
     0, 2, 1, -1, -2, -2, -1, 1, 2 };
	int b[9] = {
     0, 1, 2, 2, 1, -1, -2, -2, -1 }; //as possible8位给a、b赋初值 
	//printf("The chessboard is a row of rows and rows of rows,请输入 n, 1：");
	// scanf("%d, %d", &n, &m);
	//printf(" The starting point is the mouth linev列,请输入 u,v: ");
	//scanf(" % d, % d", &u, &v);
	n = 10;
	m = 9;
	u = 1;
	v = 2;
	i = 1;
	x[i] = u;
	y[i] = v;
	d[u][v] = 1;
	
	while (i < m* n)
	{
    
		for (k1 = 0, k = 1; k <= 8; k++)
		{
    
			u = x[i] + a[k];
			v = y[i] + b[k];
			if (u > 0 && u <= n  && v > 0 && v <= m && d[u][v] == 0)
			{
    
				x[i + 1] = u;
				y[i + 1] = v;
				if (i == m * n - 1)break;
				{
    
					t[k] = 0;
					for (j = 1; j <= 8; j++)
					{
    
						u = x[i + 1] + a[j];
						v = y[i + 1] + b[j];
						if (u > 0 && u <= n && v > 0 && v <= m && d[u][v] == 0 && !(u == x[i] && v == y[i]))
							t[k]++;
					}
					if (t[k] == 0) k1++;
				}
			}
			else {
     t[k] = 0; k1++; continue; }
		}
		if (k1 == 8)return 0;
		if (i < m * n - 1)
		{
    
			min = 8;
			for (k = 1; k <= 8; k++)
				if (t[k] > 0 && t[k] < min)
				{
    
					min = t[k];
					k1 = k;
				}
			u = x[i] + a[k1];
			v = y[i] + b[k1];
			x[i + 1] = u;
			y[i + 1] = v;
		}

		d[u][v] = i + 1;
		if (i == m * n - 1)
		{
    
			printf(" %d行%dA horse-step traversal of the column\n", n, m);
			for (j = 1; j <= n; j++)
			{
    
				for(k =1; k <= m; k++)
				printf("%4d", d[j][k]);
				printf("\n");
			}
			return 0;
		}
		else i++;
	}
}

//Recursive searchnxmCheckerboard with obstacle course traversal 

int k, n, m, x1, yy, z, d[20][20] = {
     0 };
int main()
{
    
	int g, q,x, y;

	int  tr(int g, int x, int y);
	printf("棋盘为n行m列,请输入n, m: ");
	scanf("%d, %d", &n, &m);
	printf("Please specify the obstacle location Please enter x1, yy：");
	scanf("%d, %d", &x1, &yy);
	
	g = 2;
	z = 0;
	x = 1;
	y = 1;
	d[x][y] = 1;
	q = tr(g, x, y);
	if (z > 0)
		printf(" 共有以上 %d a specified horse stride path.\n", z);
	else
		printf("未找到指定路径！\n");
}
// Horse stance path recursive function 
int tr(int g, int x, int y)
{
    
	int i, j, u, v, k = 0;
	int q = 0;
	static int a[9] = {
     0, 2, 1, -1, -2, -2, -1, 1, 2 }; //technology possible8位给a、b赋初值 
	static int b[9] = {
     0, 1, 2, 2, 1, -1,-2,-2, -1 };
	while (k < 8 && q == 0) {
    
		k = k + 1;
		u = x + a[k];
		v = y + b[k]; // Explore the firstk possible locations
		if (u > 0 && u <= n && v > 0 && v <= m && d[u][v] == 0 && !(u == x1 && v == yy))
		{
    
			d[u][v] = g; // The selected position goes first：步
			if (g == m * n -1)
			{
    
				z++;
				printf("第%dThe specified obstacle course path is ：\n ", z);
				
					for (i = 1; i <= n; i++) // Output a solution in 2D 
					{
    
						for (j = 1; j <= m; j++)
							if (i == x1 && j == yy)
								printf(" x ");
						else
								printf("%4d", d[i][j]);
						printf("\n");
					}
					g = g - 1;
				
			}
			else
				q = tr(g + 1, u, v);
			if (q == 0) d[u][v] = 0;
			if (g == 2 && k == 8) q = 1;
		}
	}
	return q;
}