#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("barbar.in");
ofstream out("barbar.out");
int n, m, i, j, k, l, f, g, x, y, ii, jj;
struct Vector2 {
    int x, y;
};
Vector2 start;
Vector2 finish;
Vector2 aux;
Vector2 current;
Vector2 rotatie;
queue <Vector2> q;
int a[1005][1005];
bool vis[1005][1005];
char ch;
bool is_path(int level) {

    //clear
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            vis[i][j] = 0;
        }
    }
    while (!q.empty())q.pop();

    //fill
    q.push(start);
    while (!q.empty()) {
        current = q.front();
        q.pop();
        if (current.x == finish.x && current.y == finish.y)return 1;
        for (g = 1; g <= 4; g++) {
            l = rotatie.x;
            //roteste orientarea
            rotatie.x = -rotatie.y;
            rotatie.y = l;
            ii = rotatie.y + current.y;
            jj = rotatie.x + current.x;
            if (ii > 0 && jj > 0 && ii <= n && jj <= m) {
                if (!vis[ii][jj] && a[ii][jj]>level) {
                    aux.x = jj;
                    aux.y = ii;
                    q.push(aux);
                    vis[ii][jj] = 1;
                }
            }
        }
    }


    return 0;
}
int main()
{
    in >> n >> m;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            in >> ch;
            switch (ch)
            {
                case '.': {
                    break;
                }
                case 'I': {
                    start.x = j;
                    start.y = i;
                    break;
                }
                case 'D': {
                    aux.x = j;
                    aux.y = i;
                    vis[i][j] = 1;
                    q.push(aux);
                    break;
                }
                case 'O': {
                    finish.x = j;
                    finish.y = i;
                    break;
                }

            }
        }
    }
    rotatie.x = 1;
    rotatie.y = 0;
    int maxim=0;
    while (!q.empty())
    {
        current = q.front();
        q.pop();
        for (g = 1; g <= 4; g++) {
            l = rotatie.x;
            //roteste orientarea
            rotatie.x = -rotatie.y;
            rotatie.y = l;
            ii = rotatie.y + current.y;
            jj = rotatie.x + current.x;
            if (ii > 0 && jj > 0 && ii <= n && jj <= m) {
                if (!vis[ii][jj]) {
                    a[ii][jj] = a[current.y][current.x] + 1;
                    if (a[ii][jj] > maxim)maxim = a[ii][jj];
                    aux.x = jj;
                    aux.y = ii;
                    q.push(aux);
                    vis[ii][jj] = 1;
                }
            }
        }
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cout << a[i][j] << " ";
        }cout << '\n';
    }
    for (k = 1; k<maxim; k++) {
        if (!is_path(k)) {
            out << k;
            return 0;
        }
    }
    while (true);
}