Red de conocimientos sobre prescripción popular - Conocimiento del confinamiento - Encuentra el camino más corto en el laberinto usando C++

Encuentra el camino más corto en el laberinto usando C++

El QQ que buscas es 85141512, que es mío.

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.