骑士周游算法分析--用数组实现.txt

数据结构 之骑士周游算法

算法思想:
用一个二维的数组stack[36][3]充当栈的作用,用来记录36个位置的行,列,以及方向.设置全程标量top,用来指向当前位置.用push()和pop()函数分别实现压栈和出栈.
start()函数则是具体实现骑士周游算法的函数.具体思想见注释.
#include<stdio.h>
#include<conio.h>
#include <stdio.h>
int stack[36][3];//设置一个全程的数组
int top=0;//设置全程的变量top.
//push()函数用来表示压栈操作
void push(int i,int j,int k)
{                 stack[top][0]=i;
				  stack[top][1]=j;
				  stack[top][2]=k;
				  top++;
}
//pop（）函数用来表示出栈操作
void pop()
{top--;
}
//start()函数用来具体执行骑士周游的算法
void start()
{   int y,z,v=0;
	int i,j;
	int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};//设置8个方向
	int c[6][6];//设置一个二维数组，用来打印出周游的具体路线
	for(i=0;i<6;i++)
	  {for(j=0;j<6;j++)
	   c[i][j]=0;
	  }//初始化数组
	 printf("input y:");
	 scanf("%d",&x);
	 printf("input z:");
	 scanf("%d",&y);//由用户输入初始起跳位置
	 int account=0;//设置一个计数器，用来清楚的显示骑士走的路线
	 while(account<35)
	 {
		 while(v<8)
		  {
			  i=x+move[v][0];
			  j=y+move[v][1];
			  if(i>=0&&i<=5&&j>=0&&j<=5&&c[i][j]==0)
				{ push(x,y,v+1);//若一个位置可走，则把前一个位置及下一个要走的方向压栈
				  account++;
				  c[x][y]=account;
				  x=i;
				  y=j;
				  v=0;
			}
			  else v++;//若一个位置走不通，则换一个方向再试
			}
		   if(v==8&&account>0&&account!=35)//加入8个方向全已经走过，则弹出刚进
栈的那个元素。

			{ pop();
			 // y=q->row;
			 // z=q->col;
			 // v=q->dir;
			   x=stack[top][0];
			   y=stack[top][1];
			   v=stack[top][2];
			   c[x][y]=0;//由于已经把c[x][y]上的元素弹出，则把该位置清零。			   
　　　　　　　　account--;
			 }
	   }
	   c[x][y]=36;//把最后一个元素置为36。
	   for(i=0;i<6;i++)//打印周游路线
		 {
		   for(j=0;j<6;j++)
			 {
				 printf("%4d",c[i][j]);
			 }
			printf("\n");
	   }
}

void main()
{printf("\n");
 start();
}

程序运行结果：
input y:1
input z:2
  36  21  12  27  30  19
  11  26   1  20  13  28
  22  35  14  29  18  31
  25  10  23   2   7   4
  34  15   8   5  32  17
   9  24  33  16   3   6

input y:3
input z:2
  26  21  12  35  32  19
  11  36  25  20  13  34
  24  27  22  33  18  31
   7  10   1  16   3  14
  28  23   8   5  30  17
   9   6  29   2  15   4