HDU 1584 Spider Solitaire (DFS)

Hdu 1584 Spider Solitaire

Límite de tiempo: 10000/5000 MS (Java / otros) Límite de memoria: 32768/32768 K (Java / otros)
Envío (s) total (es): 4818 Envío (es) aceptado (s): 2052


Descripción del problemaLa tarjeta araña es un juego de cartas que viene con el sistema operativo Windows XP. Las reglas del juego son las siguientes: solo puedes arrastrar la carta a la carta que sea una más alta que ella (la A más pequeña, la K más grande), si hay un botón en la carta arrastrada Cuando las cartas están ordenadas , entonces estas cartas se mueven juntas. El propósito del juego es organizar todas las cartas del mismo palo, de pequeñas a grandes. En aras de la simplicidad, nuestro juego solo tiene 10 cartas del mismo palo, de la A a la 10, y se expanden aleatoriamente en una línea, numerando del 1 al 10. Mueve la carta de la i-ésima carta a la j-ésima carta , la distancia de movimiento es abs (ij), ahora lo que tienes que hacer es encontrar la finalización del juego La distancia de movimiento mínima.

AporteEl primer dato de entrada es T, que representa el número de grupos de datos.
Cada grupo de datos tiene una fila, 10 datos de entrada, el rango de datos es [1,10], representando A a 10 respectivamente, garantizamos que cada grupo de datos es legal.
ProducciónCorrespondiente a cada grupo de salida de datos de distancia mínima de movimiento.
Entrada de muestra #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
Salida de muestra
 9 
Es suficiente atravesar todas las situaciones, y debe reducirse, es decir, el número de pasos en la situación actual es mayor que el número mínimo de pasos completados antes, entonces el recorrido actual no tiene sentido y se puede omitir. El almacenamiento de esta pregunta también necesita atención, porque es necesario almacenar su posición y registrar su valor, por lo que el subíndice de la matriz se usa como su valor, y el valor de la matriz se puede usar como su posición. |_+_|