求解迷宫问题 可用C语言或C++
耗子走迷宫的古典问题，要求用队列的存储方式、堆栈的存储方式分别实现程序。
首先，用二维数组来表示迷宫，其元素值只有两个
入口
000110
001000
010011
101101
010101
101000
出口
几个问题：
1、二维迷宫数组的初始化mg[m][n]
2、迷宫中的每个位置（i,j）有8个方向可走，我们要约定每次先走哪个方向，这样程序才有章可循。边缘位置只有3个方向，这样我们给迷宫周围增加一圈围墙，即迷宫数组扩充为mg[m+1][n+1]，且边缘全部为1。
11111111
10001101
10010001
10100111
11011011
10101011
11010001
11111111
3、不同方向对应有不同的坐标变换值，如对（i,j）这个位置来说，有8个方向，定义一个变量v＝1～8，对应i=i+zx[v],j=j+zy[v],这样，事先将每个方向上的横坐标、纵坐标增量zx，zy分别用数组给出即可。
4、问题的关键在：如何在走不通的情况下回过头来重新寻找其他方向？队列、栈的存储结构？需要存储哪些数据？
5、输出迷宫路径的方式：
入口->(x1,y1)->(x2,y2)->…..->出口
[解决办法]
花费了将近4个小时，终于写出一个走迷宫的程序。
迷宫的表示。
迷宫用结构体MATRIX来表示
包括迷宫矩阵
迷宫的宽，迷宫的高，
迷宫入口的坐标，迷宫出口的坐标。
迷宫矩阵的每一个元素可以是0或1，0表示可走，1表示是墙，走不通。
为了便于检查是否越界，即坐标超过迷宫的范围。在迷宫的4个边增加了全1数据，表示4堵墙，这样，在任何时候，都不会越界。下面的数据表示1个5×5的迷宫，增加了4堵墙后，实际宽度和高度变为7，迷宫变成1个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,
基本思路，
走迷宫的路径的每一步可用二元组(x,y)来表示。已经做过的路径放入一个数组path。
首先，将入口的坐标放入数组，此时path数组的元素为1.
接下来使用下面的规则，试图找到一条出路
1. 从当前位置（及数组的最后一个元素），从右，下，左，上四个方向搜索，看能否走通，
如果可走通，
将新的位置的坐标放入path数组，数组长度加1.
如果新的位置的坐标等于出口的坐标，搜索结束
如果从各个方向都走不通
将迷宫当前位置的元素置为1，这个变为变为墙，这样下次就不会走到这个位置了，并将数组的最有一个元素丢弃，数组长度-1
如果数组的长度为0，所有没有任何路径可以走通，搜索结束
下面给出源代码和运行结果
#include <stdafx.h>#include <stdlib.h>#include <stdio.h>#include <memory.h>#define MAX_WIDTH 30#define MAX_HEIGHT 30typedef struct _step{ int x; //行坐标 int y; //列坐标}STEP;typedef struct _matrix{ int data[MAX_WIDTH+2][MAX_WIDTH+2]; //迷宫数据，0：表示有路，1：表示墙 int width; //矩阵（迷宫）的宽，包括最左和最有２堵墙 int height; //矩阵（迷宫）的宽，包括顶部和底部２堵墙 STEP entrance; //迷宫入口 STEP exit; //迷宫出口}MATRIX;MATRIX g_matrix= //初始化为一个迷宫，程序也能从文件中读入迷宫数据{ { {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}, //入口坐标 {5,5} //出口坐标};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<path_len;i++) { if (i>0) printf("->"); printf("(%d,%d)",path[i].x, path[i].y); }}void print_Matrix(MATRIX* pMatrix) //打印迷宫数据，迷宫数据包含4堵墙{ int i,j; for (i=0;i<pMatrix->height;i++) { for (j=0;j<pMatrix->width;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; //找到一个位置 } } 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; //找到一个位置 } } if (bFind) { path[path_len++]=newPos; //将新的位置追加到path数组，路径长度+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; //从当前位置，无路可走，将当前位置标记为墙 path_len--; //回退一步 if ( path_len==0) return path_len; } }}int readMatrix(char *file){ char line[1024]; FILE *fp=NULL; int i,j,x,y; fp=fopen(file,"rt"); if (fp==NULL) { printf("Can not open file %s\n",file); return 0; } memset(&(g_matrix),0,sizeof(g_matrix)); fgets(line,sizeof(line)-1,fp); sscanf(line,"%d %d",&x,&y); //读入迷宫的行数和列数 if ( x>MAX_WIDTH || y>MAX_HEIGHT) { printf("The Matrix is too large\n"); fclose(fp); return 0; } g_matrix.width=x+2; //在4条边增加4堵墙，故宽和高增加2 g_matrix.height=y+2; for (j=0;j<g_matrix.width;j++) { g_matrix.data[0][j]=1; //第一行为墙 g_matrix.data[g_matrix.height-1][j]=1; //最后一行为墙 } for (i=0;i<g_matrix.height;i++) { g_matrix.data[i][0]=1; //最左边的列为墙 g_matrix.data[i][g_matrix.width-1]=1; //最右边的列为墙 } for (i=1;i<g_matrix.height-1;i++) { char *p; fgets(line,sizeof(line)-1,fp); j=1; p=line; while (1) { while ( *p==' ' || *p==９ ) //跳过空格符号 p++; if ( *p>='0' && *p<='9') { sscanf(p,"%d",&(g_matrix.data[i][j])); //读入地i行j列的数据 while ( *p>='0' && *p<='9') p++; //数据已经读入，跳过当前的数字 j++; } if (j>=g_matrix.width-2) break; } } fgets(line,sizeof(line)-1,fp); //读入入口的行坐标和列坐标，和出口的行坐标，列坐标 sscanf(line,"%d %d %d %d",&(g_matrix.entrance.x),&(g_matrix.exit.y),&(g_matrix.exit.x),&(g_matrix.exit.y)); fclose(fp); fp=NULL; g_matrix.entrance.x++; //增加了一列是墙，故入口横坐标+1 g_matrix.entrance.y++; //增加了一行是墙，故入口纵坐标+1 g_matrix.exit.x++; //增加了一列是墙，故入口横坐标+1 g_matrix.exit.y++; //增加了一列是墙，故入口纵坐标+1 return 1;}int main(){ STEP path[MAX_WIDTH*MAX_HEIGHT]; int step_count; if ( !readMatrix("matrix.txt") ) //不使用初始化的数据，从文件中读入迷宫数据 { return 0; //读取失败，直接跳出 } printf("The matrix is\n"); print_Matrix(&g_matrix); path[0]=g_matrix.entrance; //将入口位置放入path数组 step_count = search_path(g_matrix.data,path,1,g_matrix.exit); //查找一条路径，路径的每一步的坐标放入path数组 if (step_count>0) //找到一条出路，步数>０ { printf("\nThe path is\n"); print_paths(path,step_count); } else //步数<=0, 没有找到出路 printf("No solution\n"); return 0;}