+Ȧ

1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色问题 6、八皇后问题 7、原四则表达式求值 8、k阶斐波那契序列 9、遍历二叉树 10、编写DFS算法的非递归

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

int maze[11][11]={{0,0,0,0,0,0,0,0,0,0,0},{0,2,2,2,2,2,2,2,2,2,2},{0,2,0,0,2,0,0,0,2,0,2},{0,2,0,0,2,0,0,0,2,0,2},{0,2,0,0,0,0,2,2,0,0,2},{0,2,0,2,2,2,0,0,0,0,2},{0,2,0,0,0,2,0,0,0,0,2},{0,2,0,2,0,0,0,2,0,0,2},{0,2,0,2,2,2,0,2,2,0,2},{0,2,2,0,0,0,0,0,0,0,2},{0,2,2,2,2,2,2,2,2,2,2}};

int stack[200][3];//stack[][i],i=0..direction i=1..curpositionY i=2..curpositionX

int main()
{
    int startx=2,starty=2,endx=9,endy=9;//起点
    void PrintMaze(),GoMaze(int,int,int,int);

	
	PrintMaze();
	GoMaze(startx,starty,endx,endy);
	PrintMaze();
    
	return 1;
} 

void GoMaze(int startx,int starty,int endx,int endy)
{
	
	
	int j=startx,i=starty,curstep=1;

	do{
		if(maze[i][j]==0)//能走就走
		{
			maze[i][j]='*';
			
			stack[curstep][0]=1;
			stack[curstep][1]=i;
			stack[curstep][2]=j;
			
			if(i==endx&&j==endy){
                                 printf("TURE\n");
                                 curstep=-1;
                                 }
                                
			j++;
			curstep++;
		}
		else//不能走就退栈
		{
			if(curstep!=0)
			{
				curstep--;i=stack[curstep][1];j=stack[curstep][2];
				while(stack[curstep][0]==4&&curstep!=0)//若四面都走过
				{
					maze[i][j]='#';//#表示此路不通
				    curstep--;i=stack[curstep][1];j=stack[curstep][2];//再退
                   }
                   if(stack[curstep][0]<4&&curstep!=0)
                   {
                                          stack[curstep][0]+=1;//改变方向
                                         
                                          
                                          
                                          
					switch(stack[curstep][0])//转向走
                    {
                           
                             case 2:i+=1;break;
                             case 3:j-=1;break;
                             case 4:i-=1;break;
                             }
                             curstep++;
                            
				}
			}
		}
	}while(curstep!=0);
	
}


void PrintMaze()
{
      int i,j;
      for(i=1;i<11;i++)
      {
                       for(j=1;j<11;j++)
					   {
						   if(maze[i][j]=='#')
							   printf("%c ",0);
						   else
							   printf("%c ",maze[i][j]);
					   }
					   

					   printf("\n");
	  }
getchar();
}