PHP-Beispielcode zur Implementierung des Schachtresorprogramms

Beispielcode für die PHP-Implementierung des Schachtresorprogramms:

Problembeschreibung:

Angenommen, das Schachbrett hat 5*5 und insgesamt 25 Gitter. Entwerfen Sie ein Programm, das die Schachfiguren dazu bringt, von der Anfangsposition (Position mit der Nummer 1 auf dem Schachbrett) zu springen und alle Gitter auf dem Schachbrett zu verschieben. Jedes Gitter darf nur einmal verschoben werden. Anforderungen:

1) Geben Sie eine Lösung aus (verwenden Sie ein zweidimensionales Array, um den Prozess des Pferdespringens aufzuzeichnen, d. h. [Schrittnummer, Schachbrettnummer], die obere linke Ecke ist der Startpunkt des ersten Schritts ), 2) Finden Sie die Gesamtzahl Lösung

Die Schachbrettzahl ist:

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

Analyse: Einfaches 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; 
}

Das obige ist der detaillierte Inhalt vonPHP-Beispielcode zur Implementierung des Schachtresorprogramms. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!