How to use C++ stack-based deep search algorithm to realize horse pedal chessboard

This article mainly introduces how to use C++ stack-based deep search algorithm to achieve horse chessboard, the article is very detailed, has a certain reference value, interested friends must finish!

Horse pedal chessboard (implementation of deep search algorithm based on stack)

To put it simply, starting from any specified square, find a path for the horse to walk through every square of the chessboard and pass only once, which is a simple description of the chessboard.

# include # include # define M8 / / Row # define N8 / / column typedef struct snode / / coordinates {int flag; int x; int y;} stack;typedef struct node {int top; / / record how many steps top+1 int flag; / / record the direction of the previous step stack * p; / / path stack} LNode; LNode * CreateStacke () / create and initialize void Judge (LNode * s, int chess [] [N]); / / determine where to go void Push (LNode * s, stack x); / / enter stack operation void Pop (LNode * s); / / unstack operation int IsFull (LNode * s); / / full int IsEmpty (LNode * s); / / empty int main () {int chess [M] [N] = {0}; / / chessboard int I, j / / the loop variable LNode * step; / / step stores the path step = CreateStacke (); Judge (step, chess); for (I = 0; I

< N; i++){ for (j = 0; j < M; j++){ printf("%2d ", chess[i][j]); } printf("\n"); } return 0;}LNode * CreateStacke(){ LNode * s = (LNode *)malloc(sizeof(LNode)); if (!s){ printf("内存空间不足!\n"); system("pause"); exit(0); } s->

P = (stack *) malloc (sizeof (stack) * M * N); if (! s-> p) {printf ("insufficient memory!\ n"); system ("pause"); exit (0);} s-> top =-1; / / put top at the bottom of the stack return s } void Judge (LNode * s, int chess [] [N]) {int ch [8] [2] = {/ / eight possible directions of a horse {1,-2}, {2,-1}, {2, 1}, {1, 2}, {- 1, 2} {- 2,-1}, {- 1,-2} Int I, j = 1, flag = 1; stack t; printf ("Please enter the initial position of the horse: (% d *% d)\ n", M, N); scanf ("% d% d", & t.y, & t.x); if (T.X N | | t.y N) {printf ("the coordinates entered are out of range! \ n "); exit (0);} t.xmuri; t.yMurmee; chess [t.y] [t.x] = 1; / / Select the first foothold of the horse Push (s, t); while (s-> top)

< M * N - 1 && s->

Top! =-1) {for (I = 0; I

< 8; i++){ t.x = s->

P [s-> top]. X + ch [I] [0]; t. Y = s-> p [s-> top]. Y + ch [I] [1]; / / if its coordinates are not out of range and have not traveled, store the route in the path stack if (t.x > = 0 & & t.y > = 0 & & t.x)

< N && t.y < M && !chess[t.y][t.x]){ if(flag){ //没有退回去 Push(s, t); chess[t.y][t.x] = s->

Top + 1; s-> p [s-> top-1] .flag = I; flag = 1; break;} else {/ / returned if (s-> p [s-> top] .flag

< i){ //重新走时，让它的方向不等于原先的方向 flag = 1; } } } } //如果没有能走的路时，即，所有的路径都超出范围，或者，该位置已经走过了，则，退到上一步，重新选择； if (i == 8){ chess[s->

P [s-> top] .y] [s-> p [s-> top] .x] = 0; Pop (s); flag = 0;}} void Push (LNode * s, stack x) {if (IsFull (s)) {printf ("stack overflow, no stack operation!\ n"); exit (0);} else {s-> top++ S-> p [s-> top] = x;}} void Pop (LNode * s) {if (IsEmpty (s)) {printf ("stack is empty and cannot be unstacked!\ n"); exit (0);} s-> top--;} int IsFull (LNode * s) {if (s-> top > = M * N) {return 1;} else {return 0 }} int IsEmpty (LNode * s) {if (s-> top = =-1) {return 1;} else {return 0;}} above is all the content of this article entitled "how to use C++ stack-based deep search algorithm to realize horse chessboard". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!