Home  >  Article  >  Backend Development  >  PHP sample code to implement chess vault program

PHP sample code to implement chess vault program

黄舟
黄舟Original
2017-03-10 09:12:542078browse

Sample code of PHP implementation of chess vaulting program:

Problem description:

Assume that the chess board has 5*5 and a total of 25 grids. Design a program that causes the chess pieces to start jumping from the initial position (position numbered 1 on the chessboard) and move all the grids on the chessboard. Each grid is only allowed to be moved once. Requirements:

1) Output a solution (use a two-dimensional array to record the process of horse jumping, that is [step number, checkerboard number], the upper left corner is the starting point of the first step), 2) Find the total number Solution

The checkerboard number is:

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
## Analysis: Simple 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; 
}

The above is the detailed content of PHP sample code to implement chess vault program. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn