c/c++语言开发共享C/C++实现马踏棋盘算法

#include<stdio.h>        //定义棋盘的行数和列数  #define chess_board_line_num 10  #define chess_board_colum_num 10     //定义棋盘上位置的结构体  typedef struct   {      int nposx;      int nposy;  }spos;     //使用一个二维数组来表示棋盘  int g_arrchessboard[chess_board_line_num][chess_board_colum_num];     //用来表示horse跳到下一位置为第几跳，起跳位置为第0跳  int g_horsesteps = 0;     //定义horse的起跳位置，可以输入；若输入非法则使用默认起跳位置(0,0)  spos g_startpos={0,0};     //检查位置有效性, 若位置在棋盘内则返回1，不在棋盘则返回0  int checkpos(spos tpos)  {      //x/y坐标不在棋盘内则位置不在棋盘内      return !(0 > tpos.nposx || tpos.nposx +1 > chess_board_line_num || 0 > tpos.nposy || tpos.nposy + 1 > chess_board_colum_num);  }     //检查位置是否已经跳过，若跳过则位置上记录经过该位置时为第几跳，若未被跳过则值为棋盘初始值-1  int checkused(spos tpos)  {      return g_arrchessboard[tpos.nposx][tpos.nposy] != -1;  }     //根据偏移量获取位置有效性  void getnextsteplistbyoffset(spos curpos, spos nextsteplist[8], int* numofvalidstep, int offsetx, int offsety)  {      //定义horse的可跳方向      //分别为右上（1,1）、右下（1，-1）、左上（-1，1）、左下（-1，-1）      //原始坐标+方向位移得到新的跳点      static spos directionlist[4] = {{1,1},{1,-1},{-1,1},{-1,-1}};      spos tpos; //存储可能的跳点，该跳点不一定有效      int i = 0;         for (; i < 4; i++)      {          tpos.nposx = curpos.nposx + offsetx*directionlist[i].nposx;          tpos.nposy = curpos.nposy + offsety*directionlist[i].nposy;             //若跳点在棋盘内，且跳点未被跳过则可以作为下一跳点          if (checkpos(tpos) && !checkused(tpos))          {              nextsteplist[(*numofvalidstep)++] = tpos;          }      }  }     //获取下一跳位置列表, 下一跳位置列表最多存在8个，所以固定传入数组8  //只返回有效的位置列表， numofvalidstep中存储有效位置列表个数  void getnextsteplist(spos curpos, spos nextsteplist[8], int* numofvalidstep)  {      //x坐标移动2格，y坐标移动1格检查      getnextsteplistbyoffset(curpos, nextsteplist, numofvalidstep, 2, 1);                //x坐标移动1格，y坐标移动2格检查      getnextsteplistbyoffset(curpos, nextsteplist, numofvalidstep, 1, 2);      }     //冒泡排序  void sortbynextstepnum(spos nextsteplist[8], int* numofvalidstep, int nsubvalidstep[8])  {      int tmpn;      spos tmppos;      int i = 0;      int j = 0;      int maxstepnum = *numofvalidstep;      for (; i < maxstepnum; i++)      {          for (j = 1; j < maxstepnum - i; j++)          {              if (nsubvalidstep[j] < nsubvalidstep[j-1])              {                  //进行位置互换，进行冒泡                  tmpn = nsubvalidstep[j];                  nsubvalidstep[j] = nsubvalidstep[j-1];                  nsubvalidstep[j-1] = tmpn;                                    //进行对应的pos互换                  tmppos = nextsteplist[j];                  nextsteplist[j] = nextsteplist[j-1];                  nextsteplist[j-1] = tmppos;              }          }      }  }     //使用贪心算法获取下一位置列表，即对返回的有效列表根据出口进行升序排列  void getnextgreedlist(spos curpos, spos nextsteplist[8], int* numofvalidstep)  {      spos subnextsteplist[8]; //用于缓存下一跳点列表的中每个跳点的下一跳点列表      int  nsubvalidstep[8] = {0,0,0,0,0,0,0,0};  //用于存储下一跳点列表中每个跳点的下一跳点个数          int  i = 0;          //先获取所有的可跳节点      getnextsteplist(curpos, nextsteplist, numofvalidstep);            //获取子跳点的下一跳点个数      for(; i< *numofvalidstep; i++)      {          getnextsteplist(nextsteplist[i], subnextsteplist, &nsubvalidstep[i]);      }            //使用冒泡排序      sortbynextstepnum(nextsteplist, numofvalidstep, nsubvalidstep);  }        //以输入pos为起点进行马踏棋盘  //返回0  表示找到正确跳跃路径  //返回-1 表示已经完成所有跳点的尝试，不存在可行方案  //返回1  表示选中的下一跳并非可行路径，需要重新选择一个跳点进行尝试  int horseroaming(spos curpos)  {      spos nextsteplist[8];   //记录curpos的下一跳点列表，最多存在8个可能跳点，使用数组表示      int  numofvalidstep = 0;//记录下一跳列表中的跳点个数      int  i = 0;      int  nret = 1;            //添加跳点的trace记录，并刷新跳点的计数      g_arrchessboard[curpos.nposx][curpos.nposy] = g_horsesteps++;            //若已经经过棋盘上所有节点则表示找到马踏棋盘路径，退出      if (g_horsesteps == chess_board_line_num*chess_board_colum_num)      {          return 0;      }                  //使用普通dfs进行路径查找      //getnextsteplist(curpos, nextsteplist, &numofvalidstep);            //使用贪心算法获取有效列表      getnextgreedlist(curpos, nextsteplist, &numofvalidstep);            for (; i < numofvalidstep; i++)      {          //进行递归求解          nret = horseroaming(nextsteplist[i]);          if (1 != nret)          {              //求解结束              return nret;          }              }            //若回到起点位置，且起点的所有可能跳点均已尝试过，则说明未找到遍历棋盘方案      if (curpos.nposx == g_startpos.nposy && curpos.nposy == g_startpos.nposy)      {          return -1;      }            //回溯：回退棋盘上的trace记录，并返回上层      g_arrchessboard[curpos.nposx][curpos.nposy] = -1;      g_horsesteps--;      return 1;  }     //初始化棋盘上所有位置的值为-1  void initboard()  {      int i,j; //设置循环控制变量      for (i = 0; i< chess_board_line_num; i++)      {              for (j = 0; j< chess_board_colum_num; j++)          {              g_arrchessboard[i][j] = -1;          }      }  }     //将棋盘上记录的跳跃trace打印到文件中  void  printsteps()  {      int i,j;          file* pfile = fopen("output.txt","wb+");            for (i = 0; i< chess_board_line_num; i++)      {          for (j = 0; j< chess_board_colum_num; j++)          {              fprintf(pfile,"%2d ", g_arrchessboard[i][j]);          }          fprintf(pfile,"rn");      }            fclose(pfile);  }     int main()  {      //进行棋盘上跳跃trace初始化      initboard();      if (horseroaming(g_startpos) == 0)      {          //打印结果          printsteps();      }      else      {          //未找到解          printf("not found result n");      }      return 0;  }