迷宫问题.cpp

迷宫问题回朔解法

# include<iostream.h>
# include<malloc.h>
# include<stdio.h>

struct offset
{
	int vert;
	int horiz;
};
offset move[4];
int **maze;
int max_row,max_col,num;

void print_ans()
{
	maze[1][1]=2;
	cout<<"第"<<num+1<<"个解为:"<<endl;
	for(int i=0;i<max_row+2;i++)
	{
		for(int j=0;j<max_col+2;j++)
			cout<<maze[i][j];
		cout<<endl;
	}
	cout<<endl;
	num++;
}


void findpath(int row,int col)
{
	int direct,next_row,next_col;
	direct=0;
	while(direct<4)
	{
		next_row=row+move[direct].vert;
		next_col=col+move[direct].horiz;
		if(maze[next_row][next_col]==0)
		{
			maze[next_row][next_col]=2;
			if(next_row==max_row && next_col==max_col)
				print_ans();
			else
				findpath(next_row,next_col);
				maze[next_row][next_col]=0;
		}
		direct++;
	}
}





void main()

{
	move[0].vert=move[3].horiz=1;
	move[1].vert=move[2].horiz=-1;
	move[0].horiz=move[1].horiz=move[2].vert=move[3].vert=0;
	cout<<"请输入迷宫的行数和列数: "<<endl;
	cin>>max_row>>max_col;
	maze=(int**)malloc((max_row+2)*sizeof(int*));
	for(int i=0;i<(max_row+2);i++)
		maze[i]=(int*)malloc((max_col+2)*sizeof(int));
	for(i=0;i<max_col+2;i++)
	{
		maze[i][0]=maze[i][max_col+1]=1;
		maze[0][i]=maze[max_row+1][i]=1;
	}
	cout<<"请输入迷宫(0为可通,1为不可通):"<<endl;
	for(i=1;i<=max_row;i++)
	{
		for(int j=1;j<=max_col;j++)
		{
			
			cin>>maze[i][j];
			
		}
	}
	cout<<"输入的迷宫的一条出路为: "<<endl;
	findpath(1,1);
	
}