HDU 1584 Spider Solitaire (DFS)

Hdu 1584 Spider Solitaire



Tidsbegrensning: 10000/5000 MS (Java / Andre) Minne Grense: 32768/32768 K (Java / Andre)
Total innsending (er): 4818 akseptert innlevering (er): 2052


problem beskrivelseEdderkoppkortet er et kortspill som følger med Windows XP-operativsystemet. Spillereglene er som følger: du kan bare dra kortet til kortet som er ett høyere enn henne (den minste A, den største K), hvis det er en knapp på det dratt kortet Når kortene er ordnet i rekkefølge , så beveger disse kortene seg sammen. Hensikten med spillet er å ordne alle kortene i samme farge fra liten til stor. For enkelhets skyld har spillet vårt bare 10 kort av samme farge, fra A til 10, og utvides tilfeldig på en linje, nummerering fra 1 til 10. Flytt kortet på det første kortet til det tredje kortet , bevegelsesavstanden er abs (ij), nå må du finne fullføringen av spillet Minimum bevegelsesavstand.

InngangDe første inngangsdataene er T, som representerer antall datagrupper.
Hver datagruppe har en rad, 10 inngangsdata, dataområdet er [1,10], som representerer henholdsvis A til 10, vi garanterer at hver datagruppe er lovlig.
ProduksjonTilsvarende hver gruppe datautgang minimum bevegelsesavstand.
Eksempelinngang #include #include #include #define Max 999999 #include using namespace std int visit[20] int map[20] int ans void dfs(int cnt,int sum) { if(sum>ans) { return } if(cnt==9) { ans=sum } int i,j for(i=1i<10i++) { if(visit[i]==0) { visit[i]=1 for(j=i+1j<=10j++) { if(visit[j]==0) { dfs(cnt+1,sum+abs(map[i]-map[j])) break } } visit[i]=0 } } } int main(int argc, char *argv[]) { int t scanf('%d',&t) while(t--) { int a,i for(i=1i<=10i++) { scanf('%d',&a) map[a]=i } ans=999999 memset(visit,0,sizeof(visit)) dfs(0,0) printf('%d ',ans) } return 0 } 1 1 2 3 4 5 6 7 8 9 10
Eksempel på utdata
 9 
Det er tilstrekkelig å krysse alle situasjonene, og det må reduseres, det vil si at antall trinn i den nåværende situasjonen er større enn minimum antall trinn som er fullført før, da er den nåværende gjennomgangen meningsløs og kan hoppes over Lagringen av dette spørsmålet trenger også oppmerksomhet, fordi det er nødvendig å lagre hans posisjon og registrere verdien, slik at abonnementet til matrisen brukes som hans verdi, og verdien av matrisen kan brukes som hans posisjon.