#include <cstdio>
using namespace std;

enum BoardValue { eSpace = 1 , eWall , eDragon } ;

int const maxdim = 1000;
char line  [ 1 + maxdim ] ;
 int theMap  [ maxdim ] [ maxdim ] ;
 int used  [ maxdim ] [ maxdim ] ;
 int theQueue [ maxdim * maxdim ] [ 2 ] , queueIn , queueOut ;
 int theDistance [ maxdim ] [ maxdim ] ;
 int numRows, numCols ;
 int theStart [ 2 ], theStop [ 2 ] ;

int
main () {
  FILE * io = fopen ( "barbar.in", "r" ) ;
  fscanf ( io, "%d %d\n", & numRows, & numCols ) ;
  queueIn = 0 ; queueOut = 0 ;
  int i , j ;
  for ( i = 0 ; i < numRows  ; i ++ ) {
    fgets (line, 2 + maxdim, io ) ;
    for ( j = 0; j < numCols ; j ++ ) {
      switch (line [j]) {
      case 'I':
        theMap [ i ] [ j ] = eSpace ;
        theStart [ 0 ] = i ;
        theStart [ 1 ] = j ;
        break ;
      case '.':
        theMap [ i ] [ j ] = eSpace ;
        break ;
      case '*':
        theMap [ i ] [ j ] = eWall ;
        theDistance [ i ] [ j ] = 0 ;
        break ;
      case 'D':
        theMap [ i ] [ j ] = eDragon ;
        theQueue [ queueIn ] [ 0 ] = i ;
        theQueue [ queueIn ] [ 1 ] = j ;
        ++ queueIn ;
        break ;
      case 'O':
        theMap [ i ] [ j ] = eSpace ;
        theStop [ 0 ] = i ;
        theStop [ 1 ] = j ;
        // theDistance [ i ] [ j ] = numRows * numCols + 10 ; // inf
        break ;
      default : theMap [ i ] [ j ] = eSpace ; break ;
      }
    }
  }
  for ( i = 0 ; i < numRows ; i ++ ) {
    for ( j = 0; j < numCols ; j ++ ) {
      used [ i ] [ j ] = 0 ;
    }
  }
  int nDistance = 0 ;
  while ( queueOut < queueIn ) {
    int queueIn2 = queueIn ;
    int queueSlider ;
    int r, c;
    for ( queueSlider = queueOut ; queueSlider < queueIn ; queueSlider ++ ) {
      r = theQueue [ queueSlider ] [ 0 ] ;
      c = theQueue [ queueSlider ] [ 1 ] ;
      theDistance [ r ] [ c ] = nDistance ;
      if ( ( 0 < r ) && ( eSpace == theMap [ r - 1 ] [ c ] ) && 
           ! used [ r - 1 ] [ c ] ) {
        theQueue [ queueIn2 ] [ 0 ] = r - 1 ;
        theQueue [ queueIn2 ] [ 1 ] = c ;
        used [ r - 1 ] [ c ] = 1 ;
        ++ queueIn2 ;
      }
      if ( ( numRows > r + 1 ) && ( eSpace == theMap [ r + 1 ] [ c ] ) && 
           ! used [ r + 1 ] [ c ] ) {
        theQueue [ queueIn2 ] [ 0 ] = r + 1 ;
        theQueue [ queueIn2 ] [ 1 ] = c ;
        used [ r + 1 ] [ c ] = 1 ;
        ++ queueIn2 ;
      }
      if ( ( 0 < c ) && ( eSpace == theMap [ r ] [ c - 1 ] ) && 
           ! used [ r ] [ c - 1 ] ) {
        theQueue [ queueIn2 ] [ 0 ] = r ;
        theQueue [ queueIn2 ] [ 1 ] = c - 1 ;
        used [ r ] [ c - 1 ] = 1 ;
        ++ queueIn2 ;
      }
      if ( ( numCols > c + 1 ) && ( eSpace == theMap [ r ] [ c + 1 ] ) && 
           ! used [ r ] [ c + 1 ] ) {
        theQueue [ queueIn2 ] [ 0 ] = r ;
        theQueue [ queueIn2 ] [ 1 ] = c + 1 ;
        used [ r ] [ c + 1 ] = 1 ;
        ++ queueIn2 ;
      }
    }
    queueOut = queueIn ;
    queueIn  = queueIn2 ;
    ++ nDistance ;
  }

  for ( i = 0 ; i < numRows ; i ++ ) {
    for ( j = 0; j < numCols ; j ++ ) {
      if ( numRows * numCols + 10 != theDistance [ i ] [ j ] ) {
        printf ( " %d", theDistance [ i ] [ j ] ) ;
      } else {
        printf ( " #" ) ;
      }
    }
    printf ( "\n" ) ;
  }


  int nSolMin = 0 ;
  int nSolMax = numRows * numCols ;
  int nSol = - 1 ;
  int nSolMiddle ;
  bool bSolFound ;
  while ( nSolMin < nSolMax ) {
    nSolMiddle = (nSolMin + nSolMax) / 2 ;
    // bfs nSolMidle
    bSolFound = false ;
    if (nSolMiddle <= theDistance [ theStart [ 0 ] ] [ theStart [ 1 ] ]) {
      theQueue [ 0 ] [ 0 ] = theStart [ 0 ] ;
      theQueue [ 0 ] [ 1 ] = theStart [ 1 ] ;
      queueOut = 0 ; queueIn = 1 ;
      for ( i = 0 ; i < numRows ; i ++ ) {
        for ( j = 0 ; j < numCols ; j ++ ) {
          used [ i ] [ j ] = 0 ;
        }
      }
    } else {
      queueOut = 0 ; queueIn = 0 ;
    }
    int r, c ;
    int rowStop = theStop [ 0 ] ;
    int colStop = theStop [ 1 ] ;
    while ( queueOut < queueIn ) {
      r = theQueue [ queueOut ] [ 0 ] ; c = theQueue [ queueOut ] [ 1 ] ;
      ++ queueOut ;
      if ( rowStop == r && colStop == c ) {
        bSolFound = true ;
        break ;
      }
      if ( 0 < r && ! used [ r - 1 ] [ c ] && nSolMiddle <= theDistance [ r - 1 ] [ c ] ) {
        theQueue [ queueIn ] [ 0 ] = r - 1 ;
        theQueue [ queueIn ] [ 1 ] = c ;
        used [ r - 1 ] [ c ] = 1 ;
        ++ queueIn ;
      }
      if ( 0 < c && ! used [ r ] [ c - 1 ] && nSolMiddle <= theDistance [ r ] [ c - 1 ] ) {
        theQueue [ queueIn ] [ 0 ] = r ;
        theQueue [ queueIn ] [ 1 ] = c - 1 ;
        used [ r ] [ c - 1 ] = 1 ;
        ++ queueIn ;
      }
      if ( numRows > r + 1 && ! used [ r + 1 ] [ c ] && nSolMiddle <= theDistance [ r + 1 ] [ c ] ) {
        theQueue [ queueIn ] [ 0 ] = r + 1 ;
        theQueue [ queueIn ] [ 1 ] = c ;
        used [ r + 1 ] [ c ] = 1 ;
        ++ queueIn ;
      }
      if ( numCols > c + 1 && ! used [ r ] [ c + 1 ] && nSolMiddle <= theDistance [ r ] [ c + 1 ] ) {
        theQueue [ queueIn ] [ 0 ] = r ;
        theQueue [ queueIn ] [ 1 ] = c + 1 ;
        used [ r ] [ c + 1 ] = 1 ;
        ++ queueIn ;
      }
    }
    if (bSolFound) {
      nSol = nSolMiddle ;
      nSolMin = nSolMiddle + 1 ;
    } else {
      nSolMax = nSolMiddle - 1 ;
    }
  }
  io = fopen ( "barbar.out", "w" ) ;
  fprintf ( io , "%d\n", nSol ) ;
  fclose ( io ) ;
  return 0 ;
}