迷宫求解的高效算法解析

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<time.h> int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag; void maze() { int i,j; time_t t; srand(time(&t)); for(i=0;i<m;i++) for(j=0;j<n;j++) { map[i][j]=rand()%2; if(map[i][j]) num++; } if(num<m*n/2) { for(i=0;i<m;i++) for(j=0;j<n;j++) if(!map[i][j]) map[i][j]+=rand()%2; } map[0][0]=1; map[m-1][n-1]=1; } void print() { int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) { printf("%d ",map[i][j]); if(j==n-1)puts(""); } } void dfs(int x,int y) { int i,tx,ty; if(!flag) return; for(i=0;i<4;i++) { tx=x+d[0][i]; ty=y+d[1][i]; if(!f[tx][ty]&&tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty]) { f[tx][ty]=1; a[ans]=tx; b[ans++]=ty; if(tx+ty==0) { printf("(%d,%d)\n",m,n); for(flag=i=0;i<ans;i++) printf("(%d,%d)\n",a[i]+1,b[i]+1); return; } dfs(tx,ty); f[tx][ty]=0; ans--; } } } int main() { while(scanf("%d%d",&m,&n),m+n) { memset(f,0,sizeof(f)); num=ans=0; flag=1; maze(); print(); dfs(m-1,n-1); if(flag) puts("There is no path"); } return 0; }