Liny_@NotePad

沉迷ACG中

回溯法解决马步遍历问题

YOYO posted @ 2009年5月27日 01:44 in 【算法】与【数据结构】 with tags 回溯法 马步遍历 , 6897 阅读

设计一算法，求解国际象棋中的马的周游问题：给定一8×8的棋盘，马从棋盘的某个位置出发，经过棋盘中的每一个方格恰好一次。（只需求一可行解）

一、 算法思想描述

指定一个起点坐标，从起点开始对每个点遍历其能到达的八方向上的点，如果可以踩则走到该结点上，并继续深入遍历，直到最后走完所有的结点。

二、 完整的程序以及说明 

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. //      棋盘大小
  5. #define N 8
  6.  
  7. // 八方向
  8. #define DIR 8
  9. int dir[DIR][2] = { {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1} };
  10.  
  11. int mz[N][N];
  12. bool flag;
  13. int sx, sy;
  14.  
  15. /**
  16. * 遍历算法
  17. * 输入： 起点坐标
  18. */
  19. void chess(int x, int y, int t){
  20.         //      标记这格走完了
  21.         mz[x][y] = t;
  22.  
  23.         //      走完N*N格
  24.         if(t==N*N){
  25.                 //      标记找到了路径
  26.                 flag = true;
  27.  
  28.                 for(int i=0; i<N; i++){
  29.                         for(int j=0; j<N; j++){
  30.                                 printf("%5d", mz[i][j]);
  31.                         }
  32.                         putchar('\n');
  33.                 }
  34.                
  35.                 return;  
  36.  
  37.         }
  38.  
  39.         //      八方向可以走到的格子
  40.         for(int i=0; i<DIR&&!flag; i++){
  41.                 int tx = x+dir[i][0];
  42.                 int ty = y+dir[i][1];
  43.  
  44.                 //      如果存在该格并且没走过
  45.                 if(tx>=0&&tx<N&&ty>=0&&ty<N&&!mz[tx][ty]){
  46.                         //      走进去
  47.                         chess(tx,ty,t+1);
  48.                 }
  49.         }
  50.  
  51.         //      还原状态
  52.         mz[x][y] = 0;
  53. }
  54.  
  55.  
  56. int main(){
  57.         int x,y;
  58.        
  59.         memset(mz,0,sizeof(mz));
  60.  
  61.         cout<<"请输入起点坐标（从(1,1)至("<<N<<","<<N<<")）：";
  62.         cin>>x>>y;
  63.  
  64.         x--, y--;
  65.  
  66.         sx = x, sy = y;
  67.  
  68.         //      寻路标记置为false
  69.         flag = false;
  70.  
  71.         //      从(x,y)开始寻路
  72.         chess(x,y,1);
  73.  
  74.         if(!flag)puts("找不到可行路径！");
  75.  
  76.         return 0;
  77. }


 

Small_feed 评论 (1)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter