No.4.2 迷宫走秀

用迷宫试试二维平面中，深度优先算法的应用：求从出发位置到目标位置的最短路径，要求走过的路(格子)就不能再回头，有障碍物的格子不可通行。

#include

int a[50][50],book[50][50];　　//平面边界与标记数组
int n,m,p,q,min=10000;　　　//初始化一个最值，不能小，否则还走什么路呢

void dfs(int x,int y,int step){　　//DFS解决的问题：从当前位置，如何走下一步
　　int k,tx,ty;　　　　　　　//尝试的初始位置是不变的，所以最好不要动(x,y)，用另一组变量(tx,ty)
　　int next[4][2]={
　　　　{0,1},{1,0},
　　　　{0,-1},{-1,0}
　　};

　　if(x==p && y==q){　　  //躺赢，不需走下一步
　　　　if(step 　　　　　　min=step;
　　　　return;　　　　　//直接返回上一层DFS
　　}

　　for(k=0;k<=3;k++){　　//下一步可做的尝试：右、下、左、上，既然是二维平面，那么尝试就是一个向量操作
　　　　tx = x+next[k][0];
　　　　ty = y+next[k][1];
　　　　if(tx<1 || tx>n ||ty<1 ||ty>m)　　//遇到边界，则继续下一步尝试，即结束本次循环 ,k++
　　　　　　continue;
　　　　if(a[tx][ty]==0 && book[tx][ty]==0){　　//走过的路不能回头，障碍物不能通行
　　　　　　book[tx][ty]=1;
　　　　　　dfs(tx,ty,step+1);
　　　　　　book[tx][ty]=0;
　　　　}
　　}
　　return;
}

int main(){
　　int i,j,startx,starty;　　//同一个文件下，局部变量也尽量不要使用同名！
　　printf("input n*m matrix:");
　　scanf("%d %d",&n,&m);
　　for(i=1;i<=n;i++)
　　　　for(j=1;j<=m;j++){
　　　　　　scanf("%d",&a[i][j]);
　　　　}

　　printf("input original location:");
　　scanf("%d %d",&startx,&starty);
　　printf("input destination location:");
　　scanf("%d %d",&p,&q);

　　book[startx][starty]=1;
　　dfs(startx,starty,0);
　　printf("the min steps %d",min);
　　getchar();getchar();
　　return 0;
}

踩坑：

1.关于平面的定义：二维数组，走下一步的时候，就要同时操作(x,y)；

2.关于边界的判断：if(tx<1 || tx>n ||ty<1 ||ty>m) 比 while 更简洁优雅；

3.同一个文件下，局部变量也尽量不要使用同名！