Programming Praxis

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.

Pages: 1 2