#include <stdio.h>
#include <stdlib.h>
#define INITSIZE 100
#define INCREAMENT 10
#define M 8
#define N 8
typedef struct{
int x;
int y;
}PosType;
typedef struct{
int ord;
PosType seat;
int di;
}SElemType;
typedef struct SqStack{
SElemType * data;
SElemType * top;
int stacksize;
}SqStack;
void InitStack(SqStack * S){
S -> data = (SElemType *)malloc(INITSIZE * sizeof(SElemType));
if (!(S -> data)) exit(0);
S -> top = S -> data;
S -> stacksize = INITSIZE;
}
void Push(SqStack * S, SElemType e){
if(S -> top - S -> data >= S -> stacksize){
S -> data = (SElemType *)realloc(S -> data, (S -> stacksize + INCREAMENT) * sizeof(SElemType));
if (!(S -> data)) exit(0);
S -> top = S -> data + S -> stacksize;
S -> stacksize = S -> stacksize + INCREAMENT;
}
* (S -> top ++) = e;
}
void Pop(SqStack * S, SElemType * e){
if (S -> data == S -> top) exit(0);
* e = *(-- S -> top);
}
void GetTop(SqStack S, SElemType * e){
if (S.data == S.top) exit(0);
* e = * (S.top - 1);
}
bool Pass(int a[M + 2][N + 2], PosType pos){
int x = pos.x;
int y = pos.y;
if (a[x][y] == 0) //可通
return true;
else
return false;
}
bool Footprint(int a[M + 2][N + 2], PosType pos){
int x = pos.x;
int y = pos.y;
a[x][y] = 2; //通过留下的足迹
}
PosType NextPos(PosType pos, int i){
PosType nextpos;
if (i == 1){
nextpos.x = pos.x;
nextpos.y = pos.y + 1;
}
else if (i == 2){
nextpos.x = pos.x + 1;
nextpos.y = pos.y;
}
else if (i == 3){
nextpos.x = pos.x;
nextpos.y = pos.y -1;
}
else if (i == 4){
nextpos.x = pos.x -1;
nextpos.y = pos.y;
}
return nextpos;
}
void MarkPrint(int a[M + 2][N + 2], PosType pos){
int x = pos.x;
int y = pos.y;
a[x][y] = 3; //走过，不通
}
bool MazePath(int a[M + 2][N + 2], PosType start, PosType end){
SqStack S;
SElemType e;
InitStack(&S);
PosType curpos = start;
int curstep = 1;
do{
if(Pass(a, curpos)) {
Footprint(a, curpos);
e.di = 1;
e.ord = curstep;
e.seat = curpos;
Push(&S, e);
if(curpos.x == end.x && curpos.y == end.y)
return true;
curpos = NextPos(curpos, 1);
curstep++;
}
else{
if(S.data != S.top){
Pop(&S, &e);
while(e.di == 4 && (S.data != S.top)){
MarkPrint(a, e.seat);
Pop(&S, &e);
}
if(e.di < 4){
e.di ++;
Push(&S, e);
curpos = NextPos(e.seat, e.di);
}
}
}
}while(S.data != S.top);
return false;
}
int main(){
int a[M + 2][N + 2] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
PosType start = {1, 1};
PosType end = {8, 8};
bool flag = true;
flag = MazePath(a, start, end);
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
if(a[i][j] == 1)
printf("# ");
else if(a[i][j] == 2)
printf("* ");
else if(a[i][j] == 3)
printf("@ ");
else if(a[i][j] == 0)
printf(" ");
}
printf("\n");
}
return 0;
}
为增加趣味性，可以用下面主函数替换（此外还要修改宏定义M，N），生成30*50迷宫。为显示清晰，这里省去了@，不再显示访问过但不在最终路径上的节点。需要特殊说明的是，下面的数据来源于网上的蓝桥杯竞赛。代码中一些特殊处理，是为了将其转化为数组传参，其过程与迷宫求解无关。
int main(){
int c[M + 2][N + 2] = {0};
for(int k = 0; k < 52; k++){
c[0][k] = 1;
c[31][k] = 1;
}
for(int k = 0; k < 32; k++){
c[k][0] = 1;
c[k][51] = 1;
}
char a[]="010101010010110010010101100101101001000010001010100000100010000010101001000010000000100110011010010101111011010010001000001101001011100011000000010000010000000010101000110100001010000010101010110010110001111100000010100001001010001010000010110000000011001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000#";
char * p = a;
int b;
int i = 1, j = 1;
int m = 0;
while (*p != '#'){
if(*p == '0')
b = 0;
else
b = 1;
m ++;
if(*p != '#'){
c[i][j] = b;
j ++;
if(j >= 51){
j = 1;
i++;
}
}
p ++;
}
for(int i = 0; i < 32; i++){
printf(" ");
for(int j = 0; j < 52; j++){
if(c[i][j] == 1)
printf("# ");
else if(c[i][j] == 2)
printf("o ");
else if(c[i][j] == 0)
printf(" ");
}
printf("\n");
}
printf("\n\n\n\n");
PosType start = {1, 1};
PosType end = {30, 50};
bool flag = true;
flag = MazePath(c, start, end);
for(int i = 0; i < 32; i++){
printf(" ");
for(int j = 0; j < 52; j++){
if(c[i][j] == 1)
printf("# ");
else if(c[i][j] == 2)
printf("o ");
else if(c[i][j] == 3)
printf(" ");
else if(c[i][j] == 0)
printf(" ");
}
printf("\n");
}
return 0;
}
