回溯法—迷宫问题.cpp

如题 回溯法—迷宫问题 仅供参考。。谢谢大家共同讨论

//可解带厅的(8,8)迷宫：刘子杨
//迷宫初始化:无任何要求
//从(1,1)出发,走出迷宫

#include<iostream.h>
//迷宫图
#define LENGTH 8
int length=0;
///**
int maze[8][8] = 
{   {0,0,22,0,22,0,22,22},
    {22,0,0,0,0,22,0,22},
    {22,22,22,0,0,0,0,0},
	{22,0,0,0,22,0,0,22},
    {22,22,0,0,0,22,0,22},
    {22,0,0,22,0,0,0,22},
    {22,22,0,0,0,22,0,22},
    {22,22,0,22,22,22,22,22},
};
int mazeCopy[8][8]= 
{   {0,0,2,2,2,2,2,2},
    {2,0,0,0,0,0,0,2},
    {2,2,0,0,0,0,0,2},
    {2,0,0,0,0,0,0,2},
    {2,2,0,0,0,0,0,2},
    {2,0,0,0,0,0,0,2},
    {2,2,0,0,0,0,0,2},
    {2,2,2,2,2,2,2,2},
};

bool CanPass(int c,int r,int len)
{

	 if(maze[c][r] == 0  && ( (length == 0)||(length !=0 && len <= length)))
	 {
		 if((length == 0)||(length !=0 && len == length))
			 maze[c][r] = 0;
		 return true;
		 
	 }
	 
	 
	 return false;
}

void display()//show maze to us
{
	for(int i = 0;i<LENGTH;i++)
	{
		cout<<endl;
		for(int j = 0; j<LENGTH;j++)
			cout<<maze[i][j]<<"  ";
	}
	cout<<endl;
	/*for(int m = 0; m<LENGTH; m++)
	{
		//cout<<endl;
		for(int n = 0; n<LENGTH;n++)
		{
			maze[m][n] = mazeCopy[m][n];
		}
			//cout<<maze[i][j]<<"  ";
	}*/
}

void Backtrack(int c , int r,int l)
{
	//int len = l;
	if(c >= LENGTH || r >=LENGTH)
	{
		//cout<<"dsdf"<<endl;
		if((length == 0)||(length !=0 && l < length)) 
		{
		length = l;
		display();
		/*if(c = 8)
			maze[c-1][r] = 0;
		else if(r = 8)
			maze[c][r-1] = 0;
		else if(r < 0)
			maze[c][r+1] = 0;
		else if(c < 8)
			maze[c+1][r] = 0;*/
		}
		//sum++;
		
	}
	else{
		//cout<<maze[c][r]<<endl;
		//cout<<"ssd"<<endl;
		if(CanPass(c,r,l))
		{
			//cout<<maze[c][r]<<endl;
			maze[c][r] = l;
			//cout<<maze[c][r]<<"\n";
			Backtrack(c+1,r,l+1);
			maze[c][r] = 0;
			maze[c][r] = l;
            Backtrack(c,r+1,l+1);
			maze[c][r] = 0;
			maze[c][r] = l;
			Backtrack(c-1,r,l+1);
			maze[c][r] = 0;
			maze[c][r] = l;
            Backtrack(c,r-1,l+1);
			maze[c][r] = 0;
			//maze[c][r] = l;
		}
	} 
}


int main()
{
	//int *m = new int[100]
		//for
	int l = 0;
	//cout<<LENGTH<<endl;
	cout<<"初始状态为"<<endl;
	display();
	Backtrack(0,0,l);
	return 0;
}











//**/

/*class MAZE
{
	friend void  Maze(int **);
private:
	bool CanPass(int c,int r);
	void Backtrack(int c,int r,int*l);
	void display();
	int *x,//当前解
		*length = 0;//路程距离
		//long sum;//当前已找到的可行方案
}
bool MAZE::CanPass(int c,int r,int * l)
{
	 if(maze[c][r] == 0)
		 if(length != 0 && l<length)
			 return true;
	 return false;
}
void MAZE::Backtrack(int c,int r,int * l)
{
	
	int *len = l;
	if(c >= LENGTH || r >=LENGTH)
	{
		length = len;
		//sum++;
		display();
	}
	else{
		if(CanPass(c,r,len))
		{
			maze[c][r] = 1;
			Backtrack(c+1,r,l);
            Backtrack(c,r+1,l);
			Backtrack(c-1,r,l);
            Backtrack(c,r-1,l);
		}
	}
}
void MAZE::display()//show maze to us
{
	for(int i = 0;i<LENGTH;i++)
	{
		cout<<endl;
		for(int j = 0; j<LENGTH;j++)
			cout<<maze[i][j]<<"  ";
	}
}
void Maze(int[][] maze)
{
	Maze M;
	//M.sum = 0;
    /*int * n = new int[LENGTH+1];
    for(int i = 0; i<= LENGTH; i++)
		n[i] = 0;
	M.m  = n;
	M.Backtrack(0,0);
	//M.display();
	delete n[];
	int * l=0;
	M.Backtrack(0,1,l);
	M.Backtrack(1,0,l);
	//return M.sum;
}

 int main()
 {
	 MAZE m = new MAZE();
	 return 0;
 }*/