设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › 数据结构与算法 › 鱼c马踏棋盘
返回列表 发新帖
查看: 4682|回复: 5

[已解决]鱼c马踏棋盘

[复制链接]
wyj222
发表于 2021-6-21 17:30:55 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
鱼c马踏棋盘如果用非递归该怎么修改呀
最佳答案
月排行榜 / 总排行榜
临时号
2022-6-11 00:11:05
  1. #include<stdio.h>

  3. int chess[12][12]={0};
  4. int cnt = 0;
  5. int countChess = 0;
  6. int move[8][2]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
  7. int initChess();
  8. void printChess();
  9. void horse(int x, int y);
  10. struct Node{
  11.         int x;
  12.         int y;
  13.         int i;
  14. }chessStep[64];
  15. int top = -1;
  16. int main(void){
  17.         initChess();
  18.         int i,j;
  19.         for(i=2; i<10; i++){
  20.                 for(j=2; j<10; j++){
  21.                         cnt = 1;
  22.                         chess[i][j] = cnt;                        
  23.                         horse(i,j);
  24.                 }
  25.         }
  26.         
  27. }
  28. void horse(int x, int y){
  29.         int i = 0;
  30.         while(cnt < 64){
  31.                 int row;
  32.                 int col;
  33.                 for(i; i<8; i++){
  34.                         row = x + move[i][0];
  35.                         col = y + move[i][1];
  36.                         if(chess[row][col] == 0){
  37.                                 break;
  38.                         }
  39.                 }  
  40.                 if(i != 8){
  41.                         chess[row][col] = ++cnt;
  42.                         chessStep[++top].x = x;
  43.                         chessStep[top].y = y;
  44.                         chessStep[top].i = i;
  45.                         if(cnt == 64){
  46.                                 printChess();
  47.                                 chess[row][col] = 0;
  48.                                 
  49.                                 i = chessStep[top].i + 1;
  50.                                 x = chessStep[top].x;
  51.                                 y = chessStep[top].y;
  52.                                 
  53.                                 top--;
  54.                                 cnt--;
  55.                         }else{
  56.                                 x = row;
  57.                                 y = col;
  58.                                 i = 0;
  59.                         }
  60.                 }else{
  61.                         chess[x][y] = 0;

  63.                         i = chessStep[top].i + 1;
  64.                         x = chessStep[top].x;
  65.                         y = chessStep[top].y;
  66.                                 
  67.                         top--;
  68.                         cnt--;
  69.                 }
  70.                 if(top == -1){
  71.                         break;
  72.                 }
  73.         }        
  74. }
  75. int initChess(){
  76.         int i,j;
  77.         for(i=0; i<12; ++i){
  78.                 for(j=0; j<12; ++j){
  79.                         if(i<2 || i>9 || j<2 || j>9){
  80.                                 chess[i][j]=-1;
  81.                         }
  82.                 }
  83.         }
  84. }
  85. void printChess(){
  86.         ++countChess;
  87.         printf("第%d个解是：\n", countChess);
  88.         int i,j;
  89.         for(i=2; i<10; ++i){
  90.                 for(j=2; j<10; ++j){
  91.                         printf("%2d ",chess[i][j]);
  92.                 }
  93.                 printf("\n");
  94.         }
  95. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

连帅帅
发表于 2021-6-21 17:35:14 | 显示全部楼层
问题描述模糊，建议贴上代码，或者原题
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

wyj222
 楼主| 发表于 2021-6-21 17:36:29 | 显示全部楼层
连帅帅 发表于 2021-6-21 17:35
问题描述模糊，建议贴上代码，或者原题

鱼c数据结构P61讲的马踏棋盘算法
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

wyj222
 楼主| 发表于 2021-6-21 17:38:50 | 显示全部楼层
wyj222 发表于 2021-6-21 17:36
鱼c数据结构P61讲的马踏棋盘算法

#include <stdio.h>
#include <time.h>

#define X 8
#define Y 8

int chess[X][Y];

// 找到基于(x,y)位置的下一个可走的位置
int nextxy(int *x, int *y, int count)
{
        switch(count)
        {
                case 0:
                        if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
                        {
                                *x = *x + 2;
                                *y = *y - 1;
                                return 1;
                        }
                        break;

                case 1:
                        if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
                        {
                                *x = *x + 2;
                                *y = *y + 1;
                                return 1;
                        }
                        break;

                case 2:
                        if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
                        {
                                *x = *x + 1;
                                *y = *y - 2;
                                return 1;
                        }
                        break;

                case 3:
                        if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
                        {
                                *x = *x + 1;
                                *y = *y + 2;
                                return 1;
                        }
                        break;

                case 4:
                        if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
                        {
                                *x = *x - 2;
                                *y = *y - 1;
                                return 1;
                        }
                        break;

                case 5:
                        if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
                        {
                                *x = *x - 2;
                                *y = *y + 1;
                                return 1;
                        }
                        break;

                case 6:
                        if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
                        {
                                *x = *x - 1;
                                *y = *y - 2;
                                return 1;
                        }
                        break;

                case 7:
                        if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
                        {
                                *x = *x - 1;
                                *y = *y + 2;
                                return 1;
                        }
                        break;

                default:
                        break;
        }

        return 0;
}

void print()
{
        int i, j;

        for( i=0; i < X; i++ )
        {
                for( j=0; j < Y; j++ )
                {
                        printf("%2d\t", chess[i][j]);
                }
                printf("\n");
        }
        printf("\n");
}

// 深度优先遍历棋盘
// (x,y)为位置坐标
// tag是标记变量，每走一步，tag+1
int TravelChessBoard(int x, int y, int tag)
{
        int x1=x, y1=y, flag=0, count=0;
        
        chess[x][y] = tag;

        // 如果tag==X*Y，则完成整个棋盘的遍历
        if( tag == X*Y )
        {
                print();
                return 1;
        }

        flag = nextxy(&x1, &y1, count);
        while( 0==flag && count < 7 )
        {
                count++;
                flag = nextxy(&x1, &y1, count);
        }

        while( flag )
        {
                if( TravelChessBoard(x1, y1, tag+1) )
                {
                        return 1;
                }

                x1 = x;
                y1 = y;
                count++;

                flag = nextxy(&x1, &y1, count);
                while( 0==flag && count < 7 )
                {
                        count++;
                        flag = nextxy(&x1, &y1, count);
                }
        }

        if( 0 == flag )
        {
                chess[x][y] = 0;
        }

        return 0;
}

int main()
{
        int i, j;
        clock_t start, finish;

        start = clock();

        for( i=0; i < X; i++ )
        {
                for( j=0; j < Y; j++ )
                {
                        chess[i][j] = 0;
                }
        }

        if( !TravelChessBoard(2, 0, 1) )
        {
                printf("抱歉，马踏棋盘失败鸟~\n");
        }

        finish = clock();
        printf("\n本次计算一共耗时: %f秒\n\n", (double)(finish-start)/CLOCKS_PER_SEC);

        return 0;
}
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

时欢3
发表于 2022-6-7 09:59:57 | 显示全部楼层
1
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

临时号
发表于 2022-6-11 00:11:05 | 显示全部楼层    本楼为最佳答案   
  1. #include<stdio.h>

  3. int chess[12][12]={0};
  4. int cnt = 0;
  5. int countChess = 0;
  6. int move[8][2]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
  7. int initChess();
  8. void printChess();
  9. void horse(int x, int y);
  10. struct Node{
  11.         int x;
  12.         int y;
  13.         int i;
  14. }chessStep[64];
  15. int top = -1;
  16. int main(void){
  17.         initChess();
  18.         int i,j;
  19.         for(i=2; i<10; i++){
  20.                 for(j=2; j<10; j++){
  21.                         cnt = 1;
  22.                         chess[i][j] = cnt;                        
  23.                         horse(i,j);
  24.                 }
  25.         }
  26.         
  27. }
  28. void horse(int x, int y){
  29.         int i = 0;
  30.         while(cnt < 64){
  31.                 int row;
  32.                 int col;
  33.                 for(i; i<8; i++){
  34.                         row = x + move[i][0];
  35.                         col = y + move[i][1];
  36.                         if(chess[row][col] == 0){
  37.                                 break;
  38.                         }
  39.                 }  
  40.                 if(i != 8){
  41.                         chess[row][col] = ++cnt;
  42.                         chessStep[++top].x = x;
  43.                         chessStep[top].y = y;
  44.                         chessStep[top].i = i;
  45.                         if(cnt == 64){
  46.                                 printChess();
  47.                                 chess[row][col] = 0;
  48.                                 
  49.                                 i = chessStep[top].i + 1;
  50.                                 x = chessStep[top].x;
  51.                                 y = chessStep[top].y;
  52.                                 
  53.                                 top--;
  54.                                 cnt--;
  55.                         }else{
  56.                                 x = row;
  57.                                 y = col;
  58.                                 i = 0;
  59.                         }
  60.                 }else{
  61.                         chess[x][y] = 0;

  63.                         i = chessStep[top].i + 1;
  64.                         x = chessStep[top].x;
  65.                         y = chessStep[top].y;
  66.                                 
  67.                         top--;
  68.                         cnt--;
  69.                 }
  70.                 if(top == -1){
  71.                         break;
  72.                 }
  73.         }        
  74. }
  75. int initChess(){
  76.         int i,j;
  77.         for(i=0; i<12; ++i){
  78.                 for(j=0; j<12; ++j){
  79.                         if(i<2 || i>9 || j<2 || j>9){
  80.                                 chess[i][j]=-1;
  81.                         }
  82.                 }
  83.         }
  84. }
  85. void printChess(){
  86.         ++countChess;
  87.         printf("第%d个解是：\n", countChess);
  88.         int i,j;
  89.         for(i=2; i<10; ++i){
  90.                 for(j=2; j<10; ++j){
  91.                         printf("%2d ",chess[i][j]);
  92.                 }
  93.                 printf("\n");
  94.         }
  95. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-5-11 23:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表