poj 3278

3278 Aceptado 1972K 16MS Pascal 1663B 2010-06-20 19:16:09

Código fuente: puedes intentar enviarlo una vez, es AC, no incómodo

Programa p3278;

var

q, paso.200001] de booleano

cabeza, cola, n, k, maxn, tmp: longint

<; p>begin

readln(n,k);

si ngt;=k entonces writeln(n-k)

else

start

fillchar(visita, tamaño de(visita), falso);

q[0]：=n; visita[n]：= paso[0]：=0;

cabeza:=0; cola:=0; maxn:=k*2;

while (headlt;=tail) hacer

comenzar

tmp:=q[head]*2;

si (tmplt; maxn) y (no visita[tmp]) entonces

comenzar

inc(cola); visita[tmp]:=true;

q[cola]:=tmp; paso[cola]:=paso[cabeza] 1;

if ( visitar[k]) luego romper;

end

tmp：=q[head]-1; no visitar[tmp]) entonces

comenzar

inc(tail); visitar[tmp]:=true;

q[tail]:=tmp; paso[cola]:=paso[cabeza] 1;

si (visita[k]) entonces rompe;

fin;

tmp:=q[ head] 1;

si (tmplt; maxn) y (no visita[tmp]) entonces

comienza

inc(tail); ：=true;

q[tail]：=tmp; paso[tail]：=paso[head] 1;

si (visita[k]) luego rompe; > fin;

inc(cabeza);

fin;

writeln(paso[cola]); p>

p>

end.

Método: el algoritmo principal es la búsqueda en amplitud.

Analicemos primero n y k. Cuando n es mayor o igual que k, solo puede retroceder o moverse sin moverse, es decir, generar los resultados directamente y luego usar la búsqueda amplia para resolver el caso en el que n es menor que k. y comience a buscar desde n, es decir, cada vez que busque la posición anterior, busque la siguiente posición y la posición actual dos veces. Cada vez que busque una nueva posición, registre la posición actual (q actúa como una matriz) y el número. de pasos necesarios para llegar a la posición actual (el paso actúa como una matriz) y registra los puntos que se han recorrido (la visita actúa como una matriz). Cuando se busca k, se obtiene el resultado. Se emite y el programa sale. Tenga en cuenta que el granjero John no necesita ir a un punto mayor o igual a 2*k, porque llegar a ese punto es peor que caminar en línea recta, lo que requiere menos pasos.

Acabo de terminar de cenar y había una pregunta sobre el agua en el plato. Esta es una pregunta de búsqueda amplia estándar.

No he usado Pascal en dos años...

¿NOIP?

¿NOIP?