栈的应用--马踏棋盘-DFS搜索

按走棋规则进行移动。走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。

实现思路：DFS 搜索（因为我们的马要踏遍所有的方格，所以我们在这里不需要visted数组，因为如果我们要判断是否走过的话，完全就可以用棋盘是否等于零来判断,同时也提高了一丢丢效率）

实现代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#define ROW  8
#define COL  8

int integer[ROW][COL] ;
int  print(int integer[ROW][COL]);

int dir[8][2]={
    {1,2},{2,1},
    {2,-1},{1,-2},
    {-1,-2},{-2,-1},
    {-2,1},{-1,2}
}  ;     //方向数组,代表 8  个方向

int check(int x,int y)
{
    if(x< 0 || y<0 || x>= ROW || y>= COL || integer[x][y]  !=  0 )    //不是0 ，就不能走了 
        return 0;
    return 1;
}

int dfs(int x,int y ,int step_num)    //已经踏到了  x , y ，即x,y  可踏
{
    int xx,yy ,i ;
    if(step_num == 65 )  //思考一下为什么是65 ？当下面step_num == 63赋值完成后时，step_num === 64 进入dfs ，遇到if 终止程序了，故64并没有被赋值
    {
        print(integer);
        exit(1);
    }
    for(i= 0;i< 8 ;i++)   //  8 个方向 
    {
        xx =  x + dir[i][0];
        yy =  y + dir[i][1];
        if(check(xx,yy))  //xx ,yy 可踏上去
        {
            integer[xx][yy]=step_num;
            dfs(xx,yy,step_num+1) ; //DFS 易错点
            integer[xx][yy]= 0;    //回朔
        }
    }
    return 0;
}
int print(int integer[ROW][COL])
{
    int i,j;
    for(i=0;i<ROW ;i++)
    {
        for(j=0 ;j<COL ;j++)
        {
            printf("%6d",integer[i][j]);
        }
        printf("

");
    }
}
int main(void)
{
    int i,j ;
    memset(integer,0,sizeof(integer));
    integer[0][0]= 1;
    dfs(0,0,2) ; 
}

运行截图：

PS :从（0，0）点出发很快，但从其他任何一个点出发都极其的慢，可能得需要几天吧。So,效率可以说是非常的低下了，必须得想其他的办法才行！！