"""
From the Computer Science olympics:
http://ioi.dsi.unimi.it/problemi/

The Castle problem, 1994, day 1 problem 2 (description in Italian):
http://ioi.dsi.unimi.it/problemi/listdir.php?dir=IOI9412%20%28Il%20castello%29

Given this wall structure, the map of the castle:

     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 # ->#   |   |   |   |   #   #
   #############################  (Figura 1)

#  = Wall
|  = No wall
-  = No wall
-> = The wall that has to be removed according to the example output.

Required output:
1) How much rooms there are in the castle (a room is made of one of more blocks)
2) How big is the bigger room
3) What wall you can remove to create the biggest room. Represented as row and column
  number of the block, plus the direction of the wall (N=north/S=south/E=east/W=west).
  If more equivalent solutions are possible you have to give one of them.

The castle is divided in m * n (m<=50, n<=50) square blocks. Every block can have one to
four walls around it.

Input:
The map of the castle is represented as numbers, one for each block:
- rows and columns.
- Every block is represented with a number, it is the sum of: 1 = it has a W wall.
  2 it has a N wall, 4 it has a E wall, 8 it has a S wall. (Every internal wall is
  represented twice).
- The castle has 3 or more rooms.

INPUT.TXT for our example:

4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

Output for our example:

5
9
4 1 E
"""

# The Castle problem. Solution by leonardo maffi, Jun 30 2006.
# This Python solution is about 35 lines, the Pascal solution is about 140 lines,
# but this uses my external graph library.

import graph # http://www.fantascienza.net/leonardo/so/graph.zip
from baseConvert import baseConvert as bc # http://www.fantascienza.net/leonardo/so/baseConvert.py

# Note: external walls must be present
data0 = """\
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13"""

data1 = [map(int, line.strip().split()) for line in data0.split("\n") if line.strip()]
data2 = [[bc(n, 10, 2).zfill(4) for n in row] for row in data1]
nx = len(data2[0])
ny = len(data2)

cast = graph.Graph()

# An explicit addition of the blocks is necessary to let it count the rooms with four walls around them
blocks = [(r, c) for r in xrange(ny) for c in xrange(nx)]
cast.addNodes(blocks)

# To draw the free spaces of the castle
# cast.nodeData = dict( ((r, c),(c,10-r)) for r in xrange(ny) for c in xrange(nx) )
# cast.plot2d()

for r, row in enumerate(data2):
    for c, block in enumerate(row):
        n1 = (r, c)
        for w, n2 in zip(block, [(r+1,c),(r,c+1),(r-1,c),(r,c-1)]):
            if not int(w):
                cast.addBiArc(n1, n2)

rooms = cast.connectedComponents()
print "Number of rooms:", len(rooms)
print "Size of the biggest room:", max(map(len, rooms))

def external_wall((r1,c1), (r2,c2)):
    """Return True if the wall (r1,c1) <-> (r2,c2) is an external wall."""
    return r1 in (-1, ny) or r2 in (-1, ny) or c1 in (-1, nx) or c2 in (-1, nx)

max_nblocks = 0
sugg_w = (None, None) # Suggested wall
for r, row in enumerate(data2):
    for c, block in enumerate(row):
        n1 = (r, c)
        for direction, (w, n2) in enumerate(zip( block, [(r+1,c),(r,c+1),(r-1,c),(r,c-1)] )):
            #if external_wall(n1, n2): print n1, n2 # Debug: print external walls
            if int(w) and not external_wall(n1, n2):
                cast.addBiArc(n1, n2)
                nblocks = len( cast.BFS(n1) )
                #print n1, n2, nblocks
                if nblocks > max_nblocks:
                    max_nblocks = nblocks
                    sugg_w = (n1, direction)
                cast.delBiArc(n1, n2)

print "Suggested wall:", sugg_w[0][0]+1, sugg_w[0][0]+1, "SENO"[sugg_w[1]]