精华内容
下载资源
问答
  • 马踏棋盘c++
    2022-07-20 20:26:15
    • 需求分析:包含题目要求,程序功能,运行方式,测试数据等

    将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只能进入一次,走遍棋盘上全部64个方格。编写非递归程序,求出马的行走路线,并按求出的行走路线,将数字1,2,3,…,64依次填入8×8的方阵,输出之。要求给出其中的100个解。

    为了完成目的,需要定义一个二维数组Board[8][8],同时定义在x,y方向棋子可以行走的方向xd [],yd [],为了简便,定义define  M  8,方便调试程序。

    同时定义基础结构和栈相关函数。

    定义顺序栈结构:               定义存储马位置和方向的结构体:

    typedef struct{                                typedef struct{

         pos  *base;                                    int x,y;//位置

         pos  *top;                                      

         int stacksize;                                    int d;//方向

    } SqStack;//顺序栈定义                        }pos;//存储马参数结构体

    StackEmpty(SqStack S)判断栈是否空;Push(SqStack &S, pos e) 插入元素e为新的栈顶元素;Pop(SqStack &S, pos &e)删除S的栈顶元素,用e返回其值。

                 通过输入棋子不同的初始值,把走过位置数据放入栈中,当出现错误时退栈返回,再向另一个方向行走,循环这个步骤,直到走完整个棋盘时,输出存入二维数组Board的值。

    • 概要设计:包含抽象数据类型定义,程序模块等

    定义棋盘和方向:

    int Board[M][M] = {0};//棋盘,设置为二维数组,做全局变量

    int xd [] = { -2, -1, 1, 2, 2, 1, -1, -2 };//可以在x方向上行走的方向

    int yd [] = { 1, 2, 2, 1, -1, -2, -2, -1 };//可以在y方向上行走的方向

    定义栈初始化函数InitStack(SqStack &S)构造一个空栈S。StackEmpty(SqStack S)判断栈是否空;Push(SqStack &S, pos e) 插入元素e为新的栈顶元素;Pop(SqStack &S, pos &e)删除S的栈顶元素,用e返回其值。

    定义pos结构体存储棋子位置,方向,在算法调用中实现马踏棋盘。程序定义栈模块,马踏棋盘模块,棋盘与方向模块,栈模块用于存储试错,马踏棋盘模块用于调用栈模块进行在棋盘上赋值并正确输入棋子的位置和方向。

    #include <iostream>
    #include<cstdlib>
    #include <stack>
    #include <iomanip>
    
    using namespace std;
    
    #define MAXSIZE 2147483647//栈长度设置为int型最大值
    #define M 8
    
    typedef struct{
        int x,y;//位置
        int d;//方向
    }pos;//存储棋子参数结构体
    
    typedef struct{
        pos  *base;
        pos  *top;
        int stacksize;
    } SqStack;//顺序栈定义
    
    int Board[M][M] = {0};//棋盘,设置为二维数组,做全局变量
    int xd [] = { -2, -1, 1, 2, 2, 1, -1, -2 };//可以在x方向上行走的方向
    int yd [] = { 1, 2, 2, 1, -1, -2, -2, -1 };//可以在y方向上行走的方向
    
    void InitStack(SqStack &S) {//构造一个空栈S
        S.base = new pos[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
        if (!S.base)
            exit(0); //存储分配失败
        S.top = S.base; //top初始为base,空栈
        S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
    }
    
    bool StackEmpty(SqStack S){//判断栈是否空
        if(S.top == S.base){
            return true;
        }else{
            return false;
        }
    }
    
    bool StackOverflow(SqStack S){//判断栈是否满
        if (S.top - S.base == S.stacksize){
            return true;
        }else{
            return false;
        }
    }
    
    void Push(SqStack &S, pos e) {//插入元素e为新的栈顶元素
        if (S.top - S.base == S.stacksize)
            cout<<"栈满。"; //栈满
        *(S.top++) = e; //元素e压入栈顶,栈顶指针加1
    }
    
    pos Pop(SqStack &S, pos &e){//删除S的栈顶元素,用e返回其值
        if(S.top == S.base)
            cout<<"栈空";
        e = *--S.top;
        return e;
    }
    
    pos getTop(SqStack &S){//取栈顶元素值
        if (S.top != S.base)//栈非空
            return *(S.top - 1);//返回栈顶元素的值,栈顶指针不变
    }
    
    void output(){//输出马行走的结果
        for(int x = 0;x<M;x++){
            for(int y = 0;y<M;y++){
                cout<<Board[x][y]<<" ";
            }
            cout<<endl;
        }
        cout<<"--------以上为输出结果-----------"<<endl;
    }
    
    void horsePlay(int x,int y){
        int step = 1;//定义步数,目的是将步数赋给棋盘上二维数组
        SqStack stack;
        pos pos;
        InitStack(stack);//初始化栈
        pos.x = x;pos.y = y;//第一个棋子的位置
        pos.d = 0;//第一个方向
        Push(stack,pos);//将棋子位置入栈
        Board[x][y] = step++;//第一个位置赋值为1,赋值后step为2
        while (!StackEmpty(stack)) {//栈非空时继续循环
            int static num = 1;//定义循环次数
            if(step > M*M && num<=100){//当步数大于棋盘数输出结果
                cout<<"这是第"<<num++<<"个结果"<<endl;
                output();
            }
            Pop(stack,pos);//出栈,将栈中数据赋给位置结构体
            int forword = 0;//定义用于方向的int常量forward
            for(forword = pos.d;forword<8;forword++){//试探
                if((Board[pos.x+xd[forword]][pos.y+yd[forword]]) == 0 &&
                   (pos.x+xd[forword]<M && pos.y+yd[forword]<M) &&
                   (pos.x+xd[forword]>=0 && pos.y+yd[forword]>=0)){
                    break;//当试探成功时结束循环对棋盘赋值
                }
            }
            if(forword >= 8){//当方向大于8时候,试探错误,回退步数
                Board[pos.x][pos.y] = 0;
                step--;
            }
            else {//对棋盘赋值
                pos.d = forword+1;//向下一个方向
                Push(stack,pos);//下一个方向结果入栈
                pos.x = pos.x + xd[forword];//马跳到下一个正确的坐标
                pos.y = pos.y + yd[forword];
                pos.d = 0;//方向置零
                Board[pos.x][pos.y] = step++;//步数赋值给棋盘
                Push(stack,pos);//当前入栈,为下一步试探准备
            }
        }
    }
    
    int main()
    {
        int x,y;
        cout << "输入马在棋盘中的位置x:"<<endl;cin>>x;
        cout << "输入马在棋盘中的位置y:"<<endl;cin>>y;
        horsePlay(x,y);
        return 0;
    }
    
    • 详细设计:抽象数据类型以及程序模块的具体实现,算法设计思想

    构造一个空栈S, 初始化栈为顺序栈动态分配一个数组空间,插入元素e为新的栈顶元素,判断栈是否空,栈非空时继续循环,定义步数,目的是将步数赋给棋盘上二维数组。

    主函数中输入棋子位置,将棋子位置入栈,第一个位置在棋盘Board上赋值为1,赋值后step为2,定义循环次数static num,当步数大于棋盘数(64)时输出结果,出栈,将栈中数据赋给位置结构体,定义用于方向的int常量forward,试探,当棋子位置合法时(棋子在x和y坐标均在棋盘上)当试探成功时且方向在8个棋子可走的方向之内时结束循环对棋盘赋值(当方向大于8时,试探错误,回退步数,走过的地方赋值为0,步数减一)。

    对棋盘赋值,forword+1向下一个方向行走,并把下一个方向结果入栈,马跳到下一个正确的坐标,步数赋值给棋盘,方向置零,下一个坐标入栈,为下一步试探准备,当方向都错误时出栈并将前面结果赋值为0,步数减少,换方向继续行走,循环前面这些步骤,当步数大于棋盘数输出结果时,输出棋子行走的结果。

    • 调试分析:包括算法的时间复杂度和空间复杂度分析等

    算法horsePlay中,定义了栈非空时的while循环,里面还定义了试探方向的for循环,算法时间复杂度为n2;申请了栈的空间,空间复杂度为n。

    输出函数output定义了两个for循环输出Board上的值,时间复杂度为n2;只有棋盘的空间,空间复杂度为1。

    所以输出时,算法总的时间复杂度为n4,空间复杂度为n。

    调试的时候没有设置define  M ,而直接定义棋盘为8*8,调试时等待时间过久,后来先定义M为6,输出正确结果后再定义回8进行验证。

       没有在出栈时正确赋值给pos导致程序无法输入结果,后来在pop函数上设置取地址符号才得到正确出栈结果。

       没有理解方向d和forward的作用,错误使用两个数据,导致输出的结果只有01没有其他数据,需要将forword和d灵活运用在算法中指示方向并正确的出栈入栈保存数据,为棋子正确行走和棋盘正确赋值。

       调试时候栈的长度设置为8,无法输出结果,64时能输出部分结果,经过测试,栈要在100以上才能输出较多结果,因此定义为int类型的最大值2147483647。方便进行棋子在棋盘正中栈较多时进行运算。

    更多相关内容
  • 马踏棋盘算法(c++

    2017-12-12 19:52:49
    贪心算法,回溯法,哈密尔顿路径,马踏棋盘算法练习,
  • 中国象棋棋盘上,对任一位置上放置的一个马,均能选择一个合适的路线,使得该棋子能按象棋的 规则不重复地走过棋盘上的每一位置。
  • 马踏棋盘C语言的完整算法 vs2013下编译运行通过
  • 马踏棋盘:设计一个国际象棋的马踏遍棋盘的演示程序。将马随机放在国际象棋 8x8 棋盘 Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部 64 个方格。编制递归或非递归程序,...

    目录

    一、实验题目

    二、数据结构设计

    (一)存储结构设计

    (二)结点结构设计

    三、算法设计

    (一)函数设计

        1.方法一:深度优先遍历(递归)

        2.方法二:深度优先遍历+贪心算法(递归)

        3.方法三:深度优先遍历+贪心算法(非递归)

        4.menu()函数

    (二)算法描述

    四、完整代码

    五、测试与运行

    1.菜单

    2.第一种方法求解

    3.第二种方法求解

    4.第三种方法求解


    一、实验题目

        马踏棋盘:设计一个国际象棋的马踏遍棋盘的演示程序。将马随机放在国际象棋 8x8 棋盘 Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部 64 个方格。编制递归或非递归程序,求出马的行走路线,并按求出的行走路线输出。

        结果中输出:在方阵中输出 1-64 个行走足迹。

    二、数据结构设计

    (一)存储结构设计

        马踏棋盘问题的处理,在设计时注重对于顺序遍历的考虑,不需要涉及插入和删除操作,因此采用顺序表存储。设置一个容量为64的Adr_Stack[MAX_STEPS]( MAX_STEPS=64),通过其存储马的行走轨迹。

    (二)结点结构设计

        本设计中一条记录中涉及着较多的数据项,因此需要单独对数据域进行自定义变量类型。类型HORSE_CHESS_STACK中共存储三个数据项:x_adr为横轴坐标,y_adr为纵轴坐标,direction是运动的方向。

    typedef struct stack
    
    {
    
        int x_adr;     
    
        int y_adr;   
    
        int direction;
    
    }HORSE_CHESS_STACK;
    
    HORSE_CHESS_STACK Adr_Stack[64];

    三、算法设计

        马踏棋盘问题,既可以递归处理,也可以非递归处理。在设计时,采取三种方式求解,第一种为深度优先遍历递归求解,第二种为在深度优先遍历的基础上加入贪心算法求解递归求解,第三种为在深度优先遍历的基础上加入贪心算法求解非递归求解。

    (一)函数设计

        本设计中一共涉及十三个函数,通过这十三个函数的相互调用,实现马踏棋盘问题的求解。

        1.方法一:深度优先遍历(递归)

        第一种方法只需一个函数,Dfs()函数用来求解深度优先遍历递归求解;

    //深度优先遍历(递归)
    void Dfs( int path[8][8], int m, int n, int edge, int count)
    {
        if (count >= edge*edge) 
            return;
        if (m <= edge-1 && n <= edge-1 && m >= 0 && n >= 0 && path[m][n] == 0)
    	{
    		count++; 
    		path[m][n] = count; 
    		for (int i = 0;i < edge;i++)
    			Dfs(path, m + move_x[i], n + move_y[i], edge, count); 
    		return;
    	}
    	else
    		return;
    }
    

        2.方法二:深度优先遍历+贪心算法(递归)

        第二种方法也只需一个函数,Dfs_tx()函数用来求解深度优先遍历加贪心算法递归求解;

    //深度优先遍历+贪心算法(递归)
    void Dfs_tx(int flag[8][8], int path[8][8], int m, int n, int edge, int count, int found)
    {
        if(found)
            return;
        if(count >= edge*edge)
        {
            found += 1; 
            for(int i = 0; i < edge; i++)
            {
                for(int j = 0; j < edge; j++)
                    path[i][j] = flag[i][j];
            }
            return;
        }
        if(m > edge-1 || n > edge-1 || m < 0 || n < 0 || flag[m][n] != 0) 
            return; 
        count++; 
        flag[m][n] = count; 
        int count_next[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
        for (int i = 0; i < edge; i++)
        {
            int m_next = m + move_x[i];
            int n_next = n + move_y[i];     
            if (m_next < edge && n_next < edge && m_next >= 0 && n_next >= 0 && flag[m_next][n_next] == 0)
            {
                count_next[i] ++;
                for (int j = 0; j < edge; j++)
                {
                    int m_next_next = m_next + move_x[j];
                    int n_next_next = n_next + move_y[j];
                    if (m_next_next < edge && n_next_next < edge && m_next_next >= 0 && n_next_next >= 0 && flag[m_next_next][n_next_next] == 0)                
                            count_next[i]++;
                }
            }       
        }
        int opt_direct = 0;
        for (int i = 0; i < edge; i++)
        {
            if (count_next[opt_direct] == -1)
                opt_direct = i;
            if ((count_next[i] < count_next[opt_direct]) && count_next[i] != -1)
            {
                opt_direct = i;
            }
        }
        Dfs_tx( flag, path, m + move_x[opt_direct], n + move_y[opt_direct], edge, count, found); 
        flag[m][n] = 0;                
    }
    

        3.方法三:深度优先遍历+贪心算法(非递归)

        第三种方法涉及九个函数,首先是init()函数,对顺序表进行初始化操作;然后是print_stack()函数将栈中的情况输出以检验结果的正确性;第三第四个函数是push_stack()和pop_stack()函数,进行进栈和出栈操作;第五个mark_chess()是标记函数,用来标记马已经走过的地方;第六个print_chess_board()函数是将解决路径输出;第七个print_steps()是将每一步的横纵坐标输出,进而可以直观检验结果;第八个run_horse_tanxin()函数是核心函数,对于马踏棋盘用深度优先遍历加贪心算法非递归的处理;最后一个Dfs_tx_zhan()函数是对以上各个函数总的调用,共同实现深度优先遍历加贪心算法非递归方法对马踏棋盘问题的解决。

    //深度优先遍历+贪心算法(非递归)
    typedef struct stack
    {
        int x_adr;      
        int y_adr;    
        int direction;
    }HORSE_CHESS_STACK;
    int chess[ROW+1][COL+1];
    int dir[8][2] = {{2,-1},{-2,-1},{-2,1},{2,1},{1,-2},{-1,-2},{-1,2},{1,2}};
    int top;
    HORSE_CHESS_STACK Adr_Stack[MAX_STEPS];
    int out_stack;
    void init()
    {
        int n = MAX_STEPS;
        while(n--)
    	{
            Adr_Stack[n].x_adr = 0;
            Adr_Stack[n].y_adr = 0;
            Adr_Stack[n].direction = -1;
        }
        Adr_Stack[0].x_adr = 0;
        Adr_Stack[0].y_adr = 0;
        Adr_Stack[0].direction = -1;
        
        for(int i = 1;i <= ROW;i++)
    	{
            for(int j = 1;j <= COL;j++)
    		{
                chess[ROW][COL] = 0;
            }
        }  
        top = -1;
        out_stack = 0;
    }
    void print_stack()
    {
        cout<<"栈中情况:\n";
        for(int i = 0;i < MAX_STEPS;i++)
    	{
    		printf("x:%d  y:%d direction = %d\n",Adr_Stack[i].y_adr,Adr_Stack[i].x_adr,Adr_Stack[i].direction);
        }
        cout<<"\n\n";
    }
    void push_stack(int x_real,int y_real)
    {
        top++;
        Adr_Stack[top].x_adr = x_real;
        Adr_Stack[top].y_adr = y_real;
        Adr_Stack[top].direction = -1; 
    }
    void pop_stack()
    {
        Adr_Stack[top].x_adr = 0;
        Adr_Stack[top].y_adr = 0;
        Adr_Stack[top].direction = -1; 
        top--;
    }
    void mark_chess(int x,int y)
    {
        chess[y][x] = top + 1;
    }
    void print_chess_board()
    {
        cout<<"\t\t\troute:"<<endl;
        for(int i = 1;i <= ROW;i++)
    	{
    		cout<<"\t\t\t";
            for(int j = 1;j <= ROW;j++)
    		{
                printf("%4d ",chess[i][j]);
            }
            cout<<endl;
        }
        cout<<endl;
    }
    int t = 1;
    void print_steps()
    {
        printf("(%d,%d)",Adr_Stack[top].y_adr,Adr_Stack[top].x_adr);
        t++;
        if(t == ROW)
    	{
            cout<<endl;
            t = 0;
        }
    }
    void run_horse_tanxin()
    {
        int x_now,y_now;
        while(1)
    	{
            if(top >= MAX_STEPS - 1)
    		{
                print_chess_board();
                break;
            }
            x_now = Adr_Stack[top].x_adr;
            y_now = Adr_Stack[top].y_adr;
            int next[ROW] = {};
            for(int i = 0;i < ROW;i++)
    		{
                int x_next = x_now + dir[i][0];
                int y_next = y_now + dir[i][1];
                if((x_next > 0 && x_next <= COL) && (y_next > 0 && y_next <= ROW) && chess[y_next][x_next] == 0 )
    			{
                    for(int j = 0;j < ROW;j++)
    				{
                        int x_next_next = x_next + dir[j][0];
                        int y_next_next = y_next + dir[j][1];
                        if((x_next_next > 0 && x_next_next <= COL) && (y_next_next > 0 && y_next_next <= ROW) && chess[y_next_next][x_next_next] == 0)
    					{
                            next[i]++;
                        }
                    }
                }
            }
            int real_next[8] = {0};
            int k = 0;
            int t = ROW + 1;
            for(int i = 0;i < ROW;i++)
    		{
                t = ROW + 1;
                for(int j = 0;j < 8;j++)
    			{
                    if(next[j] < t)
    				{
                        real_next[i] = j;
                        t = next[j];
                        k = j;
                    }
                }
                next[k] = ROW + 1;
            }
            int dir_now = 0;
            for(dir_now = Adr_Stack[top].direction + 1;dir_now < ROW;dir_now++)
    		{
                int x_real = x_now + dir[real_next[dir_now]][0];
                int y_real = y_now + dir[real_next[dir_now]][1];
                Adr_Stack[top].direction += 1;
                if((x_real <= COL && x_real > 0) && (y_real <= ROW && y_real > 0) && chess[y_real][x_real] == 0)
    			{
                    push_stack(x_real,y_real);
                    mark_chess(x_real,y_real);
                    break;
                }
            }
            if(Adr_Stack[top].direction >= 7)
    		{
    			cout<<endl;
    			 printf("\n out:(%d,%d) \n",Adr_Stack[top].y_adr,Adr_Stack[top].x_adr);
                chess[Adr_Stack[top].y_adr][Adr_Stack[top].x_adr] = 0;
                out_stack++;
                pop_stack();
            }
            //print_stack(); 
            print_steps();
        }
    }
    void Dfs_tx_zhan(int m,int n)
    {
        init();
        push_stack(m,n);
        mark_chess(m,n);
        cout<<"\t\t\troute address:\n";
        printf("(%d,%d)",m,n);
        run_horse_tanxin();
    }
    

        4.menu()函数

        然后一个是menu()函数,实现菜单功能,对三种方法进行调用;另一个是main()主函数,进行输入操作,总体实现问题的求解。

    void menu()
    {
    	system("cls");
    	cout<<"\t\t\t马踏棋盘问题的解决:"<<endl;
    	cout<<"\t\t\t1.深度优先遍历(递归)"<<endl;
    	cout<<"\t\t\t2.深度优先遍历+贪心算法结合(递归)"<<endl;
    	cout<<"\t\t\t3.深度优先遍历+贪心算法结合(非递归)"<<endl;
    	cout<<"\t\t\t0.退出"<<endl;
    	cout<<"\t\t\t请输入选择:";
    	int sel;
    	cin>>sel;
    	if (sel == 0)
    		exit(0);
    	while(sel >3 ||sel <0)
    	{
    		cout <<"\t\t\t输入格式错误,请重新输入:";
    		cin>>sel;
    	}
        int m,n;
        int found = 0;
    	int edge;
    	cout<<"\t\t\t请输入棋盘的边长:";
        cin >> edge;
    	cout<<"\t\t\t请输入初始时马的位置:";
    	cin>>m >> n;
    	int flag[8][8]={0};
    	int path[8][8]={0};
    	DWORD start = timeGetTime();
    	if (sel == 1)
    	{
    		cout <<"\t\t\t下面是采用深度优先遍历(递归)得出的结果:"<<endl;
    		Dfs( path, m, n, edge, 0);
    	}
    	else if (sel == 2)
    	{
    		cout <<"\t\t\t下面是采用深度优先遍历+贪心算法结合(递归)得出的结果:"<<endl;
    		Dfs_tx( flag, path, m, n, edge, 0, found);
    	}
    	else if (sel == 3)
    	{
    		cout<<endl;
    		cout <<"\t\t\t下面是采用深度优先遍历+贪心算法结合(非递归)得出的结果:"<<endl;
    		Dfs_tx_zhan(m, n);
    	}
    	if (sel !=3)
    	{
    		for (int i = 0; i < edge; i++)
    		{
    			cout<<"\t\t\t";
    			for (int j = 0; j < edge; j++)
    				cout << path[i][j] << "\t";
    			cout << endl;
    		}
    	}
    	DWORD end = timeGetTime()-start;
    	cout<<"\t\t\t使用本方法所用时间为"<<end<<"ms"<<endl;
    	cout<<"\t\t\t按任意键返回菜单!"<<endl;
    	system("pause");
    	menu();
    }
    

    (二)算法描述

        算法思想:

        三种方法:第一种为深度优先遍历递归求解,第二种为在深度优先遍历的基础上加入贪心算法求解递归求解,第三种为在深度优先遍历的基础上加入贪心算法求解非递归求解。

        第一种:设置一个递归函数,先判断行动次数是否已经达到64次,若是则递归结束,否则继续进行递归。判断每一次的方向选择是否正确,以是否超出边界还有本个地点是否已经被走过为标准。当符合条件时表示这个方向是正确的,可以进行下一次的递归,否则需要考虑其他方向。

        第二种:第二种方法是建立在第一种方法的基础上的,总体思路与第一种相同,只是在下一步的选择上有了一定的改进,不再是每次都沿着8个方向顺序搜索,而是采用贪心算法选择当前情况下的最优的方向。此处最优的点,在本题中看作后续结点最少的点。进行两次循环,对可行的方向进行累计计算,选取累计结果最小的作为最优点。基于贪心算法可以快速得到搜索结果,效率上有一定的提高。

        第三种:与第二种一个是递归处理,另一个是非递归处理。非递归处理,为了满足这种需求,需要定义一个栈结构,当走到某个位置无法进行下一步时,就将原来栈顶的元素出栈,转而换一条路径继续探索,如果还是无法找到正确的路径,那么就再次出栈,以此类推。如果栈空还未结束,说明没有路径,否则即成功找到路径。

        在求解出马踏棋盘问题后,为使代码更具有普遍性,将棋盘的长宽设置为用户输入,以便于解决其他格式下的问题。为了对这三种方法有更客观的比较,本设计中还设置了对求解时间的显示。

    四、完整代码

    #include <iostream>
    #include <windows.h>
    #include<stdio.h>
    #include<stdlib.h>
    #pragma comment(lib,"winmm.lib")
    using namespace std;
    #define ROW 8
    #define COL 8
    #define MAX_STEPS ROW*COL
    int move_x[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; 
    int move_y[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    //深度优先遍历(递归)
    void Dfs( int path[8][8], int m, int n, int edge, int count)
    {
        if (count >= edge*edge) 
            return;
        if (m <= edge-1 && n <= edge-1 && m >= 0 && n >= 0 && path[m][n] == 0)
    	{
    		count++; 
    		path[m][n] = count; 
    		for (int i = 0;i < edge;i++)
    			Dfs(path, m + move_x[i], n + move_y[i], edge, count); 
    		return;
    	}
    	else
    		return;
    }
    //深度优先遍历+贪心算法(递归)
    void Dfs_tx(int flag[8][8], int path[8][8], int m, int n, int edge, int count, int found)
    {
        if(found)
            return;
        if(count >= edge*edge)
        {
            found += 1; 
            for(int i = 0; i < edge; i++)
            {
                for(int j = 0; j < edge; j++)
                    path[i][j] = flag[i][j];
            }
            return;
        }
        if(m > edge-1 || n > edge-1 || m < 0 || n < 0 || flag[m][n] != 0) 
            return; 
        count++; 
        flag[m][n] = count; 
        int count_next[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
        for (int i = 0; i < edge; i++)
        {
            int m_next = m + move_x[i];
            int n_next = n + move_y[i];     
            if (m_next < edge && n_next < edge && m_next >= 0 && n_next >= 0 && flag[m_next][n_next] == 0)
            {
                count_next[i] ++;
                for (int j = 0; j < edge; j++)
                {
                    int m_next_next = m_next + move_x[j];
                    int n_next_next = n_next + move_y[j];
                    if (m_next_next < edge && n_next_next < edge && m_next_next >= 0 && n_next_next >= 0 && flag[m_next_next][n_next_next] == 0)                
                            count_next[i]++;
                }
            }       
        }
        int opt_direct = 0;
        for (int i = 0; i < edge; i++)
        {
            if (count_next[opt_direct] == -1)
                opt_direct = i;
            if ((count_next[i] < count_next[opt_direct]) && count_next[i] != -1)
            {
                opt_direct = i;
            }
        }
        Dfs_tx( flag, path, m + move_x[opt_direct], n + move_y[opt_direct], edge, count, found); 
        flag[m][n] = 0;                
    }
    //深度优先遍历+贪心算法(非递归)
    typedef struct stack
    {
        int x_adr;      
        int y_adr;    
        int direction;
    }HORSE_CHESS_STACK;
    int chess[ROW+1][COL+1];
    int dir[8][2] = {{2,-1},{-2,-1},{-2,1},{2,1},{1,-2},{-1,-2},{-1,2},{1,2}};
    int top;
    HORSE_CHESS_STACK Adr_Stack[MAX_STEPS];
    int out_stack;
    void init()
    {
        int n = MAX_STEPS;
        while(n--)
    	{
            Adr_Stack[n].x_adr = 0;
            Adr_Stack[n].y_adr = 0;
            Adr_Stack[n].direction = -1;
        }
        Adr_Stack[0].x_adr = 0;
        Adr_Stack[0].y_adr = 0;
        Adr_Stack[0].direction = -1;
        
        for(int i = 1;i <= ROW;i++)
    	{
            for(int j = 1;j <= COL;j++)
    		{
                chess[ROW][COL] = 0;
            }
        }  
        top = -1;
        out_stack = 0;
    }
    void print_stack()
    {
        cout<<"栈中情况:\n";
        for(int i = 0;i < MAX_STEPS;i++)
    	{
    		printf("x:%d  y:%d direction = %d\n",Adr_Stack[i].y_adr,Adr_Stack[i].x_adr,Adr_Stack[i].direction);
        }
        cout<<"\n\n";
    }
    void push_stack(int x_real,int y_real)
    {
        top++;
        Adr_Stack[top].x_adr = x_real;
        Adr_Stack[top].y_adr = y_real;
        Adr_Stack[top].direction = -1; 
    }
    void pop_stack()
    {
        Adr_Stack[top].x_adr = 0;
        Adr_Stack[top].y_adr = 0;
        Adr_Stack[top].direction = -1; 
        top--;
    }
    void mark_chess(int x,int y)
    {
        chess[y][x] = top + 1;
    }
    void print_chess_board()
    {
        cout<<"\t\t\troute:"<<endl;
        for(int i = 1;i <= ROW;i++)
    	{
    		cout<<"\t\t\t";
            for(int j = 1;j <= ROW;j++)
    		{
                printf("%4d ",chess[i][j]);
            }
            cout<<endl;
        }
        cout<<endl;
    }
    int t = 1;
    void print_steps()
    {
        printf("(%d,%d)",Adr_Stack[top].y_adr,Adr_Stack[top].x_adr);
        t++;
        if(t == ROW)
    	{
            cout<<endl;
            t = 0;
        }
    }
    void run_horse_tanxin()
    {
        int x_now,y_now;
        while(1)
    	{
            if(top >= MAX_STEPS - 1)
    		{
                print_chess_board();
                break;
            }
            x_now = Adr_Stack[top].x_adr;
            y_now = Adr_Stack[top].y_adr;
            int next[ROW] = {};
            for(int i = 0;i < ROW;i++)
    		{
                int x_next = x_now + dir[i][0];
                int y_next = y_now + dir[i][1];
                if((x_next > 0 && x_next <= COL) && (y_next > 0 && y_next <= ROW) && chess[y_next][x_next] == 0 )
    			{
                    for(int j = 0;j < ROW;j++)
    				{
                        int x_next_next = x_next + dir[j][0];
                        int y_next_next = y_next + dir[j][1];
                        if((x_next_next > 0 && x_next_next <= COL) && (y_next_next > 0 && y_next_next <= ROW) && chess[y_next_next][x_next_next] == 0)
    					{
                            next[i]++;
                        }
                    }
                }
            }
            int real_next[8] = {0};
            int k = 0;
            int t = ROW + 1;
            for(int i = 0;i < ROW;i++)
    		{
                t = ROW + 1;
                for(int j = 0;j < 8;j++)
    			{
                    if(next[j] < t)
    				{
                        real_next[i] = j;
                        t = next[j];
                        k = j;
                    }
                }
                next[k] = ROW + 1;
            }
            int dir_now = 0;
            for(dir_now = Adr_Stack[top].direction + 1;dir_now < ROW;dir_now++)
    		{
                int x_real = x_now + dir[real_next[dir_now]][0];
                int y_real = y_now + dir[real_next[dir_now]][1];
                Adr_Stack[top].direction += 1;
                if((x_real <= COL && x_real > 0) && (y_real <= ROW && y_real > 0) && chess[y_real][x_real] == 0)
    			{
                    push_stack(x_real,y_real);
                    mark_chess(x_real,y_real);
                    break;
                }
            }
            if(Adr_Stack[top].direction >= 7)
    		{
    			cout<<endl;
    			 printf("\n out:(%d,%d) \n",Adr_Stack[top].y_adr,Adr_Stack[top].x_adr);
                chess[Adr_Stack[top].y_adr][Adr_Stack[top].x_adr] = 0;
                out_stack++;
                pop_stack();
            }
            //print_stack(); 
            print_steps();
        }
    }
    void Dfs_tx_zhan(int m,int n)
    {
        init();
        push_stack(m,n);
        mark_chess(m,n);
        cout<<"\t\t\troute address:\n";
        printf("(%d,%d)",m,n);
        run_horse_tanxin();
    }
    void menu()
    {
    	system("cls");
    	cout<<"\t\t\t马踏棋盘问题的解决:"<<endl;
    	cout<<"\t\t\t1.深度优先遍历(递归)"<<endl;
    	cout<<"\t\t\t2.深度优先遍历+贪心算法结合(递归)"<<endl;
    	cout<<"\t\t\t3.深度优先遍历+贪心算法结合(非递归)"<<endl;
    	cout<<"\t\t\t0.退出"<<endl;
    	cout<<"\t\t\t请输入选择:";
    	int sel;
    	cin>>sel;
    	if (sel == 0)
    		exit(0);
    	while(sel >3 ||sel <0)
    	{
    		cout <<"\t\t\t输入格式错误,请重新输入:";
    		cin>>sel;
    	}
        int m,n;
        int found = 0;
    	int edge;
    	cout<<"\t\t\t请输入棋盘的边长:";
        cin >> edge;
    	cout<<"\t\t\t请输入初始时马的位置:";
    	cin>>m >> n;
    	int flag[8][8]={0};
    	int path[8][8]={0};
    	DWORD start = timeGetTime();
    	if (sel == 1)
    	{
    		cout <<"\t\t\t下面是采用深度优先遍历(递归)得出的结果:"<<endl;
    		Dfs( path, m, n, edge, 0);
    	}
    	else if (sel == 2)
    	{
    		cout <<"\t\t\t下面是采用深度优先遍历+贪心算法结合(递归)得出的结果:"<<endl;
    		Dfs_tx( flag, path, m, n, edge, 0, found);
    	}
    	else if (sel == 3)
    	{
    		cout<<endl;
    		cout <<"\t\t\t下面是采用深度优先遍历+贪心算法结合(非递归)得出的结果:"<<endl;
    		Dfs_tx_zhan(m, n);
    	}
    	if (sel !=3)
    	{
    		for (int i = 0; i < edge; i++)
    		{
    			cout<<"\t\t\t";
    			for (int j = 0; j < edge; j++)
    				cout << path[i][j] << "\t";
    			cout << endl;
    		}
    	}
    	DWORD end = timeGetTime()-start;
    	cout<<"\t\t\t使用本方法所用时间为"<<end<<"ms"<<endl;
    	cout<<"\t\t\t按任意键返回菜单!"<<endl;
    	system("pause");
    	menu();
    }
    int main() 
    {
    	system("color E0");
    	menu();
        system("pause");
        return 0;
    }
    

    五、测试与运行

    1.菜单

    2.第一种方法求解

    3.第二种方法求解

    4.第三种方法求解

    展开全文
  • 马踏棋盘问题是旅行商(TSP)或哈密顿问题(HCP)的一个特例。在国际棋盘棋盘上,用一个马按照马步跳遍整个棋盘,要求每个格子都只跳到一次,最后回到出发点。这是一个 NP问题,通常采用回溯法或启发式搜索类算法...

    马踏棋盘问题是旅行商(TSP)或哈密顿问题(HCP)的一个特例。在国际棋盘棋盘上,用一个马按照马步跳遍整个棋盘,要求每个格子都只跳到一次,最后回到出发点。这是一个 NP问题,通常采用回溯法或启发式搜索类算法求解。 

    在此采用栈进行回溯法求解

    #include <iostream>
    #include<stdlib.h>
    #include <stdio.h>
    #include <iomanip>
    using namespace std;
    const int StackInitSize=10;
    const int StackInc=1;
    typedef struct {
        int x;
        int y;
    } Position;
    typedef struct
    {
        int n=5;//迷宫规模n*n
        int Board[10][10]={{0}};//棋盘最大规模
        Position start;//马开始位置
    }ChessBoard;
    typedef struct {
        int ord;
        //顺序(第几步)
        Position seat;
        //位置
        int di;
        //查找方向
    } SElemType;//马的当前状态
    struct SStack
    {
        SElemType * base,*top;
        int stacksize;
    };
    bool StackInit(SStack &S)
    {
        S.base=new SElemType[StackInitSize];
        if(!S.base)
            return false;
        S.top=S.base;
        S.stacksize=StackInitSize;
        return true;
    }
    bool Push(SStack &S,SElemType e)
    {
        SElemType *base;
        if(S.top-S.base==S.stacksize)
        {
            base=(SElemType*)realloc(S.base,(S.stacksize+StackInc)*sizeof(SElemType));
            if(!base)
                return false;
            S.base=base;
            S.top=S.base+S.stacksize;
            S.stacksize+=StackInc;
        }
         *S.top=e;
         S.top++;
         return true;
    }
    bool Pop(SStack &S,SElemType &e)
    {
        if(S.top==S.base)
            return false;
        S.top--;
        e=*S.top;
        return true;
    }
    void HorseOnBoard(int n,int x,int y)
    {
        ChessBoard CBoard;
        CBoard.start.x=x;
        CBoard.start.y=y;
        CBoard.n=n;
        int h_move[8][2]={{2,1},{-1,2},{1,2},{-2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
        int step=0;
        int i=0;
        SStack S;
        StackInit(S);
        Position p=CBoard.start;
        SElemType horse;
        horse.di=0;
        horse.ord=step;
        horse.seat=CBoard.start;
        Push(S,horse);
    do{
           bool f=Pop(S,horse);
           if(!f)
               break;
           if (step>=1)
            {
                i=horse.di+1;
                CBoard.Board[horse.seat.x][horse.seat.y]=0;
                step--;
    
            }
            for(i;i<8;i++)
            {
                p.x=horse.seat.x+h_move[i][0];
                p.y=horse.seat.y+h_move[i][1];
                if(CBoard.Board[p.x][p.y]==0&&(p.x<=CBoard.n-1)&&(p.x>=0)&&(p.y<=CBoard.n-1)&&(p.y>=0))
                {
                    step++;
                    horse.di=i;
                    horse.ord=step;
                    Push(S,horse);
                    CBoard.Board[horse.seat.x][horse.seat.y]=step;
                    horse.seat=p;
                    i=0;
    
                    if(step==CBoard.n*CBoard.n-1)
                    {
                        step++;
                        CBoard.Board[horse.seat.x][horse.seat.y]=step;
                        Push(S,horse);
                    }
                    continue;
                }
    
            }
    
        }while(step<CBoard.n*CBoard.n-1);
    
        if(step<CBoard.n*CBoard.n)
           cout<<"找不到合适的路径"<<endl;
        else
        {
              cout<<"马在"<<n<<"*"<<n<<"的棋盘上的足迹如下:"<<endl;
              for (int a = 0; a < n; a++) {
                for(int b = 0; b < n; b++) {
                    cout<<setw(2)<<CBoard.Board[a][b]<<setw(2)<<' ';
                    }
                cout<<' '<<endl;
        }
        }
    
    }
    int main()
    {
        HorseOnBoard(5,0,0);
        return 0;
    }
    

     

    展开全文
  • 马踏棋盘C语言贪心算法 将马随机放在国际象棋的8×8棋盘Board[0~7][0~7]的某个方格中,马按走棋规则(马走日字)进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格
  • 马踏棋盘C++源代码

    2010-06-01 23:40:19
    马踏棋盘C++源代码,执行效率较高,所采取的算法应该也是比较常见的算法。
  • 马踏棋盘 c++程序

    2008-07-16 22:01:00
    马踏棋盘c++ 程序源码,玩玩还可以吧
  • 他与求一个解不同之处在于,当我们求到一个解之后,这个程序却会告诉计算机:“啊!这不是我们想要的解,我们继续吧。”于是,傻傻的计算机就信了我们的话,跳过这个这个解,继续求下一个。当他走完所有可能之后,他...
  • 马踏棋盘代码C++

    2015-05-10 18:31:03
    马踏棋盘代码C++ void main() { int i,a,b; for(i=0;i*n;i++) { visited[i]=0; } CreatAdLlist( ga ); setnull(&q); print_original(); printf("please input importpoint<1<=x<=8 and 1<=y<=8>"); Printf("x=...
  • 马踏棋盘 数据结构

    2016-06-26 15:35:14
    这里有你想要的资源,马踏棋盘,完整代码!
  • C++贪心算法实现马踏棋盘问题

    千次阅读 2016-12-18 14:17:20
    C++马踏棋盘的贪心算法

    C++马踏棋盘的贪心算法

    转载请注明:
    http://blog.csdn.net/l773575310/article/details/53727286

    第一次看马踏棋问题时没有想到用贪心算法,结果穷举起来光5*5的棋盘也运行了很久才出来一条路径。然后看了不少关于马踏棋的解法,大体也看懂了,简单的的说,就是让棋子每次走的下一个位置的出口尽可能少

    贪心算法在这里体现:
    尽可能走出口少的路,因为如果走出口多的路,后面出口少的路越多,越容易走到死路,即没有路可走。

    看下图:
    假设小马哥在图中的位置,且其他位置都还没有走过,他有6个红色位置可以走
    这里写图片描述

    如果他走右下角,那他只有一个出口(绿色的)
    这里写图片描述

    如果走左下角那个,那他有3个出口
    这里写图片描述

    以此类推:走偏左下角,5个
    这里写图片描述

    最后看一下小马哥下一个位置的出口数量:
    这里写图片描述

    如果为0说明走到死路,有可能是走完了所有格子,也有可能没有走完,那就需要往回走了(类似弹栈)。


    下面就是代码了

    首先是一些初始化

    //宏定义,宽、高、一共的格子数
    #define WIDTH 8
    #define HEIGHT 8
    #define PLACE_COUNT ((WIDTH)*(HEIGHT)) 
    
    //放置棋子的位置
    typedef struct position {
        int x;
        int y;
    }Position;
    
    //马棋可以走的8个方向(相对当前位置)
    vector<Position> DIR({ { -1,-2 },{ 1,-2 },{ 2,-1 },{ 2,1 },{ 1,2 },{ -1,2 },{ -2,1 },{ -2,-1 } });
    
    //这个用来排序下一个位置用到,具体看下面的函数
    typedef pair<int, int> PAIR;
    

    然后在 main函数中

    int main()
    {
        //棋盘所有格子初始化都没走过,为false
        vector<bool> place(PLACE_COUNT, false);
        //顺序存放棋子所经过的所有位置
        vector<Position> pos;
    
        //这里假设从(0,2)开始,这个函数下面讲
        if (emplaceHorse(0, 2, 0, place, pos))
            for (int i = 0; i < PLACE_COUNT; i++)
                cout << i + 1 << ":(" << pos[i].x + 1 << "," << pos[i].y + 1 << ") ";
        else
            cout << "what the fuck!?";
    
        return 0;
    }

    这里解释一下两个vector:

    pos,按顺序存了小马哥走过的位置,其实充当栈来用。

    place ,存了棋盘的每一个位置,第一行第一列就是place[0],第二行第一列就是place[8],最后一行最后一列就是place[63],他的值类型bool,true代表这个位置已经走过,false代表没走过。
    place存储样例

    接下来就是递归了
    参数:小马哥的x,y坐标,走的第几步count,还有上面说的两个vector

    bool emplaceHorse(int x, int y, int count, vector<bool> & place, vector<Position> & pos)
    {
        //判断当前x,y是否在棋盘内,若在,是否此位置已经走过,因为||操作符有短路作用,所以不用怕后面place越界。
        if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT || place[x + y*WIDTH])
            return false;
    
        count++;
        place[x + y*WIDTH] = true;          //标志此位置已走过
        pos.push_back({ x,y });             //将此位置压入已走路径pos
    
        //判断是否已经走满格子的数量
        if (count == PLACE_COUNT)
            return true;
    
        vector<PAIR> vecMap = findPosition(x, y, place);
        //遍历这个已经出口数量从小到大排好序的位置
        for (int i = 0; i < vecMap.size(); i++)
            //将当前选中的位置作为下一个位置,继续递归
            if (emplaceHorse(vecMap[i].first % WIDTH, vecMap[i].first / WIDTH, count, place, pos))
                return true;
    
        //当前路径不适合,标志未走过,弹出路径队列pos
        place[x + y*WIDTH] = false;
        pos.pop_back();
        return false;
    }

    vecMap[i].first % WIDTH 就是位置的x,
    vecMap[i].first / WIDTH 就是位置的y.

    下面就是贪心的核心了,找出口少的路径

    vector<PAIR> findPosition(int x, int y, vector<bool> & currentPos)
    {
        //key为位置,value为此位置的出口数量
        map<int, int> p;
        //第一层循环,当前位置可选的下一个位置,就是上面那些图片的红色的位置
        for (int i = 0; i < DIR.size(); i++)
        {
            int temX = DIR[i].x + x;
            int temY = DIR[i].y + y;
            if (temX < 0 || temX >= WIDTH || temY < 0 || temY >= HEIGHT || currentPos[temX + temY * WIDTH])
                continue;
            int count = 0;
            //第二层循环,计算可选的下一个位置的出口数量,上面那些图片绿色的位置
            for (int j = 0; j < DIR.size(); j++)
            {
                int outX = DIR[j].x + temX;
                int outY = DIR[j].y + temY;
                if (outX < 0 || outX >= WIDTH || outY < 0 || outY >= HEIGHT || currentPos[outX + outY * WIDTH])
                    continue;
                count++;
            }
            //记录这个位置,还有他的出口数量
            p[temX + temY * WIDTH] = count;
        }
    
        //将所有可选位置的出口数量从小到大排序,即按value排序
        vector<PAIR> vecP(p.begin(), p.end());
        sort(vecP.begin(), vecP.end(), [](const PAIR& p1, const PAIR& p2) { return p1.second < p2.second; });
    
        //返回排好序的vector
        return vecP;
    }

    运行结果如下:
    8*8的棋盘,从(0,2)开始走一条不重复的路,遍历完整个棋盘。
    result

    自己画了一下图,可以发现小马哥基本上沿着边走的,因为边路出口少。
    result

    源码下载:
    C++贪心算法实现马踏棋盘问题(.cpp文件)

    展开全文
  • 设计问题:有一个 8*8 的方格棋盘(如下图所示),现有一匹马从任意一个位置(方格)出发, 给出一种方案使马走遍棋盘中的每一个方格,且每个方格只走过一次(马走日字)。 程序的输入:输入马的初始位置(相应的...
  • 马踏棋盘(源码).zip

    2019-07-23 21:10:44
    本文档为马踏棋盘课设的源码,包含5个源代码文件。在VS2017平台用C++语言编写,代码里面包含了基于贪心法、回溯法、递归法等解决马踏棋盘(骑士周游问题),每一行代码有详细的注释及解释。
  • 马踏棋盘C++代码

    千次阅读 2010-04-27 19:47:00
    闲来无事,写了一下马踏棋盘的算法,高手莫笑,有问题多指教。 马踏棋盘:在8×8方格的棋盘上,从任意指定方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。 #include #include #include using ...
  • c++马踏棋盘贪心算法

    2016-12-18 17:08:03
    c++解决马踏棋盘问题
  • c++编写的马踏棋盘

    2009-06-17 15:51:04
    该程序由VC6.0所编写,VS2005及VS2008下都能运行,主要是马踏棋盘游戏
  • 马踏棋盘C++实现与贪婪算法优化

    千次阅读 2017-02-27 19:48:55
    马踏棋盘问题即在一个8*8的棋盘上,
  • 步骤2:确定马从当前点出发,可跳跃的附近8个点,以结构体Jump数组给出,但需判断当前给出的附近8个点是否曾经访问过,或者是否这8个点超出棋盘尺寸。 步骤3:跟据步骤2确定跳跃的点,分别计算可跳跃点的下下一步,...
  • 从某点出发不重复地遍历完成整个棋盘输出遍历点的先后: 就以9*10的象棋棋盘为例: #include<stdio.h> #include<string.h> #include<stdlib.h> #define row 9 #define col 10 bool chess...
  • 马踏棋盘非递归

    2012-03-20 21:36:00
    利用贪心策略进行优化,基本在15ms即可出结果,采用的是非递归算法
  • 数据结构与算法 c++实现 马踏棋盘问题 适合大二初学数据结构与算法 程序有详细备注,可直接运行 栈问题
  • c++以数据结构的思想做的马踏棋盘,且用贪心算法优化过
  • 马踏棋盘问题

    2015-03-30 12:46:20
    马踏棋盘加剪枝 的算法,方格数为8*8 , 具体复杂度多少不太清楚
  • C程序-马踏棋盘

    2021-04-15 08:48:42
    马踏棋盘原理就是,在一个8*8方格中,定义一个起点根据马走日的原理,将方格中所有位置都走一遍,但不走重复的位置。 栈、结构体法 #include <stdlib.h> #include <stdio.h> #define ROW 8 #define COL ...
  • 设计一个国际象棋的马踏遍棋盘的演示程序。 【基本要求】 将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。编制非递归程序,求...
  • VC++实现,生成可视化演示程序 棋盘式的,点一下所有步骤1234.。
  • 马踏棋盘问题C++解决

    2008-10-08 11:39:14
    8*8棋盘递归求解 可求得从任意点出发的任意路径和所有路径
  • 马踏棋盘 栈 链表 按照老师的要求的。大家来下载吧· 但是计算算法比较冗余,计算不较慢。 #include #include "conio.h" using namespace std; #define edgetype int #define vextype int #define MAX 8 typedef ...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 217
精华内容 86
关键字:

马踏棋盘c++