(*

Il castello (IOI 1994)
Copyright (C) 2000 Paolo Boldi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*)

program Ioi9412(input,output);
const
     maxrc=50; (* Lungh. massima righe/colonne *)
	  maxst=maxrc*maxrc; (* Numero massimo stanze *)
     inputfile='input.txt'; (* Nome file di input *)
     outputfile='output.txt'; (* Nome file di output *)
     DEBUG=false;
type
    direzione=(nord,sud,est,ovest);
    indicemod=1..maxrc;
    indicest=0..maxst; (* Indice stanza; 0=nessuna stanza *)
    infoad=record
                 adiacenti: boolean;
                 r,c: indicemod;
                 dir: direzione
           end;
           (* Da informazioni sull'adiacenza di due stanze; se
              adiacenti=false, le due stanze in esame non sono adiacenti.
              Altrimenti, r,c,dir indica un muro che le rende adiacenti *)
const
     nomedir: array [direzione] of char=('N','S','E','W');
     valdir: array [direzione] of byte=(2,8,4,1);
     xdir: array [direzione] of integer=(0,0,1,-1);
     ydir: array [direzione] of integer=(-1,1,0,0);
var
   modulo: array [indicemod,indicemod] of byte;
           (* Descrizione muri di ciascun modulo *)
   stanza: array [indicemod,indicemod] of indicest;
           (* Stanza corrispondente a ciascun modulo *)
   dim: array [1..maxst] of word;
        (* Dimensione di ciascuna stanza *)
   stanze: indicest; (* Numero di stanze fino ad ora trovate *)
   ad: array [1..maxst] of infoad; (* Inform. di adiacenza relative alla stanza corrente *)
   r,c: indicemod; (* Numero righe/colonne *)
   moduli: word; (* Numero di moduli ancora non assegnati *)
   max,maxs: word; (* Massima dim. e somma dim. stanze *)
   maxa: infoad; (* Informazioni su come raggiungere maxs *)
   ip,jp: word; (* Variabili locali ad assegna *)

procedure leggifile;
(* Legge il file *)
var f: text;
    i,j: indicemod;
begin
     assign(f,inputfile);
     reset(f);
     read(f,r); read(f,c);
     moduli:=r*c;
     for i:=1 to r do
         for j:=1 to c do
             begin
                  read(f,modulo[i,j]);
                  stanza[i,j]:=0;
             end;
     close(f);
end;

procedure assegna(i,j: indicemod);
(* Assegna la stanza stanze al modulo (i,j) ed estende l'assegnamento ai moduli
   adiacenti; aggiorna: moduli (n. moduli non assegnati), dim[s], e, se trova
   stanze gia' assegnate adiacenti, l'array ad *)
var  d: direzione;
begin
     stanza[i,j]:=stanze;
     dec(moduli);
     inc(dim[stanze]);
     for d:=nord to ovest do
         begin
              ip:=i+ydir[d]; jp:=j+xdir[d]; (* Modulo adiacente *)
              if (ip in [1..r]) and (jp in [1..c]) then
                 begin
                      if (modulo[i,j] and valdir[d]=0) and (stanza[ip,jp]=0) then
                         assegna(ip,jp); (* Modulo adiacente senza muro non ass. *)
                      if (modulo[i,j] and valdir[d]>0) and (stanza[ip,jp]<>0) and
                         (stanza[ip,jp]<>stanze) and (not ad[stanza[ip,jp]].adiacenti) then
                         begin (* Altra stanza adiacente *)
                              ad[stanza[ip,jp]].adiacenti:=true;
                              ad[stanza[ip,jp]].r:=j; ad[stanza[ip,jp]].c:=i;
                              ad[stanza[ip,jp]].dir:=d
                         end
                 end
         end
end;

procedure debugout;
var i,j: integer;
begin
     for i:=1 to r do
         begin
              for j:=1 to c do
                  if (stanza[i,j]>0) then write(stanza[i,j]:2)
                  else write('  ');
              writeln
         end;
     readln
end;

procedure assegnastanze;
(* Assegna le stanze a tutti i moduli; calcola anche la dimensione della
   stanza massima (max), e la massima somma di due stanze adiacenti (maxs),
   mettendo in maxa le informazioni relative al muro corrispondente *)
var i,j: indicemod;
    k: word;
    procedure primolibero(var i,j: indicemod);
    var ii,jj: indicemod;
    begin
         for ii:=1 to r do
             for jj:=1 to c do
                 if (stanza[ii,jj]=0) then
                    begin
                         i:=ii; j:=jj;
                         exit
                    end
    end;
begin
     max:=0; maxs:=0;
     stanze:=0;
     while (moduli>0) do
           begin
                inc(stanze);
                dim[stanze]:=0;
                for k:=1 to stanze-1 do
                    ad[k].adiacenti:=false;
                primolibero(i,j); (* Cerco un modulo libero *)
                assegna(i,j);
                if (dim[stanze]>max) then max:=dim[stanze];
                for k:=1 to stanze-1 do
                    if (ad[k].adiacenti) and (dim[k]+dim[stanze]>maxs) then
                       begin
                            maxs:=dim[k]+dim[stanze];
                            maxa:=ad[k]
                       end;
                if (DEBUG) then
                   begin
                        debugout; readln
                   end
           end
end;

procedure output;
(* Emette l'output *)
var f: text;
begin
     assign(f,outputfile);
     rewrite(f);
     writeln(f,stanze);
     writeln(f,max);
     writeln(f,maxa.c,' ',maxa.r,' ',nomedir[maxa.dir]);
     close(f)
end;

(* MAIN *)
begin
     leggifile;
     assegnastanze;
     output
end.