Matrix Fill-In

January 12, 2016

The obvious solution first collects each cell containing 1 in a first pass and fills-in the matrix in a second pass:

(define (fill-in m)
  (let ((nrows (matrix-rows m))
        (ncols (matrix-cols m))
        (xs (list)))
    (for (r 0 nrows)
      (for (c 0 ncols)
        (when (= (matrix-ref m r c) 1)
          (set! xs (cons (cons r c) xs)))))
    (let loop ((xs xs))
      (cond ((null? xs) m)
      (else (for (r 0 nrows)
              (matrix-set! m r (cdar xs) 1))
            (for (c 0 ncols)
              (matrix-set! m (caar xs) c 1))
            (loop (cdr xs)))))))

This operates in time O(kmn) on an m × n matrix with k intial 1-cells:

> (fill-in '#(
    #(0 0 0 0 0)
    #(0 0 0 0 0)
    #(0 0 0 1 0)
    #(1 0 0 0 0)
    #(0 0 0 0 0)))
#(#(1 0 0 1 0)
  #(1 0 0 1 0)
  #(1 1 1 1 1)
  #(1 1 1 1 1)
  #(1 0 0 1 0))

We used the matrix operations from the Standard Prelude. You can run the program at http://ideone.com/zDuUDl.

Advertisements

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: