首页  >  文章  >  后端开发  >  PHP实现国际象棋之跳马程序的示例代码

PHP实现国际象棋之跳马程序的示例代码

黄舟
黄舟原创
2017-03-10 09:12:542089浏览

PHP实现国际象棋之跳马程序的示例代码

问题描述:

     假设国际象棋棋盘有5*5共25个格子。设计一个程序,使棋子从初始位置(棋盘格编号为1的位置)开始跳马,能够把棋盘的格子全部走一遍,每个格子只允许走一次。要求:

1) 输出一个解(用二维数组来记录马跳的过程,即[步号,棋盘格编号],左上角为第一步起点),2)求总共有多少解

                                                                                                     棋盘格编号为:

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

分析:简单的DFS。。。

#include <stdio.h> #include <string.h> 

int path[26],path1[26],res;
int vis[26][26];
int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={-1,-2,2,-1,1,2,2,1};
void DFS(int x,int y,int num,int step){    if(x<1 || x>5 || y<1 || y>5 || vis[x][y]) //越界或已访问 
        return;    
    if(step==25){
        res++;
        path1[step]=num;        for(int i=1;i<=25;i++)
            path[i]=path1[i];        return;
    }    
    if(!vis[x][y]){
        vis[x][y]=1;        for(int i=0;i<8;i++){
            path1[step]=num;
            DFS(x+dx[i],y+dy[i],(x+dx[i]-1)*5+y+dy[i],step+1);
        }
        vis[x][y]=0;
    }
}int main(){
    memset(vis,0,sizeof(vis)); //此处可以省略,因为定义全局变量时会被系统赋值为0
    DFS(1,1,1,1);
    printf("解的总个数:%d,其中一个解:\n",res);    for(int i=1;i<=25;i++)    
        printf("[%d,%d]\n",i,path[i]);    return 0; 
}

 

以上是PHP实现国际象棋之跳马程序的示例代码的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn