Optimizar algoritmo de búsqueda BFS

[KINGARZA]

Hola a todos!!
Como algunos sabran estoy aprendiendo busquedas y me he topado con el siguiente problema:
LINK: https://omegaup.com/arena/problem/colosus-Laberinto#problems
O bien aqui lo escribo:

Colosus (Laberinto)

Límite de memoria   32MB
Límite de tiempo (caso)   1s
Límite de tiempo (total)   60s

Descripción

En este problema tu tomas el papel de el gran héroe Colossus tiene la misión de rescatar a la princesa omitilda de un laberinto, pero el maligno pachus quiere matar a la princesa.Lo único con lo que cuentas es con el mapa del laberinto y el tiempo en el que pachus va a llegar a la princesa, por lo que tu tienes que llegar en el menor tiempo posible a ella. El mapa consta de una cuadricula la cual tiene una 'X' en el lugar donde no puedes pasar Una 'C' donde tú te encuentras al principio, y una 'O' donde se encuentra la hermosa omitilda y una 'L' en aquellos lugares donde el campo este libre y puedas pasar.

Problema

Tu tarea consiste en escribir un programa que determine el menor tiempo en el que puedes llegar a rescatar a tu princesa tomando en cuenta que tu te mueves a una velocidad de un cuadro por seg. En caso de que no puedas llegar a salvarla escribirás en la pantalla un -1 en el caso contrario escribirás el tiempo en el que llegaste a ella. en caso de llegar al mismo tiempo considera que la princesa se salva.

Entrada

Tu programa deberá leer del teclado los siguientes datos: En la primera línea los números M, N y T separados por un espacio donde los primeros dos son las dimensiones del laberinto y T el tiempo en que pachus llegara con la princesa. Las siguientes M líneas contendrán N caracteres que representaran el mapa. Donde 3 <= M,N <=1000.

Salida

Tu programa deberá escribir un solo número que represente el tiempo en que llegaste ó -1 en caso de que no hayas llegado.

Ejemplos

Entrada   Salida
5 5 8           6
XXXXX
XCLLX
XXXLX
XOLLX
XXXXX

Consideraciones

Tu programa deberá ejecutarse en un tiempo máximo de 1 segundo.

Lo que yo hago es usar el algoritmo de búsqueda por anchura en un grafo (BFS), desafortunadamente mi respuesta me la 80% porque da limite de memoria podrian explicarme como puedo optimizar este programa por favor?
GRACIAS.

Código (cpp) [Seleccionar] Expandir

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000
char ady[MAX][MAX];
bool visitado[MAX][MAX];

struct Estado{
    int x;
    int y;
    int d;
    Estado(int x1, int y1, int d1) : x(x1), y(y1), d(d1) {}
};

int BFS(int x, int y, int h, int w){
    Estado inicial(x,y,0);
    queue<Estado>estados;
    estados.push(inicial);
    memset(visitado, false, sizeof(visitado));
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    while(!estados.empty()){
        Estado actual = estados.front();
        estados.pop();
        if(ady[actual.x][actual.y] == 'O')
            return actual.d;
        visitado[actual.x][actual.y] = true;
        for(int i = 0; i < 4; i++){
            int nx = dx[i] + actual.x;
            int ny = dy[i] + actual.y;

            if(nx >= 0 && nx < h && ny >= 0 && ny < w && ady[nx][ny] != 'X' && !visitado[nx][ny]){
                Estado adyacente(nx, ny, actual.d + 1);
                estados.push(adyacente);
            }
        }
    }
    return -1;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int h, w, x, y, t;
    cin>>h>>w>>t;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin>>ady[i][j];
            if(ady[i][j] == 'C'){
                x = i;
                y = j;
            }
        }
    }
    cout<<BFS(x, y, h, w);
    return 0;
}

[AlbertoBSD]

Tienes que resumir el Grafo.

Este problema se parece al que propuse en

https://foro.elhacker.net/programacion_cc/iquestimposible_juego_de_rompecabezas_imposible-t455410.0.html

En tan solo ese ese cuadro de 4x4 y con las reglas de ese juego, el generar todos los nodos consume toda la ram de mi humilde sistema XD

Ahora tu caso, cada que haces un push de un nodo nuevo generas una mini clase por lo que veo, tiene su constructor y todo eso, eso necesita mas memoria por nodo. Creo no estoy seguro ya que NUNCA he visto un constructor en una estrucutura.

Mejor creo crea una funcion aparte que te genere un nodo y te reserve la memoria necesaria para cada nodo.
Acabo de validar que lo anterior NO es cierto usan la misma momoria que la estructura normal.

Ahora como te mencione al principio es posible Resumir el grafo. En lugar de generar un nodo por cada espacio recorrible es posible que generar un Grafo mas compacto.

Ejemplo del ejemplo usado en la descripcion del problema.


nodo 0 una sola arista peso 2 a la izquierda.
nodo 1 una sola arista peso 2 arriba
nodo 2 una sola arista peso 2 a la derecha
Fin

Suma de la ruta 6

Incluso si solo es una arista puedes omitir ese nodo y solo dejar nodos que tengan mas de una arista (donde existan mas de un camino)

La otra es

Código (c) [Seleccionar] Expandir

#define MAX 1000
char ady[MAX][MAX];
bool visitado[MAX][MAX];

Ahi ya estas desperdiciando al menos 2 MB

por que no lo declaras dinamicamente en tiempo de ejecución y los usas solo mientras es necesario, una vez que ya no son necesarios puedes hacerles free y te ahorras hasta 2 MB de memoria.

Saludos