//1)Fac un BFS, avand initial in coada dragonii. Astfel, determin distanta minima de la fiecare celula
//din matrice, la un dragon.
//2)Cu un nou BFS, caut drumurile posibile intre celula de start si cea de sfarsit

#include <iostream>
#include <fstream>
#include <climits>
#include <queue>

struct Coord{
    int i;
    int j;
};

Coord Start;
Coord Final;

const int INF = INT_MAX;
const int BORDAT = -3;
const char PERETE = '*';
const char CELULA = '.';
const char START = 'I';
const char FINAL = 'O';

char harta[1005][1005];
int dragoni[1005][1005];
int col[4] = {1, 0, -1, 0};
int row[4] = {0, 1, 0, -1};

std::queue<Coord> coada;

///necesare pt Dijkstra
int drag[1005];
bool inCoada[1005];
class Compara
{
public:
    bool operator() (int x, int y)
    {
        return (drag[x] > darg[y]);
    }
};
std::priority_queue<int, std::vector<int>, Comapara> pri_queue;

void infinitizare(int _N, int _M){
    for(int i = 1; i <= _N; ++i){
        for(int j = 1; j <= _M; ++j){
            dragoni[i][j] = INF;
        }
    }

    for(int i = 1; i <= _N; ++i){
        drag[i] = INF;
    }
}

void bordare(int _N, int _M){
    for(int i = 1; i <= _N; ++i){
        dragoni[i][0] = dragoni[i][_N + 1] = BORDAT;
    }
    for(int j = 1; j <= _M; ++j){
        dragoni[0][j] = dragoni[_M + 1][j] = BORDAT;
    }
}

void read_file(int& _N, int& _M){
    std::ifstream in("barbar.in");

    in >> _N >> _M;
    infinitizare(_N, _M);
    bordare(_N, _M);
    for(int i = 1; i <= _N; ++i){
        for(int j = 1; j <= _M; ++j){
            in >> harta[i][j];
            if(harta[i][j] == 'D'){
                coada.push({i, j, 0});
                dragoni[i][j] = 0;
            }
            else if(harta[i][j] == START){
                Start = {i, j};
            }
            else if(harta[i][j] == FINAL){
                Final = {i, j};
            }
        }
    }
}


void BFS_dragoni(int N, int M){

    while(!coada.empty()){

        Coord poz_curr = coada.front();
        coada.pop();

        for(int dir = 0; dir < 4; ++dir){
            Coord tmp;
            tmp.i = poz_curr.i + row[dir];
            tmp.j = poz_curr.j + col[dir];

            if(dragoni[tmp.i][tmp.j] == INF && (harta[tmp.i][tmp.j] == CELULA
            || harta[tmp.i][tmp.j] == START || harta[tmp.i][tmp.j] == FINAL)){

                dragoni[tmp.i][tmp.j] = dragoni[poz_curr.i][poz_curr.j] + 1;
                coada.push({tmp.i, tmp.j});
            }
        }
    }
}

void BFS_drum(int _N, int _M){
    while(!coada.empty()){
        Coord nod_curr = pri_queue.top();
        pri_queue.pop();

        for(int dir = 0; dir < 4; ++dir){
            Coord vecin = {nod_curr.i + row[dir], nod_curr.j + col[dir]};
            int cost = dragoni[vecin.i][vecin.j];


        }
    }
}

int main()
{
    //citesc din fisier
    int N, M;
    read_file(N, M);

    //aplic BFS-ul pentru dragoni
    BFS_dragoni(N, M);
    for(int i = 0; i <= N + 1; ++i){
        for(int j = 0; j <= M + 1; ++j){
            std::cout << dragoni[i][j] << "   ";
        }
        std::cout << '\n';
    }

    //caut drumul
    coada.push(Start);
    BFS_drum(N, M);


    return 0;
}