coastline_length.py

#!/usr/bin/env python2

import sys
from collections import deque


# We need the queue to store the to-be-flooded or to-be-counted cells
queue = deque()

# This is a cell with coordinates
class Vertex(object):

    x = None
    y = None

    def __init__(self, x, y):
        self.x = x
        self.y = y

# Process the input
lines = []

for line in sys.stdin:
    lines.append(line.strip("\n"))

N = int(lines[0].split(" ")[0])
M = int(lines[0].split(" ")[1])
A = []

for i in xrange(0, N):
    A.append([int(a) for a in lines[1:][i]])

# Add the outer edges to the queue. The flood will start from out-inwards
for i in xrange(M):
    queue.append(Vertex(0, i))
    queue.append(Vertex(N-1, i))

for i in xrange(N):
    queue.append(Vertex(i, 0))
    queue.append(Vertex(i, M-1))

# Initialize
sum = 0

while len(queue):
    # Get the first vertex in the queue
    p = queue.pop()

    if p.x < 0 or p.y < 0 or p.x >= N or p.y >= M:
        # The vertex is out of bounds
        continue
    else:
        if A[p.x][p.y] == 1:
            # Count the vertex
            sum += 1
        elif A[p.x][p.y] == 0:
            # Flood the vertex, add adjacent vertices for flooding/counting
            A[p.x][p.y] = 2
            queue.append(Vertex(p.x-1, p.y))
            queue.append(Vertex(p.x, p.y-1))
            queue.append(Vertex(p.x+1, p.y))
            queue.append(Vertex(p.x, p.y+1))

print sum