蔡子经数据结构6.13

#include <stdlib.h>
#include <string.h>

#define MAXN 100
int G[MAXN][MAXN];
//我是实在没想到这个遍历方向的前后竟然对效率影响这么大
//int dir[8][2] = {
//    {1,2},{2,1},
//    {2,-1},{1,-2},
//    {-1,-2},{-2,-1},
//    {-1,2},{-2,1}
//    };
int dir[8][2]={
    {1,2},{2,1},
    {2,-1},{1,-2},
    {-1,-2},{-2,-1},
    {-2,1},{-1,2}
};
int n = 8, m = 8;//8行8列的棋盘
int path[65][3];

void ()
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            printf("%d ",G[i][j]);
        }
        puts("");
    }
    puts("");
}

void dfs(int x, int y, int cnt)
{
    if(cnt == n*m)
    {
//        print();
        for(int i = 0; i < cnt; ++i)
        {
            printf("%d %d %dn",path[i][0],path[i][1],path[i][2]);
        }
        exit(0);
    }
    int tx,ty;
    for(int k = 0; k < 8; ++k)
    {
        tx = x + dir[k][0];
        ty = y + dir[k][1];
        if(tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
        if(G[tx][ty]) continue;
        G[tx][ty] = cnt+1;
        path[cnt][0] = tx;
        path[cnt][1] = ty;
        path[cnt][2] = cnt-1;
        dfs(tx, ty, cnt+1);
        G[tx][ty] = 0;
    }
    return ;
}

int main()
{
    memset(path, 0, sizeof(path));
    memset(G, 0, sizeof(G));
    G[0][0] = 1;
    path[0][0] = 0;
    path[0][1] = 0;
    path[0][2] = -1;
    dfs(0,0,1);
    return 0;
}