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.

#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;
}