[VICIUS]

Primo tentativo al primo punto decisamente naïve.

require 'tools'

class SubMatrix
  def initialize(matrix, row, col)
    @matrix, @row, @col = matrix, row, col
    @row_num, @col_num = 0, 0
  end
  
  def add_row()
    @row_num += 1
  end
  
  def add_column()
    @col_num += 1
  end
  
  def try_add_column()
    return 0 if (@col+@col_num+1) > @matrix.size-1
    for i in @row..(@row+@row_num)
      return 0 if @matrix[i][@col+@col_num+1] != 0
    end
    (@row_num + 1) * (@col_num + 2)
  end
  
  def try_add_row()
    return 0 if (@row+@row_num+1) > @matrix.size-1
    for i in @col..(@col+@col_num)
      return 0 if @matrix[@row+@row_num+1][i] != 0
    end
    (@row_num + 2) * (@col_num + 1)
  end
  
  def size()
    (@row_num + 1) * (@col_num + 1)
  end
  
  def to_s()
    "Matrice row:#{@row}, col:#{@col}, row_num:#{@row_num+1}, col_num:#{@col_num+1}, size:#{size}"
  end
end

def contest5a(matrix)
  best = nil
  for row in 0...matrix.size
    for col in 0...matrix.size
      if matrix[row][col] == 0
        sub = SubMatrix.new(matrix, row, col)
        while (sub.try_add_column > 0) or (sub.try_add_row > 0)
          if sub.try_add_column >= sub.try_add_row
            sub.add_column
          else
            sub.add_row
          end
        end
        if best.nil? or sub.size > best.size
          best = sub
        end
      end
    end
  end
  best
end

test_function :contest5a, 'Matrix0.txt'

E l'output

Matrice row:110, col:257, row_num:10, col_num:10, size:100
Tempo impiegato: (408.270025 secondi)

Forse si può migliorare evitando di chiamare le funzioni try_add due volte per tentativo. Poi voglio provare a saltare a pie pari tutti gli zeri all'interno delle precedenti soluzioni migliori. Se non perde risultati poi provo a saltare anche tutte le precedenti sotto-matrici anche se forse in questo caso sono quasi sicuro che non troverà più molte soluzioni.