首页 > 代码库 > 马踏棋盘代码分析

马踏棋盘代码分析

马踏棋盘代码分析

                         (因为最近数据结构讲到图和网,听是能听懂,可是一到代码上,就发现问题很多,因此将马踏棋盘的代码拿出来分析下,貌似有些不对头,其实呢是因为不想写其余的作业,所以找个借口)

说到马踏棋盘,这样说,就是一个8*8的棋盘,指定一个位置,让马走日字,将棋盘上的点全部走完。

   先说说思路:首先指定位置,在这个位置的基础上走一个位置,然后再在这个基础上走日字,现在面临一个问题,要是走着走着,突然有一次,就那么的卡住在那里了,怎么走都不行,可是全局看下,会发现,还有空点没有踏到,那么怎么办?看来这条路不通了,那就得重新的找一条路,怎么从一条路到另一条路呢?那就是退回,要退回,必须有退回的路,因此呢,要有标记,不然,就找不到退回的路了,退回到另一条路,然后继续探索,走日字,卡住了就退,哦,这里要记得将原来路也记一下,不然,你有可能重走这条不归路。就这样不停的走,不停地退,最终就会找到一条你想找的路。大体思路就是这样的,思路简单,用代码写起来,一定要逻辑清楚,我就是经常混在这种情况下,出不来进不去。

   恩,来看代码:

   声明:是MAXSIZE是100

  先定义一个8*8的棋盘:

   int board[8][8];          

  棋盘要进行初始化:N是8

  for(i=0;i<N;i++)                    

     for(j=0;j<N;j++)

         board[i][j]=0;

那么现在要输入马踏的位置,这就需要用户自己输入:记得要进行完善,要是用户输入的坐标不正确,要提示重新输入:

while(1)

printf("Please enter the location of the first step of the horse(1<=x<=8 and 1<=y<=8)\n");

printf("Input x = "); 

scanf("%d",&x);         //输入起始位置的横坐标

printf("Input y = "); 

scanf("%d",&y);         //输入起始位置的纵坐标

if(x>=1&&x<=8&&y>=1&&y<=8)

break;  //若输入的坐标超出所给棋盘的允许范围则跳出循环

printf("Your input is worng!!!\n");

}

当输入正确后,就应该将值传进去:调用起始坐标函数

 InitLocation(x-1,y-1)

这里就要用到栈:利用栈的特点,来记录走过的路

栈的定义:

struct Stack

{                  

int i;                  //行坐标

int j;                  //列坐标

         int director;           //存储方向

}stack[MAXSIZE]; 

同时定义了一个栈指针:用来记录栈的元素进入和删除,相当于计数器

int top=-1;              

然后是InitLocation函数

void InitLocation(int xi,int yi)

                          top++;                  //栈指针指向第一个栈的底层

                            stack[top].i=xi;           //将起始位置的横坐标进栈

                            stack[top].j=yi;           //将起始位置的纵坐标进栈

                            stack[top].director=-1;     //将起始位置的尝试方向赋初值

                            board[xi][yi]=top+1;       //标记棋盘

                            if(TryPath(xi,yi))            //调用马儿探寻函数,如果马儿探寻整个棋盘返回1否则返回0

                            Display();         //输出马儿的行走路径

                            else                    

                             printf("sorry ,There is no solution");     

}

上面有两个函数:TryPath(x,y)和Display();

 尝试路径:

int Htry1[8]={1,-1,-2,2,2,1,-1,-2}; 

//存储马各个出口位置相对当前位置行下标的增量数组

int Htry2[8]={2,-2,1,1,-1,-2,2,-1};                 

//存储马各个出口位置相对当前位置列下标的增量数组

int TryPath(int i,int j)

int find,director,number,min;        

int i1,j1,h,k,s;              //定义几个临时变量

int a[8],b1[8],b2[8],d[8];     //定义几个临时数组

while(top>-1)                 //栈不空时循环

for(h=0;h<8;h++)    //用数组a[8]记录当前位置的下一个位置的可行路径的条数

number=0; 

i=stack[top].i+Htry1[h];

j=stack[top].j+Htry2[h];

b1[h]=i;

b2[h]=j; 

if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)    //如果找到下一位置

{

for(k=0;k<8;k++)

i1=b1[h]+Htry1[k];

               j1=b2[h]+Htry2[k]; 

           if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8) //如果找到下一位置   

number++;              //记录条数

    a[h]=number;                   //将条数存入数组a[8]中

}

for(h=0;h<8;h++)     //根据可行路径条数小到大按下表排序放入数组d[8]中

{  

min=9; 

for(k=0;k<8;k++)

if(min>a[k]) 

min=a[k]; 

d[h]=k;    //将下表存入数组d[8]中

         s=k;

    a[s]=9;

      director=stack[top].director;     

if(top>=63)                 //如果走完整个棋盘返回

return (1); 

find=0;                     //表示没有找到下一个位置

for(h=director+1;h<8;h++)   //向八个方向进行探寻

i=stack[top].i+Htry1[d[h]];

    j=stack[top].j+Htry2[d[h]]; 

if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置

find=1;       //表示找到下一个位置

break;

}

if(find==1)          //如果找到下一个位置进栈

stack[top].director=director; //存储栈结点的方向

top++;                      //栈指针前移进栈

stack[top].i=i;

stack[top].j=j; 

stack[top].director=-1;    //重新初始化下一栈结点的尝试方向

board[i][j]=top+1;         //标记棋盘

else                           //否则退栈

{  

board[stack[top].i][stack[top].j]=0;  //清除棋盘的标记

top--;                     //栈指针前移退栈

}

return (0);   

}

打印棋盘:board[i][j]里已经记录了走的次序,只需输出即可

void Display()

 

    int i,j; 

    for(i=0;i<N;i++)

for(j=0;j<N;j++) 

printf("\t%d  ",board[i][j]);  //输出马儿在棋盘上走过的路径

printf("\n\n");

printf("\n");

}

恩恩 结束了,哦在来个运行结果截图:

 

 

 

 

 

 

 

 

 

 

 

            by:暖暖

           20141124

马踏棋盘代码分析