Shulou(Shulou.com)06/01 Report--

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!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.