本文給出一個(gè)c語言版的走迷宮的程序，
一個(gè)走迷宮的程序
。迷宮的寬和高，迷宮矩陣，迷宮的入口和出口從文件讀入。程序首先讀入迷宮數(shù)據(jù)，然后顯示迷宮矩陣，最后調(diào)用迷宮搜索程序找到一個(gè)路徑，并輸出。1. 迷宮的表示。
迷宮用結(jié)構(gòu)體MATRIX來表示
包括迷宮矩陣
迷宮的寬，迷宮的高，
迷宮入口的坐標(biāo)，迷宮出口的坐標(biāo)。
結(jié)構(gòu)體定義如下：
typedef struct _step
{
int x; //行坐標(biāo)
int y; //列坐標(biāo)
}STEP;
typedef struct _matrix
{
int data[MAX_WIDTH+2][MAX_WIDTH+2]; //迷宮數(shù)據(jù)，0：表示有路，1：表示墻
int width; //矩陣（迷宮）的寬，包括最左和最有２堵墻
int height; //矩陣（迷宮）的寬，包括頂部和底部２堵墻
STEP entrance; //迷宮入口
STEP exit; //迷宮出口
}MATRIX;
迷宮矩陣的每一個(gè)元素可以是0或1，0表示可走，1表示是墻，走不通。
為了便于檢查是否越界，即坐標(biāo)超過迷宮的范圍。在迷宮的4個(gè)邊增加了全1數(shù)據(jù)，表示4堵墻，這樣，在任何時(shí)候，都不會(huì)越界。下面的數(shù)據(jù)表示1個(gè)5×5的迷宮，增加了4堵墻后，實(shí)際寬度和高度變?yōu)?，迷宮變成1個(gè)7×7的矩陣
1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 1,
1, 1, 0, 1, 0, 1, 1,
1, 0, 0, 1, 1, 1, 1,
1, 0, 1, 0, 0, 0, 1,
1, 0, 0, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1,
2.算法
走迷宮的路徑的每一步可用二元組(x,y)來表示。已經(jīng)走過的路徑放入數(shù)組path。
首先，將入口的坐標(biāo)放入數(shù)組，此時(shí)path數(shù)組的元素個(gè)數(shù)為1.
接下來使用下面的規(guī)則，試圖找到一條出路
1. 從當(dāng)前位置（即數(shù)組的最后一個(gè)元素），從右，下，左，上四個(gè)方向搜索，看能否走通。
如果可找到一條通路，則
將新的位置的坐標(biāo)放入path數(shù)組，數(shù)組長(zhǎng)度加1.
如果新的位置的坐標(biāo)等于出口的坐標(biāo)，搜索結(jié)束。
如果從各個(gè)方向都走不通，則
將迷宮當(dāng)前位置的元素置為1，這樣，當(dāng)前點(diǎn)就變成墻，下次就不會(huì)走到這個(gè)位置了。并將數(shù)組的最有一個(gè)元素丟棄，數(shù)組長(zhǎng)度減1
如果數(shù)組的長(zhǎng)度為0，沒有任何路徑可以走通，搜索結(jié)束。
全部的代碼見下：
[cpp] view plaincopy
#include
#include
#include
#include
#define MAX_WIDTH 30
#define MAX_HEIGHT 30
typedef struct _step
{
int x; //行坐標(biāo)
int y; //列坐標(biāo)
}STEP;
typedef struct _matrix
{
int data[MAX_WIDTH+2][MAX_WIDTH+2]; //迷宮數(shù)據(jù)，0：表示有路，1：表示墻
int width; //矩陣（迷宮）的寬，包括最左和最有２堵墻
int height; //矩陣（迷宮）的寬，包括頂部和底部２堵墻
STEP entrance; //迷宮入口
STEP exit; //迷宮出口
}MATRIX;
MATRIX g_matrix= //初始化為一個(gè)迷宮，程序也能從文件中讀入迷宮數(shù)據(jù)
{
{
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 0, 1, 0, 1, 1},
{1, 0, 0, 1, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 1},
{1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1},
},
7,7, //7行，7列，包括4堵墻
{1,1}, //入口坐標(biāo)
{5,5} //出口坐標(biāo)
};
static STEP s_shift[]=
{
{1,0}, //向右走， x++, y 不變
{0,1}, //向下走, x 不變, y++
{-1,0}, //向左走, x--, y不變
{0,-1} //向上走, x 不變, y--
};
void print_paths(STEP path[],int path_len) //打印走迷宮的路徑
{
int i;
for (i=0;i { if (i>0) printf("->"); printf("(%d,%d)",path[i].x, path[i].y); } } void print_Matrix(MATRIX* pMatrix) //打印迷宮數(shù)據(jù)，迷宮數(shù)據(jù)包含4堵墻 { int i,j; for (i=0;i { for (j=0;j { if (j!=0) printf(" "); printf("%d",pMatrix->data[i][j]); } printf("\n"); } } int search_path(int matric[MAX_WIDTH+2][MAX_WIDTH+2], STEP path[],int path_len,STEP exit) { while (1) { int i,bFind; STEP newPos; for (bFind=0,i=0;i<4;i++) //從右，下，左，上，查找新的可以走的位置 { newPos.x = path[path_len-1].x + s_shift[i].x; newPos.y = path[path_len-1].y + s_shift[i].y; if ( path_len==1 ) { if ( g_matrix.data[newPos.x][newPos.y]==0) { bFind=1; break; //找到一個(gè)位置 } } // path[path_len-1]表示當(dāng)前位置，path[path_len-2]表示上一步的位置， // 如果新的位置等于上一個(gè)位置，將陷入循環(huán)，故要求新的位置不能是上一步的位置 else if ( (newPos.x != path[path_len-2].x || newPos.y!=path[path_len-2].y) && g_matrix.data[newPos.x][newPos.y]==0) { bFind=1; break; //找到一個(gè)位置 } } if (bFind) { path[path_len++]=newPos; //將新的位置追加到path數(shù)組，路徑長(zhǎng)度+1 if ( newPos.x==exit.x && newPos.y==exit.y) return path_len; } else { matric[path[path_len-1].x][path[path_len-1].y]=1; //從當(dāng)前位置，無路可走，將當(dāng)前位置標(biāo)記為墻