您好,登錄后才能下訂單哦!
這篇文章主要介紹如何使用C++基于棧的深搜算法實(shí)現(xiàn)馬踏棋盤(pán),文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
簡(jiǎn)單來(lái)說(shuō),從任意指定方格出發(fā),為馬尋找一條走遍棋盤(pán)每一格并且只經(jīng)過(guò)一次的一條路徑,這就是馬踏棋盤(pán)的簡(jiǎn)單描述。
#include <stdio.h> #include <stdlib.h> #define M 8 //行 #define N 8 //列 typedef struct snode //坐標(biāo) { int flag; int x; int y; }stack; typedef struct node { int top; //記錄走了多少步top+1 int flag; //記錄上一步走的方向 stack * p; //路徑棧 }LNode; LNode * CreateStacke(); //創(chuàng)建,并初始化 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}; //棋盤(pán) int i, j; //循環(huán)變量 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èi)存空間不足!\n"); system("pause"); exit(0); } s->p = (stack *)malloc(sizeof(stack) * M * N); if (!s->p){ printf("內(nèi)存空間不足!\n"); system("pause"); exit(0); } s->top = -1; // 把top放在棧底 return s; } void Judge(LNode * s, int chess[][N]) { int ch[8][2] = { //馬可能走的八個(gè)方向 {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("請(qǐng)輸入馬的初始位置:(%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("輸入的坐標(biāo)超出范圍!\n"); exit(0); } t.x--; t.y--; chess[t.y][t.x] = 1; //選擇馬的第一個(gè)落腳點(diǎn) 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]; //如果它的坐標(biāo)沒(méi)有超出范圍,并且沒(méi)有走過(guò),則把該路線存入路徑棧 if (t.x >= 0 && t.y >= 0 && t.x < N && t.y < M && !chess[t.y][t.x]){ if(flag){ //沒(méi)有退回去 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){ //重新走時(shí),讓它的方向不等于原先的方向 flag = 1; } } } } //如果沒(méi)有能走的路時(shí),即,所有的路徑都超出范圍,或者,該位置已經(jīng)走過(guò)了,則,退到上一步,重新選擇; 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("棧上溢,不能進(jìn)行入棧操作!\n"); exit (0); } else{ s->top++; s->p[s->top] = x; } } void Pop(LNode * s) { if (IsEmpty(s)){ printf("棧為空,不能進(jìn)行出棧操作!\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; } }
以上是“如何使用C++基于棧的深搜算法實(shí)現(xiàn)馬踏棋盤(pán)”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對(duì)大家有幫助,更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。