C++基於棧的深搜算法實現馬踏棋盤
馬踏棋盤(基於棧的深搜算法實現)
簡單來說,從任意指定方格出發,為馬尋找一條走遍棋盤每一格並且隻經過一次的一條路徑,這就是馬踏棋盤的簡單描述。
話不多說,代碼如下,要是有什麼不懂的地方,歡迎討論~
#include <stdio.h> #include <stdlib.h> #define M 8 //行 #define N 8 //列 typedef struct snode //坐標 { int flag; int x; int y; }stack; typedef struct node { int top; //記錄走瞭多少步top+1 int flag; //記錄上一步走的方向 stack * p; //路徑棧 }LNode; LNode * CreateStacke(); //創建,並初始化 void Judge(LNode * s, int chess[][N]); //判斷往哪走 void Push(LNode * s, stack x); //入棧操作 void Pop(LNode * s); //出棧操作 int IsFull(LNode * s); //判滿 int IsEmpty(LNode * s); //判空 int main() { int chess[M][N] = {0}; //棋盤 int i, j; //循環變量 LNode * step; //step存的是走的路徑 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("內存空間不足!\n"); system("pause"); exit(0); } s->top = -1; // 把top放在棧底 return s; } void Judge(LNode * s, int chess[][N]) { int ch[8][2] = { //馬可能走的八個方向 {1, -2}, { 2, -1}, {2, 1 }, { 1, 2 }, {-1, 2}, {-2, 1 }, {-2, -1},{-1, -2} }; int i, j = 1, flag = 1; stack t; printf("請輸入馬的初始位置:(%d * %d)\n", M, N); scanf("%d%d", &t.y, &t.x); if (t.x <= 0 || t.x > N || t.y <= 0 || t.y > N){ printf("輸入的坐標超出范圍!\n"); exit(0); } t.x--; t.y--; chess[t.y][t.x] = 1; //選擇馬的第一個落腳點 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 (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{ //退回去瞭 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("棧上溢,不能進行入棧操作!\n"); exit (0); } else{ s->top++; s->p[s->top] = x; } } void Pop(LNode * s) { if (IsEmpty(s)){ printf("棧為空,不能進行出棧操作!\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; } }
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。