필기문제: 03년미궁.

#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;
//         

//              。        ：      。

#define MAXSIZE 128
bool bMark[MAXSIZE][MAXSIZE];    //      ，true:       ,false:       
int iArrMaze[MAXSIZE][MAXSIZE]; //    ，0：   ，1：   
typedef struct Stat             //    
{
	Stat(int iX,int iY,int iStep):_iX(iX),_iY(iY),_iStep(iStep){}
	int _iX;                  //   
	int _iY;                  //   
	int _iStep;               //  
}Stat;
queue<Stat> queueStat;      //          ，               
int iArrGo[][2] = { {0,1} , {0,-1} ,{1,0} ,{-1,0}};//         
int iBegX,iBegY;//       
int iEndX,iEndY;//       
int iM,iN;      //        
bool isSuccess = false;//             

int BFS(int iRow,int iCol)
{
	while(!queueStat.empty())
	{
		Stat curStat = queueStat.front();
		queueStat.pop();
		for(int i = 0 ; i < 4 ; i++)//4   ，         
		{
			int iNx = curStat._iX + iArrGo[i][0];
			int iNy = curStat._iY + iArrGo[i][1];
			
			//          ，             
			if(iNx < 0 || iNx >= iRow || iNy < 0 || iNy >= iCol )
			{
				continue;
			}

			//           ，     
			if(true == bMark[iNx][iNy])
			{
				continue;
			}

			//        ，   
			if(1 == iArrMaze[iNx][iNy])
			{
				continue;
			}

			Stat nextStat(iNx,iNy,curStat._iStep + 1);
			queueStat.push(nextStat);//       
			bMark[iNx][iNy] = true;   //       

			//        
			if(iNx == iEndX && iNy == iEndY)
			{
				return nextStat._iStep;//       
			}
		}
	}
	return -1;
}


void init()
{
	printf("        (m*n):");
	scanf("%d %d",&iM,&iN);
	printf("       (1   ，0   )：
");
	for(int i = 0 ; i < iM ; i++)
	{
		for(int j =0 ; j < iN; j++)
		{
			//iArrMaze[i][j] = 
			scanf("%d",*(iArrMaze + i ) + j);
			bMark[i][j] = false;
		}
	}
	printf("
       :");
	scanf("%d %d",&iBegX,&iBegY);
	printf("
       :");
	scanf("%d %d",&iEndX,&iEndY);	
}

//      ，      ，          。            
void DFS(int iBegX,int iBegY)//       ，             
{
	for(int i = 0 ; i < 4 ; i++ )
	{
		int iNx = iBegX + iArrGo[i][0];
		int iNy = iBegY + iArrGo[i][1];

		//          
		if(iNx < 0 || iNx >= iM ||  iNy < 0 || iNy >= iN)
		{
			continue;
		}
		//           
		if(1 == iArrMaze[iNx][iNy])
		{
			continue;
		}
		//      
		if(iNx == iEndX && iNy == iEndY)
		{
			//printf("
      
");
			isSuccess = true;
			return;
		}
		//    ，         （1）
		iArrMaze[iNx][iNy] = 1;
		//        
		DFS(iNx,iNy);
		//    ，      ，           （0）
		iArrMaze[iNx][iNy] = 0;

		if(isSuccess == true)
		{
			return;
		}
	}
	//printf("
      
");
}

void process()
{
	Stat statBeg(iBegX,iBegY,0);
	queueStat.push(statBeg);
	int iRes = BFS(iM,iN);
	if(iRes != -1)
	{
		printf("
   (%d,%d)  %d       (%d,%d)
",iBegX,iBegY,iRes,iEndX,iEndY);
	}
	else
	{
		printf("
   (%d,%d)      (%d,%d)
",iBegX,iBegY,iEndX,iEndY);
	}
}

/*
    ：
  :9 ,  :9
    :1,1
    :7,7
1	1	1	1	1	1	1	1	1
1	0	0	0	0	0	0	0	1
1	0	1	1	0	1	1	0	1
1	0	1	0	0	1	0	0	1
1	0	1	0	1	0	1	0	1
1	0	0	0	0	0	1	0	1
1	1	0	1	1	1	1	1	1
1	0	0	0	0	0	0	0	1
1	1	1	1	1	1	1	1	1
*/

int iMaze[9][9] = { 
{1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,1},
{1,0,1,1,0,1,1,0,1},
{1,0,1,0,0,1,0,0,1},
{1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,1,0,1},
{1,1,0,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1}
};

int startI = 1,startJ = 1;//  
int endI = 7 ,endJ = 7;//  
void printMaze()
{
	for(int i = 0 ; i < 9 ; i++ )
	{
		for(int j = 0 ; j < 9 ; j++)
		{
			if(iMaze[i][j]==1)
			{
				printf("#");
			}
			else
			{
				printf(" ");
			}
		}
		printf("
");
	}
}

void visit(int i,int j)
{
	iMaze[i][j] = 2;
	if(i==endI && j==endJ)
	{
		printf("
    :
");
		for(int m = 0 ; m < 9 ; m++)
		{
			for(int n = 0 ; n < 9 ; n++)
			{
				if(iMaze[m][n]==1)
				{
					printf("#");
				}
				else if(iMaze[m][n]==2)
				{
					printf("%");
				}
				else
				{
					printf(" ");
				}
			}
			printf("
");
		}
	}

	if(iMaze[i][j+1]==0)
	{
		visit(i,j+1);
	}
	if(iMaze[i+1][j]==0)
	{
		visit(i+1,j);
	}
	if(iMaze[i][j-1]==0)
	{
		visit(i,j-1);
	}
	if(iMaze[i-1][j]==0)
	{
		visit(i-1,j);
	}
	iMaze[i][j] = 0;
}

int main(int argc,char* argv[])
{
	/*init();
	process();
	DFS(iBegX,iBegY);
	if(isSuccess)
	{
		printf("
   (%d,%d)      (%d,%d)
",iBegX,iBegY,iEndX,iEndY);
	}
	else
	{
		printf("
   (%d,%d)      (%d,%d)
",iBegX,iBegY,iEndX,iEndY);
	}*/
	visit(startI,startJ);
	system("pause");
	getchar();
	return 0;
}