C語言使用深度優(yōu)先搜索算法解決迷宮問題(堆棧)
更新時間:2017年09月15日 08:57:27 作者:e421083458
這篇文章主要介紹了C語言使用深度優(yōu)先搜索算法解決迷宮問題,涉及C語言堆棧的使用與深度優(yōu)先算法解決迷宮問題的相關(guān)操作技巧,需要的朋友可以參考下
本文實例講述了C語言使用深度優(yōu)先搜索算法解決迷宮問題。分享給大家供大家參考,具體如下:
深度優(yōu)先搜索
偽代碼
(Pseudocode)如下:
將起點標記為已走過并壓棧; while (棧非空) { 從棧頂彈出一個點p; if (p這個點是終點) break; 否則沿右、下、左、上四個方向探索相鄰的點 if (和p相鄰的點有路可走,并且還沒走過) 將相鄰的點標記為已走過并壓棧,它的前趨就是p點; } if (p點是終點) { 打印p點的坐標; while (p點有前趨) { p點 = p點的前趨; 打印p點的坐標; } } else 沒有路線可以到達終點;
C語言代碼:
#include <stdio.h> #define MAX_ROW 5 #define MAX_COL 5 struct point { int row, col; } stack[512]; int top = 0; void push(struct point p) { stack[top++] = p; } struct point pop(void) { return stack[--top]; } int is_empty(void) { return top == 0; } int maze[MAX_ROW][MAX_COL] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; void print_maze(void) { int i, j; for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) printf("%d ", maze[i][j]); putchar('\n'); } printf("*********\n"); } struct point predecessor[MAX_ROW][MAX_COL] = { {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, }; void visit(int row, int col, struct point pre) { struct point visit_point = { row, col }; maze[row][col] = 2; predecessor[row][col] = pre; push(visit_point); } int main(void) { struct point p = { 0, 0 }; maze[p.row][p.col] = 2; push(p); while (!is_empty()) { p = pop(); if (p.row == MAX_ROW - 1 /* goal */ && p.col == MAX_COL - 1) break; if (p.col+1 < MAX_COL /* right */ && maze[p.row][p.col+1] == 0) visit(p.row, p.col+1, p); if (p.row+1 < MAX_ROW /* down */ && maze[p.row+1][p.col] == 0) visit(p.row+1, p.col, p); if (p.col-1 >= 0 /* left */ && maze[p.row][p.col-1] == 0) visit(p.row, p.col-1, p); if (p.row-1 >= 0 /* up */ && maze[p.row-1][p.col] == 0) visit(p.row-1, p.col, p); print_maze(); } if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) { printf("(%d, %d)\n", p.row, p.col); while (predecessor[p.row][p.col].row != -1) { p = predecessor[p.row][p.col]; printf("(%d, %d)\n", p.row, p.col); } } else printf("No path!\n"); return 0; }
希望本文所述對大家C語言程序設(shè)計有所幫助。
相關(guān)文章
c語言實現(xiàn)從源文件從文本到可執(zhí)行文件經(jīng)歷的過程
這篇文章主要介紹了c語言實現(xiàn)從源文件從文本到可執(zhí)行文件經(jīng)歷的過程,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-07-07C語言中交換int型變量的值及轉(zhuǎn)換為字符數(shù)組的方法
這篇文章主要介紹了C語言中交換int型變量的值及轉(zhuǎn)換為字符數(shù)組的方法,講解了以不同進制將整型數(shù)字轉(zhuǎn)換成字符數(shù)組,需要的朋友可以參考下2016-04-04C語言中操作sqlserver數(shù)據(jù)庫案例教程
這篇文章主要介紹了C語言中操作sqlserver數(shù)據(jù)庫案例教程,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07