Encuentra el camino más corto en el laberinto usando C++
Estoy navegando por Internet en la empresa y no puedo acceder a QQ. Siento pena.
Si tiene alguna pregunta, envíela a Baidu en mi mensaje.
Se trata de estructuras de datos.
Lo encontré y lo publiqué:
# include & ltiostream.h & gt
# include & ltstdlib.h & gt
# include & ltiomanip.h & gt
# define stack _ init _ size 100//Tamaño de pila inicial
# definestackincrement 10//Aumentar la longitud de la pila.
#Define MAPH 20 //El tamaño de la altura del laberinto
#Define MAPW 20 //El tamaño de la longitud del laberinto
///// //// //////////////////////////////////////////////// //////// //////////////////////
//Nombre de la estructura: MazeCell
//Función: se utiliza para describir la información del componente del laberinto.
//Miembro: Pase: Cuando el Pase es 1, significa un bloque conductor; 0 significa un bloque de obstáculo
// Huella: Cuando la huella es 1, significa una; Se deja huella, de lo contrario significa que no ha pasado por aquí.
//////////////////////////////////////////// // ////////////////////////////////////////
typedef estructura
{
int Pass
Huella booleana;
}Mazessel;
///// // ///////////////////////////////////////////////// ////// ///////////////////////////////////// Nombre de la estructura: SElemType
//Función: Esta es la pila Un elemento de, que se utiliza para representar la ubicación actual (la pila se utiliza para describir la ruta actual).
//Miembro:ord: Número de serie del bloque de canal.
// x: la abscisa de la posición actual
// y: la ordenada de la posición actual
// di: dirección de búsqueda 1 este 2 Sur 3 Oeste 4 Norte.
//////////////////////////////////////////// // ////////////////////////////////////////
estructura typedef
{
int orden;
int x;
int y;
int di
} SElemType
////////////////////////////////////// ////// ///////////////////////////////////////////
//Nombre de la estructura: SqTack
//Función: esta es la pila utilizada para registrar la ruta actual.
//Miembro: *El puntero inferior de la pila base apunta al punto de partida.
// *top es el puntero superior de la pila, que apunta al final de la ruta.
tamaño de pila capacidad de pila
///////////////////////////////// /////////////////////////////////////////////////// / p>
estructura typedef
{
SElemType * base
SElemType * top
int tamaño de pila
} SqStack
///////////////////////////////////////// /// //////////////////////////////////////////
//Nombre de la estructura: Asiento
//Función: se utiliza para registrar las coordenadas del laberinto. Esta estructura es una variable intermedia creada exclusivamente para facilitar la programación.
//Miembro: X: se utiliza para registrar la abscisa.
// y: se utiliza para registrar la coordenada vertical.
//////////////////////////////////////////// // ////////////////////////////////////////
typedef estructura
{
int x;
int y
}asiento; ///// ////////////////////////////////////////////// //////// //////////////////////
//Nombre de la función: InitStack
//Función: esta función se utiliza para inicializar una pila, es decir, buscar una pila de tamaño STACK_INIT_SIZE en la memoria de la clase.
//Elemento y asigna su primera dirección al puntero inferior de la pila. En este punto, el puntero superior de la pila coincide con el puntero inferior. Capacidad de pila
//La cantidad es STACK_INIT_SIZE. Si la operación es exitosa, la función devuelve 1, si el espacio de almacenamiento de la clase es insuficiente, la función devuelve.
// 0, indica que la inicialización falló.
//Parámetros de función: sq stack & S
//Tipo de valor de retorno de función: bool
/////////// /////////////////////////////////////////////////// /// ////////////////////
bool init stack(sq stack & s)
{
s .base =(tipo selem *)malloc(STACK _ INIT _ TAMAÑO * sizeof(tipo selem));
if (! base de EE. UU.)
{< /p >
Devuelve 0;
}
s . top = s base;
S.stacksize = STACK _ INIT _ TAMAÑO
Devuelve 0;
}
/////////////////////////// /// //////////////////////////////////////////////// ////// /
//Nombre de la función: BuildMaze
//Función: La función de esta función es crear un mapa de laberinto de acuerdo con los requisitos del usuario y transformar el entrada de matriz de plástico por parte del usuario.
//La forma es una matriz de laberinto
//
//Parámetros de función: mapa de unidad de laberinto [tamaño _ de _ mapa] [tamaño _ de _ map ]
//Coordenadas del punto inicial del asiento y del amplificador
//Coordenadas del punto final del asiento y del amplificador
//Tipo de valor de retorno de la función: bool devuelve 1 si se establece correctamente, de lo contrario devuelve 0.
//////////////////////////////////////////// // ////////////////////////////////////////
void BuideMaze (Mazesai er mapMap size][MAPW size], int ma[MAPH size][MAPW size])
{
for(int I = 0;i<MAPH size;i++ )
{
for(int j = 0; j & ltMAPW size; j++)
{
Mapa[i] [j] . pasar = ma[I][j];
Mapa[i][j]. huella = 0;
}
}
}
/////////////// /////////////////////////////////////////////////// /// ////////////////
//Nombre de función: Pasar
//Función: esta función se utiliza para determinar si el punto actual es alcanzable. Devuelve 1 si es accesible, 0 en caso contrario.
//La llamada transitabilidad significa que la posición actual es un bloque conductor y no quedan huellas en la posición actual.
//Parámetros de función: Asienta las coordenadas del bloque actual.
//Mapa de unidad de laberinto [tamaño del mapa] [tamaño del mapa] mapa de laberinto
//Tipo de valor de retorno de función: si el bloque actual se puede generalizar, bool devuelve 1; de lo contrario, devuelve 0.
//////////////////////////////////////////// // ////////////////////////////////////////
Pase booleano Mapa de Persia, Mazessel Tamaño del mapa][Tamaño MAPW])
{
if(map[curpos.x][curpos.y].pass == 0)
{
Devuelve 0;
}
else if(Mapa[curpos.x][curpos.y]. Huella== 1)
{
Devuelve 0;
}
Otros
{
Devuelve 1 ;
}
}
//////////////////////// // /////////////////////////////////////////////////// / ///////
//Nombre de la función: FootPrint
//Función: esta función se utiliza para dejar huellas en la ruta actual.
//Parámetros de función: las coordenadas actuales del curpos del asiento.
//Mapa de unidad de laberinto [tamaño del mapa] [tamaño del mapa] mapa de laberinto
//Tipo de valor de retorno de función: Ninguno
////// /////////////////////////////////////////////////// /// ////////////////////////////////////////
Huella vacía (Seat curpos, mapa MazeCell Tamaño del mapa] [tamaño MAPW])
{
Mapa[curpos.x][curpos.y].
huella = 1;
}
boolean push(SqStack & amps, SElemType e) // función de inserción de pila
{
if (s . top-s . base>=S.stacksize)
{
s . base =(tipo selem *)realloc(s . base, (s . tamaño de pila+ incremento de pila)* sizeof(tipo selem));
if (! base de EE. UU.)
{
Devuelve 0;
}
s .top = s .base+s .tamaño de pila;
}
p>
* s . top++ = e;
Return 1;
}
bool Pop(SqStack & s, seleccione tipo & ampE)/ /Elimina el elemento superior de la pila y asigna el valor a e.
{
if(S.base==S.top) devuelve falso
s top-;
e = *. S.top
Devuelve verdadero
}
//////////////////////// / ///////////////////////////////////////////////// ///// ///////
//Nombre de la función: NextPos
//Función: esta función se utiliza para cambiar la posición en la dirección di de X e Y a la posición actual.
//Parámetros de función: las coordenadas actuales del curpos del asiento.
// int di dirección
// int x, y coordenadas
//Tipo de valor de retorno de función: Ninguno
// /////////////////////////////////////////////////// //// /////////////////////////////
void NextPos(int x, int y, Seat & ampcurpos, int di )
{
if(di==1)
{
curpos . ;
curpos.x = x
}
si no(di==2)
{
curpos . x = x+1;
curpos.y = y
}
si no(di==3)
{
curpos . y = y-1;
curpos.x = x
}
else if(di== 4)
{
curpos .x = x-1
curpos.y = y
}
<; p>}///////////////////////////////////////// //////// ///////////////////////////////////Nombre de función: Putin
//Función: Introducir elementos en la matriz.
//Parámetros de función: int map[] proporciona la matriz de resultados que se asignará.
//int La longitud del laberinto de Wei
La altura del laberinto de Inthig
//Tipo de valor de retorno de función: Ninguno
/// /////////////////////////////////////////////// //////// ///////////////////////////////////
nulo putin(int mapa[], int & Wei International Trade Co., Ltd.; alto)
p>{
int w, h;
cout & lt& ltSi el laberinto al que desea ingresar es más grande que el tamaño especificado, solo necesita modificar el tamaño del MAPH y el Tamaño del mapa
cout & lt& lt"Ingrese la longitud del laberinto ( la longitud es menor o igual que "
CIN & gt;& gtw;
cout & lt& lt" Ingrese la altura del laberinto (la altura es menor o igual a "
CIN>>h;
cout<<"1 representa el bloque conductor; 0 representa el bloque obstáculo"
wei = w;
hig = h;
for(int i = 0; i<MAPH size; i++)
for( int j = 0; tamaño de j & ltMAPW; j++)
*(mapa+I * TAMAÑO _ DE _ MAPW+j)= 0;
for(int es = 1 ; es & lth+1; es ++)
{
cout & lt& lt"Ingrese el primero"
for(int js = 1 ; js & ltw+1; js++)
{
int punto;
CIN & gt;& gt punto;
* (mapa+es * TAMAÑO _ DE _ MAPW+js)=punto;
}
cout & lt& ltendl
}
}
////////// ////////////////////////////////// //////////////// //////////////////
//Nombre de la función: mostrar
//Función: se utiliza para mostrar todos los elementos en la pila
//Parámetros de función: Ninguno
//Tipo de valor de retorno de función: Ninguno
//////////////// ///////////////////////////////////// ///////////// //////////////
Pantalla vacía (SqStack S)
{
int I = 1;
selem escriba * p;
p = s .
cout & lt& lt"de abajo hacia arriba:"
cout & lt& lt" di dirección de búsqueda: di=1 este, di=2 sur, di=3 oeste, di=4 norte" < & ltendl
Y ( p! =S.top) //Imprime elementos de abajo hacia arriba.
{
cout & lt& lt"Primero"
cout & lt& lt"(" & lt& lt(*p).y;
cout & lt& lt","& lt& lt(*p).
cout & lt& lt","& lt& lt(*p).
di & lt& lt")" & lt& ltendl
p++;
i++;
}
}
laberinto de visualización nula (int ma[tamaño MAPH][tamaño MAPW], int w, int h)
{
cout & lt& lt"El laberinto es (1 significa que puede pasarse; 0 significa fallido):"
for(int I = 0;i<h+2;i++)
{
for(int j = 0 ; j & ltw+2; j++)
{
cout & lt& ltma[I][j]& lt;& lt" ";
}
cout & lt& ltendl
}
cout & lt& ltendl
}
///// /////////////////////////////////////////////////// /// /////////////////////
//Nombre de la función: MazePath
//Función: organizar todo subfunciones, resolver laberinto.
//Parámetros de función: Ninguno
//Tipo de valor de retorno de función: 1 Si el laberinto int tiene solución, si no hay solución, es 0;
//// //////////////////////////////////////////// ////////// ////////////////////////
int ruta del laberinto(mapa de la celda del laberinto[MAPA tamaño][tamaño MAPW], punto inicial del asiento, punto final del asiento)
{
Seleccione el tipo;
sq stack S //Defina una pila;
InitStack//Inicializar la pila
p>Curvatura del asiento; //Definir la posición actual
int curstep//Podómetro
curstep = 1; //Podómetro 1
curpos . x = inicio .
cout & lt& lt "El destino es:"
/////. ///////////////////// ////////////////////////////// ////////////////////////
//
//El siguiente bucle es el programa principal para resolviendo el laberinto.
//////////////////////////////////////////// // //////////////////////////////////
Hacer
{
If(Pass(curpos,Map)) //Si el bloque actual es accesible, haga lo siguiente.
{
Huellas (curpos, Mapa); //Dejar huellas
e.ord = curstep//Recuerda el podómetro
e .x = curpos . //Supongamos que una dirección es el este.
Push(S, e); //Operación de inserción de pila, incluida la posición actual en la ruta actual.
si(curpos .
{ //
cout & lt& lt"OK!"; //
Displayer //Llama a la subrutina de la pila de visualización para mostrar el resultado; .
Devuelve 1; //La función devuelve 1.
} //
De lo contrario //Si la posición actual no es el punto final, realice las siguientes operaciones
{ //
NextPos(curpos .x, curpos.y, curpos, 1); //Cambia la posición este a la posición actual
cur step++; Aumenta el podómetro en 1.
}
}//Si
Otro
{
Si (S.base!=S .top) //Si el bloque actual es inaccesible, la pila no está vacía (lo que indica que todavía hay una solución)
{
Pop(S, e); Pop la parte superior de la pila para continuar con la observación.
while(e . di = = 4 & & amp(S.top-S.base)) //Si los cuatro elementos en la parte superior de la pila están bloqueados.
{
Pop(S, e); // Extrae el siguiente elemento superior de la pila para observarlo.
}//Cuando
if(e . di & lt; 4) //Si el elemento superior de la pila no se transfiere en otras direcciones,
{ //
e . di++; // Cambia la siguiente dirección a la dirección actual.
Push(S, e); //Empujar en la pila
NextPos(e.x, e.y, curpos, e.di); //Cambia la siguiente posición de dirección a la actual. posición .
}//si
}//si
}//else
} while(S.base!= s. top); //Mientras la pila no esté vacía, significa que hay una solución y el ciclo se repite.
cout & lt& lt"Ruta no encontrada"
}
/////////////////// /////////////////////////////////////////////////// // ////////////
//Nombre de la función: principal
//Función: organiza todas las subfunciones y resuelve el laberinto.
//Parámetros de función: Ninguno
//Tipo de valor de retorno de función: bool maze Si hay una solución, devuelve 1, de lo contrario devuelve 0;
//
///////////////////////////////////////// /////// ///////////////////////////////////////
void main()
{
Mapa de Mazessel Tamaño del mapa][Tamaño de MAPW] //Definir una matriz de laberinto
/* int migong[MAPH tamaño][Tamaño MAPW] = {
{ 0,0,0,0,0,0,0,0,0,0},
{ 0,1,1 ,0,0,0 ,0,0,0,0}, //1
{ 0,0,1,1,1,0,1,1,1,0}, // 2
{ 0,0,1,0,1,1,1,0,1,0}, //3
{ 0,0,1,0,0 ,0,0,0 ,1,0}, //4
{ 0,0,1,0,1,1,1,0,0,0}, //5
{ 0 ,0,1,1,1,0,1,1,1,0}, //6
{ 0,0,0,0,0,0,0 ,0,0,0 },
};// Laberinto representado por matriz*/
int w, h;
int migong[tamaño MAPH] [Tamaño de MAPW];
Putin(Migong[0],w,h);
BuideMaze(map, Migong); //Llama a la subfunción que crea el laberinto.
DisplayMaze(Migong, w, h); //Muestra la forma del laberinto.
Asiento inicio, fin; //Estructura que define la posición actual, posición inicial y posición final
/* inicio . p> inicio . y = 1; //
fin . x = 2; //punto final
fin . >cout & lt& lt"Punto de partida abscisa:";
CIN & gt;& gtstart.y
cout & lt& lt"Punto de partida ordenada:";
CIN & gt; & gtstart. lt<"Fin de ordenada:";
CIN & gt;& gtend.x
MazePath(mapeo, inicio, fin);
}
p>La mayoría de los programas están divididos por función. Sólo necesitas descubrir qué hace la función y listo.
¡Te deseo éxito! Pasé tres días escribiéndolo.