(*************************************************************************
 *      Lawnmowing problem
 *
 *      For:    1997 UMCP Programming Contest
 *      Author: David Mount
 *      Date:   March 17, 1997
 *
 *      This program determines the region of a grid reachable
 *      by a 3x3 square lawnmower.  The region is given as a 
 *      grid of characters, where the entries have the following
 *      interpretation:
 *
 *              .       nothing here
 *              +       a tree (the lawnmower cannot overlap this square)
 *              M       the initial center of the mower
 *      
 *      At all time the lawnmower must remain within the mowing
 *      region, and may not overlap a tree.  It may move horizontally
 *      or vertically by one square, so long as it does not violate
 *      these rules.  The final output is the set of squares that
 *      the lawnmower can cover.
 *************************************************************************)

program Mow(input, output);

var
    F: array [1..40, 1..40] of char;            (* input array *)
    G: array [1..40, 1..40] of char;            (* output array *)
    temp : char;
    len, wid: integer;                          (* length and width *)
    i, j : integer;
    ii, jj : integer;
    grew : boolean;

    (********************************************************************
     *  Try(i,j):
     *  Test whether square F[i,j] can be marked, and if so, mark it.
     *  If a new mark was created, then return true.
     ********************************************************************)

    function Try(i, j: integer): boolean;
    var
        ii, jj: integer;
        legal: boolean;
    begin
        if (F[i,j] = 'M') then                  (* already marked *)
            legal := false
        else if ((i < 2) or (i > len-1) or (j < 2) or (j > wid-1)) then
            legal := false                      (* mower extends outside *)
        else begin                              (* check for trees *)
            legal := true;
            for ii := i-1 to i+1 do for jj := j-1 to j+1 do begin
                if (F[ii,jj] = '+') then begin
                    legal := false;
                end;
            end;
            if (legal) then F[i,j] := 'M';      (* success--mark it *)
        end;
        Try := legal;
    end;

    (********************************************************************
     *  Main program:
     *
     *  The algorithm first determines all the locations that the
     *  center of the lawnmower can reach.  All such locations are
     *  marked with an `M'.
     *  
     *  This is done by a simple closure rule.  For each existing M,
     *  we consider the 4 squares where we can move.  If any of these 
     *  is `free' to place the center of the mower there, then we mark
     *  it with an `M'.  If we perform a full iteration and no new
     *  M's are added, then we terminate the closure.
     *
     *  Next we copy the F array to the G (output) array.  For each
     *  `M' in array F, we copy `O's to this and the surrounding
     *  8 squares of G.
     ********************************************************************)

    begin
    readln(len, wid);
    for i := 1 to len do begin
        for j := 1 to wid do begin
            read(temp);                         (* skip leading space *)
            read(F[i,j]);                       (* read marker character *)
        end;
        readln;
    end;

    grew := true;
    while (grew) do begin                       (* main closure loop *)
        grew := false;
        for i := 1 to len do begin              (* iterate over whole field *)
            for j := 1 to wid do begin
                if (F[i,j] = 'M') then begin    (* got here, check neighbors *)
                    grew := grew or Try(i-1,j) or Try(i+1,j)
                                 or Try(i,j-1) or Try(i,j+1);
                end;
            end;
        end;
    end;

    for i := 1 to len do begin                  (* copy F to G *)
        for j := 1 to wid do begin
            G[i,j] := F[i,j];
        end;
    end;

    for i := 1 to len do begin                  (* expand M to surroundings *)
        for j := 1 to wid do begin
            if (F[i,j] = 'M') then begin
                for ii := i-1 to i+1 do begin
                    for jj := j-1 to j+1 do begin
                        G[ii,jj] := 'O';
                    end;
                end;
            end;
        end;
    end;

    for i := 1 to len do begin                  (* produce output *)
        for j := 1 to wid do begin
            write(G[i,j]:2);
        end;
        writeln;
    end;
end.