#include <stdlib.h>
#include <stdio.h>
#define maxhole 10000
typedef enum {none,min1,plus1,maal2,over2} parents;
typedef struct field {
int distance;
parents next;
} field;
typedef struct queue {
int index;
int dist;
} queue;
int r,runs;
field hole[maxhole+1];
int size;
int fromhole,tohole;
void Init() {
int i;
for (i=1;i<=size;i++) {
hole[i].distance=maxhole*2;
hole[i].next=none;
}
}
void Dijkstra() {
queue q[maxhole+1]; /* Index to hole */
int qstart,qend;
field *tmp;
qstart=0;
q[0].index=tohole;
q[0].dist=0;
qend=1;
while (qend>qstart) {
if ((q[qstart].index % 2)==0) {
tmp=&(hole[q[qstart].index / 2]);
if (q[qstart].dist<tmp->distance) {
tmp->distance=q[qstart].dist;
tmp->next=maal2;
q[qend].index=q[qstart].index / 2;
q[qend].dist=q[qstart].dist+1;
qend++;
}
}
if (q[qstart].index>1) {
tmp=&(hole[q[qstart].index-1]);
if (q[qstart].dist<tmp->distance) {
tmp->distance=q[qstart].dist;
tmp->next=plus1;
q[qend].index=q[qstart].index-1;
q[qend].dist=q[qstart].dist+1;
qend++;
}
}
if (q[qstart].index<size) {
tmp=&(hole[q[qstart].index+1]);
if (q[qstart].dist<tmp->distance) {
tmp->distance=q[qstart].dist;
tmp->next=min1;
q[qend].index=q[qstart].index+1;
q[qend].dist=q[qstart].dist+1;
qend++;
}
}
if (q[qstart].index*2<=size) {
tmp=&(hole[q[qstart].index*2]);
if (q[qstart].dist<tmp->distance) {
tmp->distance=q[qstart].dist;
tmp->next=over2;
q[qend].index=q[qstart].index*2;
q[qend].dist=q[qstart].dist+1;
qend++;
}
}
qstart++;
}
}
void PrintPath() {
int current=fromhole;
printf("%d",current);
while (current!=tohole) {
switch (hole[current].next) {
case none: break; /* eliminates gcc-warning */
case min1: current-=1; break;
case plus1: current+=1; break;
case maal2: current*=2; break;
case over2: current/=2; break;
}
printf(" %d",current);
}
printf("\n");
}
int main() {
scanf("%d",&runs);
for (r=0;r<runs;r++) {
scanf("%d",&size);
Init();
scanf("%d %d",&fromhole,&tohole);
hole[tohole].distance=0;
Dijkstra();
PrintPath();
}
return(0);
}
Generated by Java2Html