Solicitud urgente: ¡Código para el problema del laberinto implementado en lenguaje C!
#include
#include
#include
estructura nodo
{
int sign;//Identificación, 0 está en nada, 1 está abierto, 2 está cerrado
int flag;//flag Bit 0/1, 0 se puede mover, 1 no se puede mover
int f, g, h;//función de juicio
int x, y;//coordenadas
int old; //Si el nodo es antiguo, 0 no lo es, 1 es sí
};
struct link
{
nodo fnodo;
enlace *siguiente;
enlace *pri;
};
enlace *abierto, *cerrado,*mejornodo,*sucesor,*p,*q,*r,*s;
int maze_flag[7][7]={ {0,1,0,0,0,0 ,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1 ,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//Una matriz que representa el laberinto , 0 se puede caminar, 1 no se puede ir
laberinto de nodos[7][7];
int juez(nodo n)// Función de juicio para determinar si el nodo n puede ir
{
if(n.flag==1)
return(1);
else
return(0);
}
void in_open(node n)//Coloque n nodos en la tabla abierta
{
p=abrir;
while(p->siguiente!=abrir)
{
if(n.f>=p->fnode. f)
{
p->siguiente->pri=(enlace *)malloc(tamañode(enlace));
p->siguiente-> pri->pri=p;
p=p->siguiente;
p->pri->siguiente=p;
p->pri- >pri->next=p->pri ;
p=p->pri;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p- >fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p- >fnode.sign=n.sign=1 ;
}
más
p=p->n
text;
}
open->pri=(link *)malloc(sizeof(link));
open->pri->pri=p ;
open->pri->next=open;
p->next=open->pri;
p=p->siguiente;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p->fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p->fnode.sign=n.sign=1;
}
void out_open(node n)//Eliminar n nodo de la tabla abierta
{
p=open;
while(p->next! = abrir)
{
if(n.f=p->fnode.f)
{
enlace *p1;
p1=p->siguiente;
p->siguiente=p->siguiente->siguiente;
p->siguiente->pri=p;
p>libre(p1);
n.sign=0;
}
más
p =p- >siguiente;
}
}
void in_closed(node n)//Coloque n nodo en la tabla cerrada
{
while(q->siguiente!=cerrado)
{
if(n.f>=q->fnode.f)
{
q->siguiente->pri=(enlace *)malloc(tamañode(enlace));
q->siguiente->pri->pri =q;
p>q=q->siguiente;
q->pri->siguiente=p;
q->pri->pri ->next=q->pri;
q=q->pri;
q->fnode.flag=n.flag;
q- >fnode.f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnodo .x=n.x;
p>
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign=n.sign= 2;
}
más
q=q->siguiente;
}
cerrado-> pri=(enlace *)malloc(tamañode
(enlace));
cerrado->pri->pri=q;
cerrado->pri->siguiente=cerrado;
q->siguiente =cerrado->pri;
q=q->siguiente;
q->fnode.flag=n.flag;
q->fnode. f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnode.x= n.x;
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign= n.sign=2;
}
void out_closed(node n)//Eliminar n nodo de la tabla cerrada
{
q=cerrado;
while(q->siguiente!=cerrado)
{
if(n.f=q->fnode.f)
{
enlace *q1;
q1=q->siguiente;
q->siguiente=q->siguiente- > siguiente;
q->siguiente->pri=q;
gratis(q1);
n.sign=0;
}
más
q=q->siguiente;
}
}
void in_bestnode (nodo n)//Establecer n nodo como mejor nodo
{
while(r->next!=bestnode)
{
if(n.f>=r->fnode.f)
{
r->next->pri=(link *)malloc(sizeof(link));
r->siguiente->pri->pri=r;
r=r->siguiente;
r->pri->siguiente=r;
r->pri->pri->next=r->pri;
r=r->pri;
r->fnode.flag =n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r->fnode.h =n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode.old=n .old;
}
else
r=r->siguiente;
}
mejornodo- >pri=(enlace *)malloc(sizeof(enlace));
bestnode->pri->pri=r;
ser
stnode->pri->siguiente=mejornodo;
r->siguiente=mejornodo->pri;
r=r->siguiente;
r- >fnode.flag=n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r- >fnode.h=n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode .old=n.old;
}
void out_bestnode(nodo n)//Eliminar el mejor nodo del nodo n
{
r=mejornodo;
while(r->siguiente!=mejornodo)
{
if(n.f=p->fnodo.f)
{
enlace *r1;
r1=r->siguiente;
r->siguiente=r->siguiente- >siguiente ;
r->siguiente->pri=r;
gratis(r1);
}
más
r=r->next;
}
}
void in_successor(nodo n)//Establecer n nodo como sucesor nodo
p>{
s=sucesor;
while(s->siguiente!=sucesor)
{
if (n.f>=s->fnode.f)
{
s->next->pri=(enlace *)malloc(sizeof(enlace)) ;
s->siguiente->pri->pri=s;
s=p->siguiente;
s->pri->siguiente= s;
s->pri->pri->next=s->pri;
s=s->pri;
s->fnodo .flag=n.bandera;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode .h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
s->fnode.old =n.old;
}
más
s=s->siguiente;
}
sucesor->pri= (enlace *)malloc(sizeof(enlace));
sucesor->pri->pri=s;
sucesor->pri->next=sucesor ;
s->siguiente=sucesor->pri;
s=s->siguiente;
s->fnode.flag=n.flag;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode.h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
p>
s->fnode.old=n.old;
}
void out_successor(node n)//Eliminar el sucesor de nodo n
{
s=sucesor;
while(s->siguiente!=sucesor)
{
if(n.f= p->fnode.f)
{
enlace *s1;
s1=s->siguiente;
s-> siguiente=s->siguiente->siguiente;
s->siguiente->pri=s;
gratis(s1);
}
más
s=s->siguiente;
}
}
nulo print(link *n)/ /Tabla de tipos de enlaces de salida n
{
link *forprint;
forprint=n;
printf("la clave es ");
while(forprint->next!=n)
printf("(%d,%d)\n",forprint-> fnode.x,forprint- >fnode.y);
}
int main()
{
//Parte de inicialización
//La función de esta parte es asignar la matriz de enteros bidimensional a la matriz bidimensional de tipo nodo
int i=0,j=0;
para(i=0 ;i<7;i++)
para(j=0;j<7;j++)
{
laberinto[i][j].x =i;
laberinto[i][j].y=j;
laberinto[i][j].flag=maze_flag [i][j];
if(laberinto[i][j].flag==0)
{
laberinto[i][j ].h=6-i+6- j;
laberinto[i][j].sign=laberinto[i][j].f=laberinto[i][j].g=laberinto [i][j].old=0 ;
}
else
laberinto[i][j].h=-1;
}
for(i=0;i<7;i++)//Diagrama de laberinto de salida
{
for(j=0; j<7;j++)
{
printf("%2d",maze_flag[i][j]);
}
printf("\n");
}
//La función de esta parte es inicializar las tablas abiertas, cerradas y de mejor nodo y configurarlas como tablas vacías
p=open=(enlace * )malloc(tamañoo
f(enlace));
abrir->siguiente=abrir;
abrir->pri=abrir;
q=cerrado=(enlace *)malloc (sizeof(enlace));
cerrado->siguiente=cerrado;
cerrado->pri=cerrado;
r=bestnode=(enlace *) malloc(sizeof(link));
bestnode->next=bestnode;
bestnode->pri=bestnode;
//Cambiar el primer elemento que es decir, coloque el nodo (0,0) en la tabla abierta e inicie el algoritmo
in_open(maze[0][0]);
maze[0][0] .f=laberinto [0][0].h;
enlace *s2;
s2=sucesor;
if(open->siguiente!= open)// Si la tabla abierta está vacía, fallará y saldrá
{
while(1)
{
in_bestnode(open->fnode); //Coloca el primer elemento de la tabla abierta en bestnode
in_closed(maze[open->fnode.x][open->fnode.y]); Coloque el primer elemento de la tabla abierta en elementos de bestnode en un laberinto cerrado
[open->fnode.x][open->fnode.y].g++;//Agregue uno al valor g de primer elemento de la tabla abierta, lo que significa Ya he dado un paso
out_open(maze[open->fnode.x][open->fnode.y]);//Eliminar el primer elemento de la tabla abierta table
if(bestnode->fnode.x==6&&bestnode->fnode.y==6)//Si bestnode es el nodo de destino, salga correctamente
{
printf("éxito!!\nluego imprime la clave:\n");
print(cerrado);
break;
}
else //Si el mejor nodo no es el nodo objetivo, expande sus nodos adyacentes para que sean el sucesor
{
if(i==0||j= =0||i== 6||j==6)
{
if(i==0&&j==0)//Si es (0,0) , juzgue los elementos de la derecha y de abajo
{
if(judge(maze[i][j+1])==0)
in_successor (laberinto[i][j+1 ]);
if(juez(laberinto[i+1][j])==0)
in_successor(laberinto[i+ 1][j]);
}
else if(i==0&&j==6)//Si es (0,6), determina los elementos de la izquierda y debajo
{
if(judge(maze[i-1][j])==0)
in_successor(laberinto[i-1][j]);
if(juez(laberinto[i+1][j])==0)
in_successor(laberinto[i +1][j]);
}
else if(i==6&&j==0)//Si es (6,0), juzga la izquierda y la parte superior Elemento
{
if(judge(laberinto[i-1][j])==0)
in_successor(laberinto[i-1][ j]);
if(judge(laberinto[i][j-1])==0)
in_successor(laberinto[i][j-1]);
}
else if(i==6&&j==6)//Si es (6,6), determine los elementos izquierdo y superior
{
if(judge(laberinto[i-1][j])==0)
in_successor(laberinto[i-1][j]);
if(juez(laberinto[i][j-1])==0)
in_successor(laberinto[i][j-1]);
}
else if(i==0)// Si es un elemento en la primera fila (no en la esquina), juzgue los lados izquierdo, inferior y derecho
{
if(juez(laberinto[i][j+1])==0)
in_successor(laberinto[i][j+1]);
if(juez(laberinto [i][j-1])==0)
in_successor(laberinto[i][j-1]);
if(juez(laberinto [i+1] [j])==0)
in_successor(laberinto[i+1][j]);
}
más si (i==6) // Si es un elemento en la séptima fila (no en la esquina), juzgue los lados izquierdo, superior y derecho
{
if( juez(laberinto[i][j+1 ])==0)
in_successor(laberinto[i][j+1]);
if(juez(laberinto[i ][j-1])==0 )
in_successor(laberinto[i][j-1]);
if(juez(laberinto[i-1][j ])==0)
in_successor(laberinto[i-1][j]);
}
else if(j==0)/ /Si es un elemento en la primera columna (no en la esquina), entonces juzgue los lados derecho, inferior y superior
{
if(judge(maze[i+1][ j])==0)
in_successor(laberinto[i+1][j]);
if(juez(laberinto[i-1][j])== 0)
in_successor(laberinto[ i-1][j]);
if(juez(ma
ze[i][j+1])==0)
in_successor(laberinto[i][j+1]);
}
else if(j==6)//Si es un elemento en la séptima columna (no en la esquina), entonces juzgue los lados izquierdo, superior y superior
{
if (juez(laberinto[ i+1][j])==0)
in_successor(laberinto[i+1][j]);
if(juez(laberinto[ i-1][j])==0)
in_successor(laberinto[i-1][j]);
if(juez(laberinto[i][j- 1])== 0)
in_successor(laberinto[i][j-1]);
}
}
else//if Para el elemento Teniente General, juzga los nodos en las cuatro direcciones
{
if(judge(maze[i][j-1])==0 )
in_successor(laberinto[i][j-1]);
if(juez(laberinto[i][j+1])==0)
in_successor(laberinto [i][j+1]);
if(juez(laberinto[i-1][j])==0)
in_successor( laberinto[i-1] [j]);
if(juez(laberinto[i+1][j])==0)
in_successor(laberinto[i+1 ][j]);
}
}
while(s2->next!=successor)//Realice las siguientes operaciones en todos los nodos sucesores
{
laberinto[s2->fnode.x][s2->fnode.y].g=bestnode->fnode.g+bestnode->fnode.h;// Calcular g(suc)= g(bes)+h(bes,suc)
if(s2->fnode.sign==1)//Si está en la tabla abierta, configúrelo en antiguo y observe la g más pequeña. Y retírela de la mesa abierta y colóquela en la mesa cerrada
{
s2->fnode.old=1;
if(s2->fnode. g
{
laberinto[s2-> fnode.x][s2->fnode.y].g=s2->fnode.g;
laberinto[s2->fnode.x][s2->fnode.y].f=laberinto [s2->fnode.x] [s2->fnode.y].g+laberinto[s2->fnode.x][s2->fnode.y].h;
out_open(laberinto[ s2->fnode.x][ s2->fnode.y]);
in_closed(laberinto[s2->fnode.x][s2->fnode.y]
);
laberinto[s2->fnode.x][s2->fnode.y].old=0;
}
más
continuar;
}
else if(s2->fnode.sign==2)//Si está en la tabla cerrada, configúrelo en antiguo, escriba elimine el g pequeño anterior, elimine el antiguo de la tabla cerrada y coloque el nodo de g más pequeño en la tabla cerrada
{
s2->fnode.old=1;< / p>
if(s2->fnode.g
{
laberinto [s2->fnode.x][s2->fnode.y].g=s2->fnode.g;
laberinto[s2->fnode.x][s2->fnode.y ] .f=laberinto[s2->fnode.x][s2->fnode.y].g+laberinto[s2->fnode.x][s2->fnode.y].h;
out_closed(laberinto[s2->fnode.x][s2->fnode.y]);
in_closed(laberinto[s2->fnode.x][s2->fnode.y]); /p>
laberinto[s2->fnode.x][s2->fnode.y].old=0;
}
más
continuar;
}
else//Si ya no está en la tabla abierta o en la tabla cerrada, coloque este nodo en la tabla abierta y calcule el valor de este nodo f valor
{
in_open(laberinto[s2->fnode.x][s2->fnode.y]);
laberinto[s2->fnode .x][s2->fnode.y].f=laberinto[s2->fnode.x][s2->fnode.y].g+laberinto[s2->fnode.x][s2->fnode. ].h;
}
s2=s2->siguiente;
}
s2=sucesor;
}
}
else
printf("¡error!! ¡¡Este laberinto no tiene respuesta!");
retorno(0);
}