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

using namespace std;

ifstream fin ("barbar.in");
ofstream fout ("barbar.out");

int n, m;
const int INF = 1e9;
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};
int d[1005][1005];
bool is_blocked[1005][1005], vis[1005][1005];
queue<pair<int, int>> q;

bool is_ok (int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && is_blocked[x][y] == false;
}
bool check (int mid, int i_s, int j_s, int i_e, int j_e) {
    if (d[i_s][j_s] < mid) {
        return 0;
    }
    if (i_s == i_e && j_s == j_e) {
        return 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            vis[i][j] = false;
        }
    }
    q.push(make_pair(i_s, j_s));
    vis[i_s][j_s] = true;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + di[k];
            int ny = y + dj[k];
            if (is_ok(nx, ny) && d[nx][ny] >= mid && vis[nx][ny] == false) {
                vis[nx][ny] = true;
                q.push(make_pair(nx, ny));
                if (nx == i_e && ny == j_e) {
                    return 1;
                }
            }
        }
    }
    return 0;
}
int b_s(int i_s, int j_s, int i_e, int j_e) {
    int le = 0, ri = 1e9;
    int ret = -1;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        //cout << check(mid, i_s, j_s, i_e, j_e) << " " << mid << "\n";
        if (check(mid, i_s, j_s, i_e, j_e)) {
            ret = mid - 1;
            le = mid + 1;
        }
        else {
            ri = mid - 1;
        }
    }
    return ret;
}
int main() {
    int i_start, j_start, i_end, j_end;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            d[i][j] = INF;
            char c;
            fin >> c;
            if (c == '*') {
                is_blocked[i][j] = true;
            }
            if (c == 'D') {
                q.push(make_pair(i, j));
                d[i][j] = 0;
            }
            if (c == 'I') {
                i_start = i;
                j_start = j;
            }
            if (c == 'O') {
                i_end = i;
                j_end = j;
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + di[k];
            int ny = y + dj[k];
            if (is_ok(nx, ny) && d[nx][ny] == INF) {
                d[nx][ny] = d[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    for (int i = 1; i <= n ; i++) {
        for (int j = 1; j <= m; j++) {
            cout << d[i][j] << " ";
        }
        cout << "\n";
    }
    int ans = b_s(i_start, j_start, i_end, j_end);
        fout << ans << "\n";
    //cout << check (2, i_start, j_start, i_end, j_end) << "\n";
}