数据结构迷宫问题的C 代码

数据结构课程设计——迷宫问题求解代码

问题描述及要求：

迷宫问题求解

输入：

第一行n，m表示迷宫大小n*m

之后有n行m列，全由01组成，0表示路，1表示墙

入口设为(0,0)

出口设为(n-1,m-1)

输出：

输出从入口到出口的所有不同解，每组解的第一行打印一个数表示第几组解，之后k行表示路径，如：

1

(0,0)

(0,1)

(1,1)

代码部分（已测试，可直接运行）：

#include<cstdio>

#include<cstring>

#define N255

int n,m,cnt;

int maze[N][N],step[N][N];

struct Point{

int x,y;

}path[N*N];

int oper[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

bool isvaild(int x,int y){

if(x>=0&&x<n&&y>=0&&y<m&&!maze[x][y]&&!step[x][y])

return true;

return false;

}

void dfs(int x,int y,int len){

if(x==n-1&&y==m-1){

cnt++;

printf("%d\n",cnt);

for(int i=0;i<len;i++)

printf("(%d,%d)\n",path[i].x,path[i].y);

return;

}

for(int i=0;i<4;i++)

if(isvaild(x+oper[i][0],y+oper[i][1])){

Point tmp;

tmp.x=x+oper[i][0];

tmp.y=y+oper[i][1];

path[len]=tmp;

step[tmp.x][tmp.y]=1;

dfs(tmp.x,tmp.y,len+1);

step[tmp.x][tmp.y]=0;

}

}

void work(){

step[0][0]=1;

Point cur;

cur.x=0;

cur.y=0;

path[0]=cur;

dfs(0,0,1);

}

int main(){

scanf("%d%d",&n,&m);

for(int i=0;i<n;i++)

for(int j=0;j<m;j++)

scanf("%d",&maze[i][j]);

cnt=0;

memset(step,0,sizeof(step));

work();

return0;