有一个nm格的迷宫(表示有n行、m列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这nm个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。 请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)
第一行是两个数n，m( 1 < n ， m < 15 )，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“->”表示方向。 如果没有一条可行的路则输出-1。
算法分析 用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表： 2 1 x,y 3 4 对应的位置为：(x, y-1)，(x-1, y)，(x, y+1)，(x+1, y)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。 这个查找过程用search来描述如下： procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路} begin for i:＝1 to 4 do{分别对4个点进行试探} begin 先记住当前点的位置，已走过的情况和走过的路； 如果第i个点(xl，y1)可以走，则走过去； 如果已达终点，则输出所走的路径并置有路可走的信息， 否则继续从新的点往下查找search(xl，y1，b1，p1)； end； end； 有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。
#include <iostream> #include <cstdio> using namespace std; struct route{ int x; int y; }r[10000]; //每一步的坐标 int start_x,start_y; //起点位置 int end_x,end_y; //出口位置 int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0}; //分别表示为左、上、右、下 int map[16][16],m,n; //地图 bool flag=false; //有无出路 void DFS(int x,int y,int step){ if(x==end_x&&y==end_y){ //找到一条出口时 for(int i=0;i<step;i++) //打印该条路线 printf("(%d,%d)->",r[i].x,r[i].y); printf("(%d,%d)\n",x,y); flag=true; //标记有出路 return; } r[step].x=x; //更新这一步的位置 r[step].y=y; for(int i=0;i<4;i++){ //往四个方向搜寻出路 if(map[x+dx[i]][y+dy[i]]==1){ //某方向可走 map[x][y]=0; //把这一步置0，表示已经走过了 DFS(x+dx[i],y+dy[i],step+1); //朝某方向继续搜寻出路 map[x][y]=1; //搜寻完之后回到该处，继续朝其它方向搜寻出路 } } } int main() { scanf("%d%d",&m,&n); //输入地图大小 for(int i=1;i<=m;i++) //输入地图 for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); scanf("%d%d",&start_x,&start_y); //输入起点 scanf("%d%d",&end_x,&end_y); //输入出口 DFS(start_x,start_y,0); //搜寻出路 if(!flag) //没有出路 printf("-1\n"); return 0; }