求C语言迷宫程序的解释说明！！！

我看了一下,算法应该是一样的,下面是我以前用C++写的

相信你能看得懂

/////////////////////////

/////////迷宫求解////////

//////作者:baihacker/////

/////时间:11102006/////

/////////////////////////

/class:

Matrix:矩阵类

offsets:搜索偏移

enum directions:四个方向

struct item:搜索节点

Migong:迷宫类

1创建一个Migong对象

2使用用Create方法输入数据

3使用Solve方法进行求解

4ShowSolve方法显示解

5可以重复使用Create方法

6入口只能在左上角

7默认出口在右下角

ShowAllPath:穷举所有的路径

备注:

由于算法原因,这里的所有路径应该是指

介于:

a如果两条路存在某个点不同那么就是不同的路

b如果在一条路中去掉一个或者一个以上的圈,那么他们是同一条路

之间意义上的路

/

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

#ifndef MIGONG_H

#define MIGONG_H

///////////////////

///////矩阵类//////

///////////////////

class Matrix{

int m;

int row, col;

bool iscreate;

public:

Matrix(){m=0;iscreate=false;};

~Matrix() {Release();};

bool Create(int, int);

int& operator () (int, int);

int GetRow(){return row;};

int GetCol(){return col;};

void Release();

void Show(char, char );

};

bool Matrix::Create(int r, int c)

{

if( r<=0 || c<=0) return false;

Release();

row = r;

col = c;

m = new int[rowcol];

for (int i=0;i<rowcol;i++)

{

(m+i) = 0;

}

iscreate = true;

return true;

}

int& Matrix::operator ()(int r, int c)

{

return (m+rcol+c);

}

void Matrix::Release()

{

if (iscreate)

{

row = col = 0;

if (m) delete[] m;

m = 0;

}

iscreate = false;

}

void Matrix::Show(char blk='#', char nblk=' ')

{

int i, j;

for (i=0;i<row;i++)

{

for (j=0;j<col;j++)

{

if ((m+icol+j) == 0)

cout<<nblk;

else

cout<<blk;

}

cout<<endl;

}

}

/////////////////////////////

////迷宫相关数据结构的定义///

/////////////////////////////

struct offsets{

int a, b;

};

enum directions{

_S = 0,

_E,

_N,

_W

};

struct item{

int row, col, dir;

};

class Migong{

static offsets move[4];

Matrix maze;

Matrix mark;

int row;

int col;

int desr;

int desc;

stack<item> stk;

bool iscreate;

int pathlength;

bool GetPath();

bool IsInPath(int, int);

public:

Migong(){issolved=false;result=0;pathlength=row=col=0;iscreate=false;};

~Migong(){Release();};

bool Create(int , int , int , int , int );

void Solve();

void Release();

void OutputMaze();

void ShowSolve(char, char );

public:

bool issolved;

item result;

};

offsets Migong::move[4]={ {1, 0}, {0, 1},

{-1, 0}, {0, -1}};

////////////////////////////

//迷宫数据应该是不含边框的//

////////////////////////////

bool Migong::Create(int m, int r, int c, int desrow=-1, int descol=-1)

{

if (r<=0 || c<=0) return false;

Release();

if (desrow==-1 || descol==-1)

{

desr = r;

desc = c;

}

else

{

desr = desrow;

desc = descol;

}

row = r;

col = c;

mazeCreate(r+2, c+2);

markCreate(r+2, c+2);

int i, j;

for (i=0;i<r+2;i++)

{

for (j=0;j<c+2;j++)

{

if (j==0 || j==c+1 || i==0 || i==r+1)

{

mark(i, j) = maze(i, j) = 1;

}else

{

mark(i, j) = 0;

maze(i, j) = m[((i-1)col+j-1)];

}

}

}

return iscreate = true;

}

bool Migong::GetPath()

{

mark(1,1) = 1;

item temp;

tempcol = 1;

temprow = 1;

tempdir = _S;

stkpush(temp);

while (!stkempty())

{

temp = stktop();

stkpop();

int i = temprow;

int j = tempcol;

int d = tempdir;

while (d<4)

{//根据当前点的状态确定下一个搜索点

int g = i + move[d]a;

int h = j + move[d]b;

if (g==desr && h==desc)

{

return true;

}

//如果这个点不是障碍点且没有被搜索过那么可以对这个点进行搜索

if (maze(g, h)==0 && mark(g, h)==0)

{

mark(g, h) = 1;

temprow = g;

tempcol = h;

tempdir = d+1;

stkpush(temp);

i = g;

j = h;

d = _S;//对一下个点进行搜索

}

else d++;

}

}

return false;

}

void Migong::Solve()

{

issolved = GetPath();

if (issolved)

{

pathlength = stksize();

result = new item[pathlength];

for (int i=0;i<pathlength;i++)

{

(result+i) = stktop();

stkpop();

// cout<<"("<<((result+i))row<<","<<((result+i))col<<")"<<endl;

}

}

while (!stkempty())

stkpop();

}

void Migong::Release()

{

if (iscreate)

{

mazeRelease();

markRelease();

row=col=0;

if (result)

delete [] result;

result = 0;

while (!stkempty())

stkpop();

}

iscreate = false;

issolved = false;

pathlength = 0;

}

void Migong::OutputMaze()

{

if (!iscreate) return;

mazeShow();

}

bool Migong::IsInPath(int r, int c)

{

if (!iscreate || !issolved)

return false;

item temp;

for (int i=0;i<pathlength;i++)

{

temp = (result+i);

if ((temprow==r) && (tempcol==c))

return true;

}

return false;

}

void Migong::ShowSolve(char blk='#',char s='o')

{

if (!iscreate) return;

if (!issolved)

{

cout<<"无解"<<endl;

}

else

{

int i, j;

for (i=0;i<row+2;i++)

{

for (j=0;j<col+2;j++)

{

if ((i==1 && j==1) || (i==desr && j==desc))

{

cout<<s;

}

else if (maze(i, j) == 1)

{

cout<<blk;

}else

{

if (IsInPath(i, j))

cout<<s;

else

cout<<' ';

}

}

cout<<endl;

}

}

}

//////////////////////

//////穷举所有路径////

//////////////////////

offsets move[4]={ {1, 0}, {0, 1},

{-1, 0}, {0, -1}};

struct node

{

int row,col;

};

vector<node> path;

int count;

bool IsReachable( Matrix& maze, Matrix& mark, node beg, node des)

{

if (begrow==desrow&&begcol==descol)

{//如果达到的话那么显示路径

count++;

cout<<"第"<<count<<"条路径:"<<endl;

for (int i=0;i<pathsize();i++)

cout<<"("<<path[i]row<<","<<path[i]col<<")";

cout<<"("<<desrow<<","<<descol<<")";

cout<<endl;

return false;

}

if (maze(begrow, begcol)==1 || mark(begrow, begcol)==1)

{

return false;

}

pathpush_back(beg);

mark(begrow, begcol) = 1;

node nextnode;

for (int i=_S;i<_W+1;i++)

{

nextnoderow = begrow + move[i]a;

nextnodecol = begcol + move[i]b;

IsReachable(maze, mark, nextnode, des);

}

pathresize(pathsize()-1);

mark(begrow, begcol) = 0;

return false;//如果不是穷举的话应该根据for循环的结果重新设置返回值

}

/

参数maze,mark为迷宫长宽均加二的矩阵

desr,desc为出口点

/

void FindAllPath( Matrix& maze, Matrix& mark, int desr, int desc)

{

node first, last;

firstrow = 1;

firstcol = 1;

lastrow = desr;

lastcol = desc;

IsReachable(maze, mark, first, last);

pathclear();

}

/

m迷宫矩阵数据

r,c行和列的大小

desr,desc目标位置

/

void ShowAllPath(int m, int r, int c, int desr=-1, int desc=-1)

{

Matrix maze, mark;

mazeCreate(r+2, c+2);

markCreate(r+2, c+2);

if (desr==-1 || desc==-1)

{

desr = r;

desc = c;

}

int i, j;

for (i=0;i<r+2;i++)

{

for (j=0;j<c+2;j++)

{

if (j==0 || j==c+1 || i==0 || i==r+1)

{

mark(i, j) = maze(i, j) = 1;

}else{

mark(i, j) = 0;

maze(i, j) = m[((i-1)c+j-1)];

}

}

}

count = 0;

FindAllPath(maze, mark, desr, desc);

mazeRelease();

markRelease();

}

#endif

#include <stdioh> #include <memh> void main() { int a[100][100]; //0:blocked 1:passage 2:finish -1:visited; int b[10000][2]; int m=0,n=0; int sttop=0; int i,j,k,l; memset(a,0,sizeof(a)); printf("Please Input m,n:"); scanf("%d%d",&m,&n); printf("Input the start:"); scanf("%d%d",&i,&j); b[0][0]=i-1; b[0][1]=j-1; printf("Input the Map:\n"); for (i=0;i<m;i++) for (j=0;j<n;j++) { scanf("%d",&a[i][j]); } printf("Input the Finish:"); scanf("%d%d",&i,&j); a[i-1][j-1]=2; i=b[sttop][0];j=b[sttop][1]; a[i][j]=-1; while (sttop!=-1) { if (i>0) { //can up if (a[i-1][j]==1) { a[--i][j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i-1][j]==2) { b[++sttop][0]=--i; b[sttop][1]=j; break; } } if (i<m-1) { //can up if (a[i+1][j]==1) { a[++i][j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i+1][j]==2) { b[++sttop][0]=++i; b[sttop][1]=j; break; } } if (j>0) { //can left if (a[i][j-1]==1) { a[i][--j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i][j-1]==2) { b[++sttop][0]=i; b[sttop][1]=--j; break; } } if (j<m-1) { //can up if (a[i][j+1]==1) { a[i][++j]=-1; b[++sttop][0]=i; b[sttop][1]=j; continue; }else if (a[i][j+1]==2) { b[++sttop][0]=i; b[sttop][1]=j++; break; } } sttop--; } if (sttop+1) { for (i=0;i<sttop;i++) printf("(%d,%d)->",b[i][0]+1,b[i][1]+1); printf("(%d,%d)\n",b[i][0]+1,b[i][1]+1); } else printf("Can't Reach The Finish Spot!\n"); return; } 用非嵌套的方法做的栈，起点 终点自己定 输入数据规则如下： 先输入m n（m为行数，n为列数） 再输入起点(最左上角为(1,1)（前者行号，后者列号）则输入"1 1"（不含引号）其他依次类推) 再输入地图(0为被阻挡，1为通路)（起点被默认为通路，无论输入0还是1） 再输入终点（规则和起点一样） 回车后出结果，结果的表达方式以(x,y)->(x,y)->->(x,y)（坐标任以1，1为左上角） 或者Can't Reach The Finish Spot! 呈现 其他的修改的话可以随便咯（规模m,n<=100，太大栈放不下了）

//寻路_带权重_带障碍_最短_文件地图_不闪------wlfryq------//

#include <stdioh>

#include <stdlibh>

#include <stringh>

#include <windowsh>

typedef struct

{

int x;

int y;

} _PT;

_PT pt;

int row=0,col=0;

//设置CMD窗口光标位置

void setxy(int x, int y)

{

   COORD coord = {x, y};

   SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);

}

//获取当前CMD当前光标所在位置

void getxy()

{

HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

    COORD coordScreen = {0, 0}; //光标位置

    CONSOLE_SCREEN_BUFFER_INFO csbi;

    if (GetConsoleScreenBufferInfo(hConsole, &csbi))

    {

     ptx=csbidwCursorPositionX;

     pty=csbidwCursorPositionY;

    }

}

typedef struct

{

int x;

int y;

int type;

int v;

}PT;

PT s=NULL,stack[50],start,end,c;

int pos=0;

void prt()

{

int i,j;

system("cls");

for(i=0;i<row;i++)

{

for(j=0;j<col;j++)

{

if(s[i][j]type==1)

{

printf("■");

}

else if(i==endx && j==endy)

{

printf("★");

}

else if(i==cx && j==cy)

{

printf("◎");

}

else

{

printf("  ");

}

}

printf("\n");

}

Sleep(500);

}

void stack_in(PT a)

{

stack[pos++]=a;

}

PT stack_out()

{

int i;

PT t;

t=stack[0];

for(i=0;i<pos-1;i++)

{

stack[i]=stack[i+1];

}

pos--;

return t;

}

void fun()

{

PT a;

int x,y,v;

while(1)

{

if(pos==0)

{

break;

}

a=stack_out();

x=ax;

y=ay;

if(x==startx && y==starty)

{

break;

}

v=s[x][y]v;

if(x-1>=0 && s[x-1][y]type==0 && (s[x-1][y]v==-1 || s[x-1][y]v>v+1))

{

s[x-1][y]v=v+1;

stack_in(s[x-1][y]);

}

if(x+1<=row-1 && s[x+1][y]type==0 && (s[x+1][y]v==-1 || s[x-1][y]v>v+1))

{

s[x+1][y]v=v+1;

stack_in(s[x+1][y]);

}

if(y-1>=0 && s[x][y-1]type==0 && (s[x][y-1]v==-1 || s[x-1][y]v>v+1))

{

s[x][y-1]v=v+1;

stack_in(s[x][y-1]);

}

if(y+1<=col-1 && s[x][y+1]type==0 && (s[x][y+1]v==-1 || s[x-1][y]v>v+1))

{

s[x][y+1]v=v+1;

stack_in(s[x][y+1]);

}

}

}

void go(int x, int y)

{

printf("\n按任意键开始\n");

getchar();

int v;

while(1)

{

if(x==endx && y==endy)

{

setxy(0,y+2);

printf("end");

return;

}

v=s[x][y]v;

if(v==0)

{

return;

}

if(x-1>=0 && s[x-1][y]v==v-1)

{

c=s[x-1][y];

setxy(y2,x);

x=x-1;

printf("  ");

setxy(y2,x);

printf("◎");

Sleep(500);

continue;

}

else if(x+1<=row-1 && s[x+1][y]v==v-1)

{

c=s[x+1][y];

setxy(y2,x);

x++;

printf("  ");

setxy(y2,x);

printf("◎");

Sleep(500);

continue;

}

else if(y-1>=0 && s[x][y-1]v==v-1)

{

c=s[x][y-1];

setxy(y2,x);

y--;

printf("  ");

setxy(y2,x);

printf("◎");

Sleep(500);

continue;

}

else if(y+1<=col-1 && s[x][y+1]v==v-1)

{

c=s[x][y+1];

setxy(y2,x);

y++;

printf("  ");

setxy(y2,x);

printf("◎");

Sleep(500);

continue;

}

}

printf("\nreturn go\n");

system("pause");

}

void GetMapFromFile()

{

int i,j,x,y,len;

char ch[50]={'\0'};

FILE fp=fopen("e:\\map1txt","r");

if(fp==NULL)

{

printf("open file failed\n");

return;

}

x=0;

while(!feof(fp))

{

fgets(ch,50,fp);

row++;

}

col=strlen(ch);

fseek(fp,0L,SEEK_SET);

while(!feof(fp))

{

fgets(ch,50,fp);

if(s==NULL)

{

len=strlen(ch);

for(i=len-1;i>0;i--)

{

if(ch[i]!='0' && ch[i]!='1')

{

ch[i]='\0';

}

else

{

break;

}

}

len=strlen(ch);

s=(PT)malloc(sizeof(PT)row);

for(j=0;j<len;j++)

{

(s+j)=(PT)malloc(sizeof(PT)len);

}

}

y=0;

for(i=0;i<len;i++)

{

s[x][y]type=ch[i]-48;

s[x][y]x=x;

s[x][y]y=y;

s[x][y]v=-1;

y++;

}

x++;

}

start=s[row-2][1];

end=s[row-2][len-2];

fclose(fp);

}

int main()

{

GetMapFromFile();

int i,j;

int x,y;

x=endx;

y=endy;

s[x][y]v=0;

stack_in(end);

fun();

c=start;

prt();

go(startx,starty);

return 0;

}

以上就是关于求C语言迷宫程序的解释说明！！！全部的内容，包括:求C语言迷宫程序的解释说明！！！、C语言迷宫问题，用栈来做、c语言的迷宫问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！